HashMap知识总结

HashMap:

 1.   扰动函数hash值右移16位与原hash值做异或运算得出的新hash值散列程度高.  
 2.   负载因子0.75,就是说一个数组初始化new HashMap(17)容量会比17最小2的n次方大,就是32,
   想要已空间换时间,就是负载因子小于0.75这样的话hash冲突更低,但是扩容频率更高.
 3    扩容,jdk1.7采用重新计算hash值的方式,1.8直接用hash右移16位高位与低位进行与运算得出
   低5位是否是0进行判断是否需要重新计算索引位置,0保持原位置,1数组长度加索引.

1
2
3
4
5
6
7

hashMap的put方法:

1   首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
2   判断tab是否为空或者长度为0，如果是则进行初始化扩容操作。
3   根据哈希值计算下标，如果对应下标正好没有存放数据，则直接插入即可否则需要覆盖.
4   判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。 
5   如果链表中插入节点的时候，链表长度大于等于8，并且tab桶大于64则需要把链表转换为红黑树。
6   最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容

1
2
3
4
5
6
7

链表树化

1   链表树化的条件有两点；链表长度大于等于8、桶容量大于64，否则只是扩容，不会树化。
2   链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗平衡树。同时在树转换过程中
会记录链表的顺序，tl.next = p，这主要方便后续树转链表和拆分更方便。
3   链表转换成树完成后，在进行红黑树的转换。先简单介绍下，红黑树的转换需要染色和旋转，以及比对大小。
1
2
3
4

hashMap 的get方法:

1   扰动函数获取key的hash值
2   计算下标
3   获取桶下标位置,遍历链表红黑树
1
2
3