HashMap源码浅析

java1.8 hash算fa优化

HashMap的数据结构：entry数组+链表/红黑树

一、根据key进行寻址（位运算）

 // JDK 1.8以后的HashMap里面的一段源码
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h ››› 16);
}

hashMap首先会根据key计算出一个hash值。这段代码也解释了为什么hashMap的key可以为null，
如果key为null，则它的hash值默认为0。

1、int值在计算机中是32位的，例如：
h = key.hashCode()，h=1111 1111 1111 1111 1111 1010 0111 1100

h ››› 16,h向右移动16位之后的值为：0000 0000 0000 0000 1111 1111 1111 1111

然后两个值进行异或运算（不同取1，相同取0）。新的hash值为：
1111 1111 1111 1111 0000 0101 1000 0011

之所以这样运算是为了，与原值相比，新值的低16位同时具备了高16位
和低16位的共同的特征，尽可能的降低hash冲突。

2、在真正put的时候其实根据 if ((p = tab[i = (n - 1) & hash]) == null)
计算出位桶位置，这里之所以用了hash & (n - 1) ，其实就是用了取模运算，只不过借用了
位运算的方式代替了取模，也从侧面说明为什么HashMap的扩容每次都是2的幂次。

二、解决hash冲突

1、采用hash & (n - 1)与运算（相同为1，不同为0）
2、如果还有冲突，采用链表的方式，如果链表的长度大于8则变成红黑树。

常用的解决hash冲突的方法有；
（1）开放定址法(2)链地址法(3)再哈希法(4)公共溢出区域法

三、扩容

1、首先会进行rehash，即用每个hash值跟新数组的lenth-1进行与操作。

之前冲突的数据，在rehash之后，可能就不冲突了，不冲突的数据的新位置是
在老位置的基础上加上扩容前数组的长度。