lua hash 函数的一点讨论

最近一段时间，lua 的邮件列表中有好几个主题讨论 hash 表的设计。我读下来受益匪浅。比如 前两周的这个主题 中，有同学主张去掉 lua hash table 中的链表指针，而改成固定步长的冲突链表。具体这里就不展开了，有兴趣的同学可以自己看。

这两天的讨论是围绕 lua 的 hash 函数的，暂时还没有固定链接，我把我的理解和思考记录下来，不一定正确，如有行家发现错误，请不吝赐教。

unsigned int
luaS_hash (const char *str, size_t l, unsigned int seed, size_t step) {
  unsigned int h = seed ^ cast_uint(l);
  for (; l >= step; l -= step)
    h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
  return h;
}

来看这样一个 hash 函数：

(h<<5) + (h>>2) 本质上相当于 ((h<<7) + h) >> 2 ，不同的是，前者可以多保留 2 个高位，不至于移出去。

而 (h<<7) + h 即 h * 129 ，所以这个算法本质上就是 Knuth 在《计算机编程艺术》第 3 卷 第 2 版的 6.4 节谈论的 hash 算法。

不过这个乘数选的不好，因为它不是素数。为什么素数更好呢？我的理解是，hash 函数和伪随机数列发生器类似，都是想把源数据流变得随机。因为在 hash 表的实现中，桶的数量比较小，往表中放的时候需要按桶的数量再次取模。数据是随机时，取模后碰撞的几率更小。

当采用 LCG 算法时，乘数的选择会影响随机数列的周期，为了获得更大的周期，就需要取更大的素数做乘数。非素数因为可以被分解为更小的素数的积，所以不如差不多大的素数。

这里采用移位和加法是建立在乘法运算的开销明显大于移位和加法的前提上的，但本质上，乘法就是若干次的移位和加法的组合。太多次的移位的开销未必还能比单次乘法要低，所以我们在优化常数乘法的时候，要谨慎选择常数。

这里有同学建议把这里的算法改成 (h<<4)-(h>>3) ，它等价于 (h*127)>>>3 同时保护了高 3 位。和原版的区别在于 127 是一个梅森素数。 乘数是梅森数 (2^n-1) 可以保证能分解成一次移位和一次减法。

这里把移位从 2 改成 3 的道理在于，hash 函数是迭代处理数据流的，而数据流是按计算机字长逐个输入。通常字长都是 2 的倍数，所以移位的数量不宜是 2 ，3 会更好一些。

如果设备的乘法足够快的话，其实直接用乘法而不是用移位可能更好。因为我们可以选择更好的乘数。

Thomas Wang 有一篇关于 Integer Hash Function 的文章分析了怎样构造 hash 函数。

构造一个整数 hash 函数应该保证运算步骤是可逆的。因为只要存在可逆函数，就能保证源和结果 1:1 对应，避免了冲突。

加减法、左移、取反、异或操作都是可逆操作，乘法可以看作是移位和加法的组合，也是可逆的。

为了达到随机的效果（即 2 进制表达时，每个 bit 是 0 或 1 的可能性都是 50% ），我们迭代计算 hash 的过程，每 1bit 输入都尽量多个 bits 的变化。

上面的可逆操作中，移位、取反、异或要么是调整了 bits 的位置，要么是做了整体反转。真正引起变化的是加减法。比如 0111 + 1 = 1000 ，它让若干个连续 bits （但不是整体）反转了。只要结合这些运算，就能达到 hash 和稀(泥) 的效果。

乘法相当于多次的移位和加法，其实从实用价值上看，性价比是很高的。加法的次数等价于乘数中连续 1 的区段的个数。从这个角度看，0101010101 这样交错形式的乘数性价比最高。

对于 32bit 的 word ，我们应该选一个 16bit 的乘数。可惜 0b0101010101010101 = 0x5555 是 5 的倍数不是素数，如果稍微调整一下， 0b1010101010101011 = 0xAAAB = 43691 这个素数更好一些。

如果我们把上面的算法改写成：

h ^= ((h + cast_byte(ptr[l])) * 0xAAAB)>>3

或许是一个更好的 hash 函数。

我还猜想， 11011011 这样两个 1 一个 0 的模式会不会更好，因为 0b1011011011011011 = 0xB6Db = 46811 是一个更大的素数。

btw, Knuth 针对 64bit word 提出的乘数建议是 2654435761 ，它是 2^32 的黄金分割点附近的素数。