SMILE 哈希函数库实战指南:MurmurHash2/3、完美哈希与 SimHash 相似检测

原创2026-10-08 21:33:051,947 阅读
文章标签:机器学习深度学习人工智能大模型本地部署模型推理服务NLP数据可视化桌面应用IDEAI Agent

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)完整实现了文档描述的六步流程:

  1. 字符频率分析:统计所有关键字中每个字符的出现频率,按聚合频率降序排列关键字,让约束最强的键先放置(countCharacterFrequency / sortKeys,见 PerfectHash.java);
  2. 表大小选择:初始 tsize = n + (n >> 1)(即 ceil(1.5 * n)),负载因子约 2/3(PerfectHash.java);
  3. 随机赋值:给 kvals 每个槽位赋 [0, tsize) 内的均匀随机整数,然后检查 n 个键是否全部映射到不同槽位;
  4. 重试:若发生冲突则重新抽取随机 kvals。负载因子 2/3 时单次随机赋值无冲突概率至少为 e^(−n²/(2·tsize)) ≈ e^(−3n/4),因此期望尝试次数为 O(1);
  5. 表扩容:若 1000 次尝试(源码常量 MAX_RETRIES = 1000,见 PerfectHash.java)仍未找到无冲突赋值,tsize 自增 1 后从头再搜(PerfectHash.java),保证必然终止;
  6. 建表:找到无冲突 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. 验证与进一步阅读

SMILE — © 2010-2026 Haifeng Li. GNU GPL 许可。

登录后查看全文
smile