常见 hash 散列算法的分布和性能比较
hash 散列算法是计算机算法中非常重要的一种基础算法，在计算机软硬件的各个领域都有所应用。这篇文章就对此作简要的分析。
什么是 hash 散列
这里再次引用维基百科的定义：
散列函数（或散列算法，又称哈希函数，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。
这个定义对学计算机的同学应该很清楚了。在这里仅对还不明白的同学举个浅显的栗子：
就像是一个学校来了的2000名新生，学校有365间宿舍，怎么分宿舍呢？— 将1月1号的分到同一间屋，1月2号的一间… 一直到12月31号的同学住一间。这样又平均又快速明了，不用任何多余的数据记录，仅凭每人的生日特征就搞定了。
个人原创解释：散列就是对复杂特征的数据源进行特征的简化、分类。
计算机应用
散列在计算机方面的应用真是实在太多了。 数据存储、加密、校验；map 类的数据结构；负载均衡；网络拓扑等等方面都以散列算法做为基础。其重要性就不再多语了。
笔者在2016上半年写的一个 http2 检测统计站点里，在 UA 查找、特征化记录上散列算法起到的核心作用。
常见的散列算法
在这里给出几种基础散列算法的 js 版本。这些经典的算法都是一些牛B的前人研究出来的，我们也受些熏陶。
/**
* 加法 hash
*/
function additiveHash(string, range) {
let hash, i;
for (hash = string.length, i = 0; i < string.length; i++) {
hash = hash + string.charCodeAt(i);
}
return range ? hash % range : hash;
}
/**
* 位运算 HASH
*/
function rotatingHash(string, range) {
let hash, i;
for (hash = string.length, i = 0; i < string.length; i++) {
hash = hash << 4 ^ hash >> 28 ^ string.charCodeAt(i);
}
hash = range ? hash % range : hash;
return Math.abs(hash);
}
/**
* 乘法 hash
* 推荐乘数可以是31.131.13131.13131...
*/
function bernsteinHash(string, range) {
let hash = 0,
i;
for (i = 0; i < string.length; i++) hash = 131 * hash + string.charCodeAt(i);
return range ? hash % range : hash;
}
/**
* 改进后的 FNVHash
*/
function FNVHash(string, range) {
let p = 16777619,
hash = 2166136261;
for (let i = 0; i < string.length; i++) hash = (hash ^ string.charCodeAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return range ? hash % range : hash;
}
分布及其性能
在这里，笔者对每种 hash 散列算法的分布情况(10000000个无规律数据分布在1000个点上)和性能（node v8）进行了一个简单的测试，比较一下各算法的优劣。
| 算法 | 分布 | 性能 |
|---|---|---|
| 加法 | 差 | 优 |
| 位运算 | 优 | 优 |
| 乘法 | 良 | 优 |
| FNVHash | 优 | 良 |
统计方式和详细结果会在稍后给出
由此可见，一般的话，我们选择位运算 hash 算法是最合适的。笔者的统计可能比较我狭义，不能代表其它的算法就完全没有用，这个有机会会对些进行进一步研究。
