Time33算法

Hash-链地址法

一、哈希(Hash)简介

Hash，一般翻译做“散列”，也有直接音译为”哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。

这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。用数学语言来讲就是空间变换，从一个自变量空间映射到另一个值空间。也可以认为是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

使用哈希查找有两个步骤:

使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况，所以哈希查找的第二个步骤就是处理冲突。
处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法

哈希表是一个在时间和空间上做出权衡的经典例子。

如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；
如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。

哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

目前常用的hash方法有：开放地址法、再哈希法、链地址法（拉链法）

二、Time33方法

目前普遍采用的哈希算法是time33，又称DJBX33A (Daniel J. Bernstein, Times 33 with Addition)。这个算法被广泛运用于多个软件项目，Apache、Perl和Berkeley DB等。对于字符串而言这是目前所知道的最好的哈希算法，原因在于该算法的速度非常快，而且分类非常好(冲突小，分布均匀)。

对于一个Hash函数，评价其优劣的标准应为随机性，即对任意一组标本，进入Hash表每一个单元（cell）之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。

Time33算法：

对字符串的每个字符，迭代的乘以33
hash(i) = hash(i-1) * 33 + str[i]

三、PHP中Time33实现方式

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
     register ulong hash = 5381;
 
     /* variant with the hash unrolled eight times */
     for (; nKeyLength >= 8; nKeyLength -= 8) {
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
     }
     switch (nKeyLength) {
          case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 1: hash = ((hash << 5) + hash) + *arKey++; break;
          case 0: break;
     }
     return hash;
}

为什么初始值是`5381`？

5381（001 010 100 000 101），据说hash后的分布更好一些。

四、参考

1、PHP内核中的神器之HashTable
2、详解time33 hash函数
3、解决Hash碰撞冲突方法总结
4、Hash算法和Hash冲突碰撞
5、位与&，位或|，位异或^运算，以及运用场景
6、常见算法及问题场景——散列（哈希）