HashMap底层源码

...

假设当前HashMap底层存储的机构如下：1.两个线程都在往hashMap中put值，数组发生扩容，数据发生transfer2.Thread1线程transfer的时候，刚执行完核心代码的第2行，记录了next：为B节点，cpu执行权被Thread2获取3.Thread2线程已经完成扩容，由于采用的是头插法，所以A->B变为B->A。4.Thread1继续执行，在执行过程中，节点顺序变为B->A->null，由于Thread2将Entry变为B->A，所以Thread1在继续执行的时候，就会形成B和A的闭环5.在下次遍历到这个链表的时候，就会造成死循环的问题。

将链表转换为红黑树

1.hash(key):计算key的hashCode，并且采用算法（高位二进制参与计算hash，这样的方式减少hash冲突的发生）：扰动函数2.indexFor(hash):计算索引

Y

4

B

hashMap.putVal()

N

resize进行扩容扩容的方式采用尾插法

1.7中出现的死循环问题多线程

++size>threshold

A

end

3

2

6

10

tab[i].hash == hash&& tab[i].key == key

treeifyBin()判断当前tab.length<64

size>threshold

resize()创建table

jdk1.8

循环i位置链表是否有hash(key)是否一致&&key.equals(currentEntry.key)

newNode添加新的节点到链表尾部

init tableinit threshold

newNode添加新的Node到table中

p instanceOf TreeNode

0

addEntry()

添加到RBT中

resize()

creatEntry()添加节点的时候也是采用的头插法

1

替换currentNode

tab[i] == null

为什么扩容是2的倍数1 h%n==h&(n-1) 增加运算速度2 使hash分布更均匀，减少哈希碰撞3 扩容时仅需要多比较1个bit：4 扩容迁移时，仅有一半的数据要迁移，减少迁移成本

table== EMPTY_TABLE

双层循环遍历Entry，采用头插法迁移数据

覆盖原有的Entry中的值

8

遍历链表

table[i] ==null

1.1.8的HashMap底层采用的数据结构是数组+链表+红黑树2.span style=\"font-size: inherit;\

7

jdk1.7

tab == null || tab.length==0

binCount：当前链表长度binCount>8

9