MurmurHash - 它是什么？

Question

我一直试图高度了解MurmurHash的作用.

我已经阅读了一个基本的描述,但还没有找到何时使用它的好解释以及原因.我知道它非常快,但想知道更多.

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

Answer 1

Murmur是一个良好的通用散列函数系列,适用于非加密用法.如Austin Appleby所述,MurmurHash提供以下好处:

• 简单(根据生成的汇编指令数).
• 良好的分布(几乎所有键组和铲斗尺寸均通过卡方检验.
• 良好的雪崩行为(最大偏差为0.5%).
• 良好的碰撞阻力(通过Bob Jenkin的frog.c酷刑测试.对于4字节键,没有小的(1到7位)差异可能没有碰撞).
• 在Intel/AMD硬件上表现出色,散列质量和CPU消耗之间的良好折衷.

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

Answer 2

我知道我的回复很晚,但它可以帮助其他任何人...

Murmur哈希是一个非加密哈希函数 ,用于基于哈希的查找,它使用3个基本操作作为一个整体乘法,旋转和异或.它使用多个常量,通过传递2个基本测试来使其成为良好的散列函数.

1. 雪崩测试
2. Chi-Squared测试

你可以观看我制作的这段视频,详细解释Murmur Hashing.