LevelDB布隆过滤器双重哈希实现及旋转位数疑问

在阅读LevelDB的布隆过滤器实现时，会发现它没有采用传统的两个独立哈希函数，而是通过对单个哈希值做17位右旋转生成delta，再累加delta来生成多个哈希序列，核心代码如下：

// Use double-hashing to generate a sequence of hash values.
// See analysis in [Kirsch,Mitzenmacher 2006].
uint32_t h = BloomHash(keys[i]);
const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
for (size_t j = 0; j < k_; j++) {
  const uint32_t bitpos = h % bits;
  array[bitpos/8] |= (1 << (bitpos % 8));
  h += delta;
}

针对你提出的两个疑问，解答如下：

1. 17位旋转是如何选定的？ #

这个选择基于Kirsch和Mitzenmacher在2006年的论文结论：要让生成的哈希序列尽可能均匀分布，delta需要和哈希值的位数（此处为32位）互质。17是质数，且和32的最大公约数为1（gcd(17,32)=1），这样每次累加delta时，能避免生成的哈希值过早进入循环，从而覆盖更多不同的位位置。
同时，17位的右旋转能充分混合原哈希值的高位与低位——32位的一半是16位，17位刚好超过这个分界，让高低位信息交叉，避免简单移位导致的信息丢失，最大程度保留原哈希的随机性。

2. 若应用于uint64_t类型，应选择多少位旋转？ #

同样遵循与64位互质的原则，由于64是2的6次方，只要选择一个奇数质数即可（所有奇数都和2的幂次互质）。常见的选择比如41（gcd(41,64)=1），31、17这类质数也适用。核心是保证旋转后的delta与64位互质，这样累加生成的哈希序列能均匀遍历更多不同的位位置，避免重复，维持布隆过滤器的误判率性能。

内容的提问来源于stack exchange，提问作者h11