SMILE 哈希函数库实战指南:MurmurHash2/3、完美哈希与 SimHash 相似检测
SMILE 哈希函数库实战指南:MurmurHash2/3、完美哈希与 SimHash 相似检测
SMILE(Statistical Machine Intelligence & Learning Engine)的 smile.hash 包提供了一组高性能的非加密哈希函数及其上层数据结构,覆盖两类典型场景:一是哈希表、Bloom Filter、分片、校验和等需要快速且分布均匀的"常规哈希";二是固定字符串集合上的 O(1) 精确查找(完美哈希),以及大规模文档集合的近似查重(SimHash)。本文以 base/HASH.md 为主体,结合 base/src/main/java/smile/hash 的源码实现与 base/src/test/java/smile/hash 的测试用例,完整讲解这五个工具类的 API、原理与工程化用法,读完即可在项目中直接落地。
包概览:五个类各司其职
smile.hash 目前包含五个类,全部位于 base/src/main/java/smile/hash:
| 类 | 用途 |
|---|---|
MurmurHash2 |
面向原始字节数据的快速 32/64 位非加密哈希 |
MurmurHash3 |
改进版,提供 32 位与 128 位输出 |
PerfectHash |
编译期式(构造期式)完美哈希,将固定字符串集合映射到 [0, n) |
PerfectMap |
基于 PerfectHash 的不可变 String → T 字典 |
SimHash |
面向近似重复检测的局部敏感指纹 |
其中 MurmurHash2、MurmurHash3、SimHash 以 Java 接口形式提供静态工厂与静态方法(package-info.java 将包描述为 "Hashing functions");PerfectHash 与 PerfectMap 为类实现,前者可序列化,后者提供流式 Builder。
1. MurmurHash2:快速 32/64 位非加密哈希
MurmurHash2 由 Austin Appleby 设计,名字来自其内循环的两个基本操作:乘(MU) 与 旋转(R)。它非常适合哈希表构造、校验和、分片等需要快速且分布良好摘要、但不要求密码学强度的场景。
SMILE 的实现改编自 Apache Cassandra,是一个纯静态方法接口。源码注释与文档保持一致(见 MurmurHash2.java),提供两个重载:
MurmurHash2.hash32(ByteBuffer data, int offset, int length, int seed) → int
MurmurHash2.hash64(ByteBuffer data, int offset, int length, long seed) → long
1.1 32 位哈希
import smile.hash.MurmurHash2;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
byte[] data = "hello world".getBytes(StandardCharsets.UTF_8);
ByteBuffer buf = ByteBuffer.wrap(data);
int h32 = MurmurHash2.hash32(buf, 0, data.length, 42 /*seed*/);
System.out.printf("MurmurHash2-32 = 0x%08X%n", h32);
1.2 64 位哈希
long h64 = MurmurHash2.hash64(buf, 0, data.length, 0L /*seed*/);
System.out.printf("MurmurHash2-64 = 0x%016X%n", h64);
1.3 源码级实现细节
从 MurmurHash2.java 的实现可以看到两个经典常量:
- 32 位版本:乘法常数
m = 0x5bd1e995,旋转位数r = 24,按 4 字节块处理,尾部字节按length % 4收尾,最后经过h ^= h >>> 13; h *= m; h ^= h >>> 15三段混淆(见 MurmurHash2.java); - 64 位版本:
m64 = 0xc6a4a7935bd1e995L、r64 = 47,按 8 字节块处理,尾部通过 fall-through 的switch (length & 0x7)逐字节吸收(见 MurmurHash2.java)。
两个版本都显式按小端序加载字节(data.get(offset + i) 为最低字节),并支持任意 seed —— 不同 seed 会产生相互独立的哈希族。
1.4 属性总结
| 属性 | 值 |
|---|---|
| 输出宽度 | 32 或 64 位 |
| 字节序 | 小端 |
| Seed 支持 | 是 —— 不同 seed 产生独立哈希族 |
| 密码学安全 | 否 |
| 适用场景 | 哈希表、Bloom Filter、校验和、分片 |
2. MurmurHash3:更好的雪崩效应与 128 位输出
MurmurHash3 是 MurmurHash2 的继任者,改善了雪崩(avalanche)效应,并提供更宽的输出选项。SMILE 同样改编自 Apache Cassandra,提供两个变体(见 MurmurHash3.java):
MurmurHash3.hash32(String text, int seed) → int
MurmurHash3.hash32(byte[] data, int offset, int length, int seed) → int
MurmurHash3.hash128(ByteBuffer data, int offset, int length,
long seed, long[] result) → void
128 位变体实现的是 x64 版本:两条独立的 64 位 lane(h1、h2,均以 seed 初始化)在 body 阶段交替吸收 128 位块,最后在 finalization 阶段交叉混合(h1 += h2; h2 += h1 后再做 fmix,见 MurmurHash3.java)。
注意: x86 与 x64 两种 128 位变体对同一输入会产生不同输出(算法各自针对平台优化)。SMILE 只实现 x64 变体,跨语言/跨库对比结果时务必确认双方使用同一 flavour。
从源码可以看出 x64 变体使用的关键常数:c1 = 0x87c37b91114253d5L、c2 = 0x4cf5ad432745937fL,以及三段式 fmix 最终混淆函数(k ^= k >>> 33; k *= 0xff51afd7ed558ccdL; ...,见 MurmurHash3.java)。
2.1 从 String 计算 32 位哈希
import smile.hash.MurmurHash3;
int h = MurmurHash3.hash32("the quick brown fox", 0);
hash32(String, int) 内部先用 UTF-8 编码字符串再委托给字节数组版本(见 MurmurHash3.java)。
2.2 从字节数组计算 32 位哈希
byte[] data = "the quick brown fox".getBytes(StandardCharsets.UTF_8);
int h = MurmurHash3.hash32(data, 0, data.length, 0);
32 位实现使用 c1 = 0xcc9e2d51、c2 = 0x1b873593,按 4 字节块循环,尾部同样以 switch (length & 0x03) 吸收,最终经三次异或-乘混淆(见 MurmurHash3.java)。
2.3 128 位哈希(x64)
结果写入调用方提供的 long[2] 数组:result[0] = 低 64 位,result[1] = 高 64 位。
byte[] data = "the quick brown fox".getBytes(StandardCharsets.UTF_8);
ByteBuffer buf = ByteBuffer.wrap(data);
long[] result = new long[2];
MurmurHash3.hash128(buf, 0, data.length, 0L, result);
System.out.printf("h1=0x%016X h2=0x%016X%n", result[0], result[1]);
2.4 如何选择 MurmurHash2 与 MurmurHash3
| 判据 | MurmurHash2 | MurmurHash3 |
|---|---|---|
| 输出宽度 | 32、64 | 32、128 |
| 速度(64 位 JVM) | 64 位路径略快 | 32 位路径略快 |
| 雪崩质量 | 良好 | 优秀 |
| 建议 | 遗留代码 / Cassandra 兼容 | 新代码 |
3. PerfectHash:固定字符串集合上的无冲突 O(1) 查找
PerfectHash 在构造时对已知的固定字符串集合构建最小完美哈希:每个键映射到 [0, n) 中的唯一整数,查找时间 O(键长度) —— 无冲突、无链式处理。
3.1 原理:哈希函数
对长度为 L 的关键字 w,哈希值计算如下:
h(w) = (L + Σ kvals[w[i] − min]) mod tsize
其中 kvals 是按 (字符 − min_char) 索引的整数数组,tsize 是表大小(≥ n)。该公式在 PerfectHash.java 的 Javadoc 中有完整定义;对应的运行时实现见 hash(String) 方法(PerfectHash.java)。
3.2 原理:构造算法
构造采用随机化字符取值方法,源码 generate()(PerfectHash.java)完整实现了文档描述的六步流程:
- 字符频率分析:统计所有关键字中每个字符的出现频率,按聚合频率降序排列关键字,让约束最强的键先放置(
countCharacterFrequency/sortKeys,见 PerfectHash.java); - 表大小选择:初始
tsize = n + (n >> 1)(即ceil(1.5 * n)),负载因子约 2/3(PerfectHash.java); - 随机赋值:给
kvals每个槽位赋[0, tsize)内的均匀随机整数,然后检查 n 个键是否全部映射到不同槽位; - 重试:若发生冲突则重新抽取随机
kvals。负载因子 2/3 时单次随机赋值无冲突概率至少为e^(−n²/(2·tsize)) ≈ e^(−3n/4),因此期望尝试次数为 O(1); - 表扩容:若 1000 次尝试(源码常量
MAX_RETRIES = 1000,见 PerfectHash.java)仍未找到无冲突赋值,tsize自增 1 后从头再搜(PerfectHash.java),保证必然终止; - 建表:找到无冲突
kvals后,填充大小为tsize的查找表,关键字索引存入对应槽位,空槽位填-1。
整体期望构造时间为 O(n × |字母表|)。查找时除 hash() 外还会用 table<a href="https://link.gitcode.com/i/43c9af57d676628e507f27dfdf044baf" target="_blank">i] 中存的关键字索引与查询串做 equals 校验,杜绝误命中(见 get(String),[PerfectHash.java)。
3.3 基本用法
import smile.hash.PerfectHash;
PerfectHash hash = new PerfectHash("abstract", "boolean", "break",
"class", "continue", "default");
int idx = hash.get("break"); // 返回 2(上述数组中的下标)
int miss = hash.get("integer"); // 返回 -1 —— 不在集合中
3.4 选择字符位置以加速
对于长字符串,可以让哈希只使用指定位置的字符,类似 gperf 的 % 关键字选项。构造器会排序并复制 select 数组(PerfectHash.java):
// 只使用位置 0 和 1 的字符。
PerfectHash hash = new PerfectHash(new int[]{0, 1}, keywords);
选择区分度最高的位置(例如关键字的首尾字符)通常能显著缩短构造时间。测试 PerfectHashTest.java 用 new int[]{0} 在 {"apple","banana","cherry"} 上验证了该构造路径。
3.5 约束与特性
- 关键字数组必须非空,否则抛出
IllegalArgumentException(测试testEmptyKeySetThrows验证,见 PerfectHashTest.java); - 重复关键字抛出
IllegalArgumentException(构造时add()检测,PerfectHash.java); - 集合在构造期冻结 —— 之后无法增删关键字;
PerfectHash实现Serializable,且并发读是线程安全的;- 查找严格区分大小写:
get("INT")对"int"键返回-1(测试 PerfectHashTest.java 验证); - 空字符串是合法键,且查询串包含低于
min的字符时安全返回-1而非抛异常(测试 PerfectHashTest.java 验证)。
单元测试还覆盖了 50 个 Java 关键字的真实规模键集,逐一断言索引正确且非关键字返回 -1(PerfectHashTest.java)。
4. PerfectMap:不可变的 String → T 完美字典
PerfectMap<T> 是基于完美哈希的不可变 String → T 字典,查找 O(键长度),热路径零分配。非常适合小规模、固定、被高频读取的字典(如 HTTP 头表、语言关键字→token 映射、配置键→处理器表)。
从源码看,它内部持有 PerfectHash 与一个 List<T> values(PerfectMap.java):build() 时先对键集合构造 PerfectHash,再把值按 hash.get(key) 返回的索引对齐放入数组,保证 values.get(i) 与 keys<a href="https://link.gitcode.com/i/e8af9f94eed4dfec55f5165730716703" target="_blank">i] 严格对应([PerfectMap.java)。get(key) 先查哈希,索引为负(未命中)返回 null,否则取值(PerfectMap.java)。
4.1 使用流式 Builder 构建
import smile.hash.PerfectMap;
PerfectMap<Integer> tokenTypes = new PerfectMap.Builder<Integer>()
.add("abstract", 1)
.add("boolean", 2)
.add("break", 3)
.add("class", 4)
.add("continue", 5)
.add("default", 6)
.build();
int type = tokenTypes.get("break"); // 3
Object miss = tokenTypes.get("goto"); // null
4.2 从已有 Map 构建
Map<String, String> source = Map.of(
"Content-Type", "application/json",
"Accept", "application/json",
"Authorization", "Bearer …"
);
PerfectMap<String> headers = new PerfectMap.Builder<>(source).build();
String ct = headers.get("Content-Type"); // "application/json"
Builder(Map<String, T>) 构造器会把源 Map 全部复制进内部 HashMap(PerfectMap.java)。
4.3 Null 语义
get(key) 对任何不在原始键集合中的键返回 null;对格式良好(非 null)的查询串永不抛异常。注意 PerfectMap 的值不可为 null(构造时 Map.of 也不允许),因此 null 返回值可以可靠地作为"键不存在"的信号。
5. SimHash:局部敏感指纹与近似查重
SimHash 是一种局部敏感指纹(locality-sensitive fingerprinting)算法。与普通哈希不同:两个相似输入产生的指纹汉明距离很小,不相似输入则汉明距离很大。这正是 Google 爬虫用于发现近似重复页面的技术(源码注释与文档一致,见 SimHash.java)。
每个指纹是一个 64 位 long。两指纹的汉明距离为 Long.bitCount(h1 ^ h2);文档建议:汉明距离 ≤ 3 通常视为近似重复(阈值可由应用自定义)。
5.1 文本相似度(分词文档)
SimHash.text() 返回 SimHash<String<a href="https://link.gitcode.com/i/04dceb02b810aa567bb09ce42b887ff0" target="_blank">]>,把数组的每个元素当作一个 token。从源码([SimHash.java)可见内部机制:每个 token 先经 UTF-8 编码,再用 MurmurHash2.hash64 哈希,哈希位在 64 个计数器上投 +1/−1 票,最后每个计数器的符号(≥ 0 置 1)成为指纹的一位。
import smile.hash.SimHash;
SimHash<String[]> sh = SimHash.text();
String[] doc1 = {"the", "quick", "brown", "fox", "jumps"};
String[] doc2 = {"the", "quick", "brown", "fox", "leaps"}; // 仅一词不同
long h1 = sh.hash(doc1);
long h2 = sh.hash(doc2);
int hamming = Long.bitCount(h1 ^ h2);
System.out.println("Hamming distance = " + hamming); // 通常很小(≤ 5)
测试 SimHashTest.java 验证了:相似文档汉明距离 < 20,完全不同的文档汉明距离 > 5;同一输入重复哈希结果确定(testTextDeterministic,SimHashTest.java)。
5.2 加权特征向量
当文档表示为预定义特征的稀疏权重向量时,使用 SimHash.of(byte<a href="https://link.gitcode.com/i/a93388fff42f8d1cf94471c7869d3220" target="_blank">][] features)。每个特征由其字节表示标识;传给 hash(int[] weights) 的权重数组必须与 features 数组长度一致,否则抛出 IllegalArgumentException([SimHash.java),对应测试 SimHashTest.java。实现中每个特征先经 MurmurHash2.hash64 得到 64 位哈希,投票时按权重 w 做 count<a href="https://link.gitcode.com/i/c01fadb19e06eac8a0585bbceb5283be" target="_blank">j] += w(位为 1)或 count[j] -= w(位为 0)的加权累加([SimHash.java)。
byte[][] features = {
"title".getBytes(),
"body".getBytes(),
"tags".getBytes()
};
SimHash<int[]> sh = SimHash.of(features);
// 一篇 title 权重 5、body 权重 3、tags 权重 1 的文档
long fp = sh.hash(new int[]{5, 3, 1});
5.3 近似重复检测流水线
典型流水线:先为所有文档计算指纹,再用以指纹为键的哈希表找完全重复,或用汉明距离索引(如排序排列)找近似重复:
SimHash<String[]> sh = SimHash.text();
Map<Long, String> seen = new HashMap<>();
for (var entry : corpus.entrySet()) {
String id = entry.getKey();
String[] tokens = entry.getValue();
long fp = sh.hash(tokens);
// 指纹完全一致 → 很可能是重复
String prev = seen.putIfAbsent(fp, id);
if (prev != null) {
System.out.println(id + " is a near-duplicate of " + prev);
}
}
对于大规模语料,把 64 位切成 k 段、每段 b 位(标准 LSH 技术),按每一段分别分桶,即可在汉明距离 ≤ b·k 的范围内高效找对。
5.4 属性总结
| 属性 | 值 |
|---|---|
| 输出宽度 | 64 位 |
| 相似性度量 | 汉明距离 |
| 内部哈希 | MurmurHash2-64 |
| 近似重复阈值 | 汉明 ≤ 3(应用可调) |
| 线程安全 | 无状态 —— SimHash 实例线程安全 |
SimHash 是无状态的:text() 与 of() 返回的实例内部不保存文档数据,同一实例可安全地在多线程下并发调用 hash()。
6. 速查表
| 使用场景 | 推荐类 / 方法 |
|---|---|
| 将字节缓冲哈希为 32 位 int | MurmurHash2.hash32 |
| 将字节缓冲哈希为 64 位 long | MurmurHash2.hash64 |
| 将字符串哈希为 32 位 int | MurmurHash3.hash32(String, seed) |
| 将字节数组哈希为 128 位值 | MurmurHash3.hash128 |
| 固定字符串集合上的 O(1) 查找 | PerfectHash |
不可变 String → T 字典 |
PerfectMap |
| 近似重复文档检测 | SimHash.text() |
| 加权特征向量指纹 | SimHash.of(byte[][]) |
7. 验证与进一步阅读
- 文档主体:base/HASH.md;
- 源码实现:
MurmurHash2.java、MurmurHash3.java、PerfectHash.java、PerfectMap.java、SimHash.java均位于 base/src/main/java/smile/hash,另有包描述文件package-info.java; - 单元测试:MurmurHash2Test.java、MurmurHash3Test.java、PerfectHashTest.java、PerfectMapTest.java、SimHashTest.java 位于 base/src/test/java/smile/hash;
- 相邻应用:
PerfectHash式的固定字典思路与SimHash的 LSH 思想同样出现在 base/src/main/java/smile/neighbor 的近似近邻结构中(测试中可见SNLSH相关用例复用哈希基础设施)。
SMILE — © 2010-2026 Haifeng Li. GNU GPL 许可。