hash - 如何使用 MurmurHash3 32 位生成任意长度的哈希

Question

我目前正在尝试使用 MurmurHash3 散列一组字符串，因为 32 位散列似乎对我来说太大而无法处理。我想将用于生成哈希的位数减少到 24 位左右。我已经发现了一些问题，解释了如何使用 XOR 折叠将其减少到 16、8、4、2 位，但对于我的应用程序来说，这些位太少了。

有人可以帮助我吗？

标签： hashhash-functionmurmurhash

Answer 1

当你有一个 32 位散列时，它类似于（带有空格以便于阅读）：

1101 0101  0101 0010  1010 0101  1110 1000

要获得 24 位散列，您需要保留较低的 24 位。其表示法会因语言而异，但许多语言使用“x & 0xFFF”进行位与运算与 0xFFF 十六进制。这有效地做到了（将 AND 逻辑应用于数字的每个垂直列，因此 1 AND 1 为 1，0 和 1 为 0）：

1101 0101  0101 0010  1010 0101  1110 1000 AND  <-- hash value from above
0000 0000  1111 1111  1111 1111  1111 1111      <-- 0xFFF in binary
==========================================
0000 0000  0101 0010  1010 0101  1110 1000

虽然你确实从你的哈希值中浪费了一点随机性，这对于像 murmur32 这样相当不错的哈希来说并不重要，但是如果你使用你的高位进一步随机化低位，你可以期望稍微减少冲突否则会砍掉。为此，右移高位并与低位进行异或（哪个并不重要）。同样，一个常见的符号是：

 ((x & 0xF000) >> 8) ^ x

...可以读为：执行按位与仅重新训练 x 的最高有效字节，然后将其右移 8 位，然后按位异或与 X 的原始值。上述结果当且仅当第 23 位和第 31 位中的一个或另一个（但不是两者）在 x 的值中设置时，表达式然后设置第 23 位（从 0 开始计数为最低有效位）。类似地，第 22 位是第 22 位和第 30 位的异或。所以它下降到第 16 位，即第 16 位和第 24 位的异或。第 0..15 位保持与 x 的原始值相同。

另一种方法是选择一个略低于 2^24-1 的素数，然后对 32 位杂音哈希值进行 mod (%)，这将比上面的 XOR，但你显然只能得到质数 - 1 的值，而不是一直到 2^24-1。