MurmurHash

MurmurHash是一种非加密型哈希函数,由 Austin Appleby 于 2008 年设计,目标是在保证良好散列质量的同时追求极致的计算速度。它的名字来自实现中反复出现的乘法与旋转位运算。

概述

哈希函数按用途分为加密型与非加密型两类。加密型强调抗碰撞与抗逆推,但速度较慢;非加密型只求把输入均匀地映射到取值范围,速度快、分布好即可。MurmurHash 属于后者,其目标是给哈希表、数据分片等场景提供又快又均匀的散列结果。

核心特点

• 速度快:大量使用乘法、异或与位移这类廉价指令,处理大块数据时吞吐很高。
• 分布均匀:输出的每一位都受输入充分扰动影响,雪崩效应良好,不易在哈希表中形成聚集。
• 多种版本:常见有面向 32 位与 128 位输出的变体,以及针对不同平台优化的实现。
• 非安全:算法公开且可预测,不能抵御恶意构造的碰撞,不用于口令或签名。

应用场景

它常作为哈希表的默认散列函数,用于分布式系统中把键映射到分片或节点,用于布隆过滤器与 HyperLogLog 等概率结构生成哈希位,也用于快速比对大块数据是否相同。许多数据库、消息队列和大数据框架都内置了它。

常见问题

问:能用它存储用户口令吗?答:不能。它是非加密哈希,不抗逆推也不抗恶意碰撞,存储口令应使用专门的慢哈希算法。

问:面向用户输入的哈希表用它安全吗?答:若键来自不可信外部输入,攻击者可能构造大量碰撞制造性能退化,此时应使用带随机种子且抗碰撞的哈希,或对种子保密。