MurmurHash
MurmurHash
设计者
Austin Appleby
首次发布
2008
最终版本
MurmurHash3
类别
非加密哈希函数
输出长度
32 / 128 bit
速度
~5.5 GB/s
许可证
Public Domain
MurmurHash 是由 Austin Appleby 于 2008 年创建的非加密哈希函数族。其名称来源于其内部使用的乘法（MUltiply）和旋转（Rotate）操作。MurmurHash 以出色的分布性、高速度和简洁的实现著称，是哈希表和数据分片中最常用的算法之一。
版本历史
| 版本 | 年份 | 输出 | 备注 |
|---|---|---|---|
| MurmurHash1 | 2008 | 32 bit | 初始版本，已弃用 |
| MurmurHash2 | 2008 | 32/64 bit | 改进分布性，存在已知弱点 |
| MurmurHash2A | 2009 | 32 bit | 支持增量式哈希（流式） |
| MurmurHash3 | 2011 | 32/128 bit | 最终版本，修复了所有已知问题 |
MurmurHash3 原理
MurmurHash3 的核心混合操作使用乘法和旋转：
- 32位变体：读取 4 字节块，乘以常量
0xcc9e2d51和0x1b873593，然后旋转 13 和 17 位 - 128位变体：处理 16 字节块，使用 64 位乘法常量，在 x64 和 x86 平台有不同的实现
- 最终雪崩：通过
x ^= x >> 16; x *= 0x85ebca6b; x ^= x >> 13; x *= 0xc2b2ae35; x ^= x >> 16;确保良好的雪崩效应
安全性注意
MurmurHash 是非加密哈希函数，不应用于安全敏感场景。此外：
- MurmurHash2 存在哈希碰撞攻击漏洞，攻击者可以构造大量碰撞输入
- MurmurHash3 对此进行了改进，但仍然不防恶意攻击
- 在需要防哈希洪水攻击的场景中，应使用 SipHash
应用
- GNU libstdc++ 的
std::unordered_map默认哈希（部分实现） - Redis 的哈希表实现
- Cassandra、HBase 等分布式数据库的数据分片
- Bloom Filter 的首选哈希函数
- Nginx、libmemcached 等基础设施软件
参考文献
- Appleby, A. (2008-2011). "MurmurHash". https://github.com/aappleby/smhasher
- Appleby, A. (2011). "SMHasher — Test framework for hash functions". GitHub.