散列算法

散列函数

正整数

将整数散列使用的方法是除留余数法。

选择大小为素数M的数组，对于任意正整数k，计算k除以M的余数，即k%M。可以有效的将键散列在0到M-1范围内

Java中Integer的hashCode函数默认返回int值本身

浮点数

如果键是0到1的实数，将他乘以M并四舍五入得到一个0到M-1的索引值。但这个方法效果不好，键的高位对索引值影响大，最低位对散列结果没有影响。

更好的方法是将键表示为二进制数然后使用除留余数法。

字符串

可以使用除留余数法

int hash=0;
for(int i=0;i<s.length();i++)
    hash =  (R * hash + s.charAt(i)) % M;

其中java中String计算hashCode的方法

public int hashCode() {
    int h = hash; // hash默认=0,当String用new初始化的时候才会初始化成其他值
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

乘子为31的原因：

从注释中可知有如下式子(并没有什么乱用)

s_0\times31^{(n-1)} + s_1\times31^{(n-2)} + ... + s_{n-1}

31可以被jvm优化，首先可知java中利用移位运算符计算2幂乘数的乘除法效率高，由此可知

31 * i = ( i << 5 ) - i

即

31\times i=i \times 2^5 - i

(废话)

31是一个不大不小的质数，是优选质数之一，同理37、41、43亦是不错的候选质数。如果质数过小（如 2）会导致哈希值会挤在一个很小的范围内，冲突的概率会上升；如果质数过大（如 101）会导致哈希值过高很容易超过int的范围 $\tt{ -2^{31} \rightarrow 2^{31}-1} $

在《数据结构、算法与应用 C++语言描述》（第二版）中有一段与除留余数法 $f(k)=k \bmod M$ 相关算子M的描述

假设M是偶数。当k是偶数时，f(k)是偶数，当k是奇数时，f(k)是奇数。如果你的应用以偶数关键字为主，则大部分关键字都会映射到偶数为主的起始桶中，同理应用以奇数为主。所以M为偶数不能构建好的散列函数。同时，M不应该能被3、5、7等小奇数整除，也会产生不良的散列函数。故，应该选择既不是偶数又不会被小奇数整除的数，理想的M应该是一个素数，当你不能用心找到与散列表长度相近的素数，应该选择不能被2和19之间的数整除的M

参考链接：科普：为什么 String hashCode 方法选择数字31作为乘子

散列算法的步骤

根据散列函数构造哈希表

碰撞处理

拉链法（链表法）

链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位

/**
 * 在槽位bucketIndex新添加一个Entry
 * 
 * 先获取原来槽位的值（可能为null）
 * 创建一个新的Entry，并链上原来槽位的值，形成一个新的链表
 * 放入槽位，然后扩容
 * 
 * 查询到这个槽位的时候，必须要遍历链表才行，先插入的在链表后
 */
void addEntry(int hash, K key, V value, int bucketIndex) {  
    Entry<K,V> e = table[bucketIndex];  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
    if (size++ >= threshold)  
        resize(2 * table.length);  
}