hash - MurmurHash - 它是什么？

Question

我一直在努力深入了解 MurmurHash 是什么做。

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

我问了一个相关的question关于如何将 UUID 放入 Redis 位集中，有人建议使用 MurmurHash。它有效，但我想了解风险/ yield 。

Answer 1

Murmur 是一系列优秀的通用哈希函数，适用于非加密用途。正如 Austin Appleby 所说，MurmurHash 具有以下优势:

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

您当然可以使用它来散列 UUID(就像任何其他高级散列函数一样:CityHash、Jenkins、Paul Hsieh 等...)。现在，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/