HashMap - hash算法详解

1. 重点代码

• hash再运算

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 计算桶位置

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ...代码省略
    // 计算桶位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    ...代码省略

2. 代码讲解

1. key的hash值做再运算
   这里采用的是hash值高16位与低16位的异或运算，这里有两个问题，1-为什么要高位与低位进行运算，2-为什么用异或进行运算，而不用&或者|呢

• 原因:

1. 因为之后的计算hash桶位置的时候，用的算法是除余，并且数组的长度始终是2的n次方，所以桶位置的运算用2的n次方-1做与运算即可，但是这样hash高位的特征就丧失了，为了将高位特征也加入到hash计算中，所以这么操作。
2. 那为什么要用^运算，而不用&或者|呢？因为使用&，每位数据将会有1/4的概率变为0，使用|每位数据将会有3/4的概率变为1，只有使用^每位的数据变成0或者1的概率都是1/2，所以使用^。