哈希算法 xxHash 介绍和使用

Question

在阅读代码 freecache 的过程中，发现引用到了 xxHash，然后顺势又了解一下 xxHash 是个啥。

xxHash 是一种非常快的非密码散列算法，工作速度接近 RAM 限制。 它分为两种形式: 32位和64位。

基准

基准测试 使用由 Austin Appleby 在 Windows Seven 32位上用 Visual c 以单线程模式编译的开源 smhashher 程序。 参考系统使用 Core 2 Duo@3.0 GHz。

Name	Speed 速度	Quality 品质	Author 作者
xxHash 2. xxHash	5.4 GB/s 5.4 gb / s	10	Y.C.
MurmurHash 3a 3 a	2.7 GB/s 2.7 gb / s	10	Austin Appleby 奥斯汀 · 阿普尔比
SBox	1.4 GB/s 1.4 gb / s	9	Bret Mulvey 布雷特 · 马尔维
Lookup3	1.2 GB/s 1.2 gb / s	9	Bob Jenkins 鲍勃 · 詹金斯
CityHash64 64	1.05 GB/s 1.05 gb / s	10	Pike & Alakuijala
FNV 国家自然保护联合会	0.55 GB/s 0.55 gb / s	5	Fowler, Noll, Vo 福勒，诺尔，沃
CRC32	0.43 GB/s 0.43 gb / s	9
MD5-32	0.33 GB/s 0.33 gb / s	10	Ronald L.Rivest 罗纳德 · 里维斯特
SHA1-32	0.28 GB/s 0.28 gb / s	10

其中 Quality 是对散列函数质量的度量。 这取决于是否成功通过 SMHasher 测试集。 10分是个完美的分数。

非加密现代 hash 列表

非加密现代 hash 列表:

年份	算法	作者	使用者
2006	lookup3	Bob Jenkins
2008	MurmurHash	Austin Appleby	redis
2011	SpookyHash	Bob Jenkins
2011	CityHash	google
2012	xxhash	Y.C.
2014	FarmHash	google

hash 算法应用 -- 列表

1. 负载均衡，分布式缓存节点调度、分布式节点调度
2. Hash 表数据字典（压缩、索引）、缓存等
3. 安全相关 密码表、数字签名（SHA）、文件校验（MD5）、鉴权协议
4. 海量数据处理 bloom filter