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

Question

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

有人可以帮我吗？

Answer 1

当你有一个 32 位散列时，它类似于（带有可读性的空格）：

1101 0101  0101 0010  1010 0101  1110 1000

要获得 24 位哈希值，您需要保留低位 24 位。表示法因语言而异，但许多语言使用“x & 0xFFF”与 0xFFF 十六进制进行按位 AND 运算。这有效地做到了（将 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.[=13 的原始值相同=]

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

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

How to generate hash of arbitrary length with MurmurHash3 32 bit

hash

hash-function

murmurhash