xxHash
xxHash
Extremely Fast Hash
Extremely Fast Hash
设计者
Yann Collet
首次发布
2012 (XXH32/64)
2019 (XXH3)
2019 (XXH3)
类别
非加密哈希函数
输出长度
32 / 64 / 128 bit
速度
~11 GB/s (XXH3)
许可证
BSD 2-Clause
安全用途
不适用
xxHash 是由 Yann Collet（同时也是 Zstandard 压缩算法的作者）设计的超高速非加密哈希算法族。xxHash 以接近内存带宽极限的吞吐量著称，广泛用于数据校验、文件分片、哈希表等对性能要求极高的场景。
算法变体
| 变体 | 输出 | 发布 | 速度 (GB/s) | 特点 |
|---|---|---|---|---|
| XXH32 | 32 bit | 2012 | ~6.0 | 兼容32位平台，简单快速 |
| XXH64 | 64 bit | 2012 | ~9.5 | 64位平台最佳，广泛使用 |
| XXH3 | 64/128 bit | 2019 | ~11.0 | 最新版本，速度之王 |
| XXH128 | 128 bit | 2019 | ~11.0 | XXH3 的128位输出变体 |
XXH3 技术特点
XXH3 是 xxHash 系列的最新成员，采用了多项创新技术：
- 宽读取策略：每次读取 64 字节（一行缓存行），充分利用内存带宽
- 延迟乘法：使用 64×64→128 位乘法作为主要混合手段，比传统旋转更高效
- 分层处理：小输入（≤ 16 字节）使用专用快速路径，中等输入使用迭代路径，大输入使用条纹（stripe）路径
- 秘密值：使用预定义的随机常量表（secret）增强分布质量
- 零分支设计：核心循环无分支预测失败
XXH3-64 核心迭代（简化）：
for each 64-byte stripe:
# 读取两个 64 位值
data_val = read64(input + offset)
data_val2 = read64(input + offset + 8)
# 使用秘密值和乘法混合
acc += data_val ^ secret[i]
acc = mul128_fold64(acc, data_val2)
# 更多轮混合...
final_mix(acc) # 最终雪崩混合
性能基准
在 Intel Core i9-11900K (DDR4-3200) 上的实测吞吐量（大输入，单线程）：
| 算法 | 吞吐量 (GB/s) | 占内存带宽比例 |
|---|---|---|
| XXH3 | ~11.0 | ~70% |
| XXH64 | ~9.5 | ~60% |
| CRC-32 (硬件) | ~15.0 | ~94% |
| MurmurHash3 | ~5.5 | ~34% |
| BLAKE3 | ~7.0 | ~44% |
| SHA-256 | ~1.8 | ~11% |
应用场景
- 数据校验：Zstandard 压缩格式使用 xxHash 作为默认校验
- 分布式存储：Ceph、MinIO 等用于数据分片和校验
- 数据库：ClickHouse 用于数据校验和哈希分区
- 文件系统：Btrfs 的 xxHash 校验选项
- 网络：gRPC 用于消息校验
参考文献
- Collet, Y. (2012-2024). "xxHash — Extremely Fast Hash Algorithm". GitHub: cyan4973/xxHash.
- xxHash Benchmark. https://github.com/Cyan4973/xxHash#benchmark