Hash算法-time33

发表于 更新于 分类于

散列表的应用

涉及到数据查找比对，首先考虑到使用HashSet。HashSet最大的好处就是实现查找时间复杂度为O（1）。使用HashSet需要解决一个重要问题：冲突问题。对比研究了网上一些字符串哈希函数，发现几乎所有的流行的HashMap都采用了DJB Hash Function，俗称“Times33”算法。Times33的算法很简单，就是对字符串逐字符迭代乘以33，见下面算法原型:hash(i)=33*hash(i-1)+str[i]

1
2
3
4
5
6
7
8
uint32_t time33(char const *str, int len)   
{   
        unsigned long  hash = 0;   
        for (int i = 0; i < len; i++) {   
            hash = hash *33 + (unsigned long) str[i];   
        }   
        return hash;   
}

把乘法操作换成位操作(Java版)

1
2
3
4
5
6
7
8
9
10
public String time33(String skey) {  
        if (skey == null) return null;  
        int hash = 5381;  
        for (int i = 0, len = skey.length(); i < len; ++i) {  
            int cc = skey.charAt(i);  
            hash += (hash << 5) + cc;  
        }  
        hash &= 0x7fffffff;  
        return String.valueOf(hash);  
    }

Time33在效率和随机性两方面上俱佳。对于一个Hash函数，评价其优劣的标准应为随机性，即对任意一组标本，进入Hash表每一个单元（cell）之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。

为什么初始值是5381？5381（001 010 100 000 101），据说hash后的分布更好一些。

如何实现乘除运算和位运算之间的转化：
a<<n 在数值上等同于 a*2^n
a>>n 在数值上等同于 a/2^n
比如 a*33 (33=2^5+1)用位运算可以写成 ((a<<5)+a)

其它倍数
Ngix使用的是 time31
Tokyo Cabinet使用的是 time37
Bob在他的文章说，小写英文词汇适合33, 大小写混合使用65。time33比较适合的是英文词汇的hash.