View on GitHub

Yinjie - GitHub.io

Welcome to the Yinjie's notes

常见 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 算法是最合适的。笔者的统计可能比较我狭义,不能代表其它的算法就完全没有用,这个有机会会对些进行进一步研究。