85

我一直试图对MurmurHash所做的事情有一个高层次的理解。

我已经阅读了基本描述，但还没有找到关于何时使用它以及为什么使用它的很好的解释。我知道它非常快，但想知道更多。

我问了一个有关如何将 UUID 放入 Redis bitset 的相关问题，有人建议使用 MurmurHash 。它有效，但我想了解风险/收益。

4

2 回答 2

118

Murmur 是一系列良好的通用散列函数，适用于非加密用途。正如 Austin Appleby 所说，MurmurHash 提供以下好处：

  • 简单（就生成的汇编指令的数量而言）。
  • 良好的分布（通过几乎所有键集和桶大小的卡方测试。
  • 良好的雪崩行为（最大偏差为 0.5%）。
  • 良好的抗碰撞性（通过 Bob Jenkin 的 frog.c 酷刑测试。4 字节密钥不可能发生碰撞，没有小的（1 到 7 位）差异）。
  • 在 Intel/AMD 硬件上具有出色的性能，在哈希质量和 CPU 消耗之间取得了良好的平衡。

您当然可以使用它来散列 UUID（就像任何其他高级散列函数：CityHash、Jenkins、Paul Hsieh's 等）。现在，Redis 位集限制为 4 GB 位 (512 MB)。因此，您需要将 128 位数据（UUID）减少到 32 位（散列值）。无论散列函数的质量如何，都会发生冲突。

使用像 Murmur 这样的工程散列函数将最大限度地提高分布的质量，并最大限度地减少冲突的数量，但它不能提供其他保证。

以下是一些比较通用哈希函数质量的链接：

http://www.azillionmonkeys.com/qed/hash.html

http://www.strchr.com/hash_functions

http://blog.aggregateknowledge.com/2011/12/05/choosing-a-good-hash-function-part-1/

http://blog.aggregateknowledge.com/2011/12/29/choosing-a-good-hash-function-part-2/

http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/

于 2012-08-10T12:25:22.263 回答
-3

MurmurHash 可以返回负值，原值位 AND 与 0x7fffffff。即 value & 0x7fffffff 。当输入为正时，返回原值。当输入数字为负时，返回的正值是原始值位与 0x7fffffff 不是绝对值。注意：MurmurHash 的返回值不能固定长度。

于 2020-05-21T03:23:25.643 回答