HashMap底层原理

GC回收

否

是

转换为树

遍历旧数组

如果此时高位头结点不为空

第二个if语句根据(n-1)&hash 定位数组的下标，如果这个位置的元素为空

扩容resize（）

font color=\"#323232\

如果低位的头结点不为空

for循环，当链表的节点的next为空时

HashMap的构造方法不提供数组的初始化

设置新阈值newThr

不等于0说明是高位

如果该位置的元素不为空

扩容阈值newThr = oldThr << 1; // double threshold

旧数组的长度大于0，已经初始化完成

调用split()方法进行扩容

数组未初始化

当前位置只有一个节点，因此将treeNode对象赋值给尾结点，并记录节点个数

判断是否树化

判断是不是红黑树p instanceof treeNode

start

数组已经初始化完成，并且不是头结点

三目运算判断数组容量、阈值是否小于数组最大容量float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);

for循环的对象的hash码与旧数组的长度进行与运算

int hash = hash(key)

将阈值赋值给新数组的容量 newCap = oldThr；

根据默认值创建数组

既不重复，也不是红黑树，那就是链表结构，

如果数组为空，或者数组最小容量小于64(没有进行两次扩容)

此时节点数是大于6的，

如果低位、高位的尾节点不为空

设置新数组容量

++binCount；该节点的next赋值，调用newNode()方法尾插法

resize() 初始化

如果遍历的Node对象不为null

调用treeify(tab)进行树化

e=p；会替换原来的值，返回原来的值

说明原来的红黑树已经拆成两个链表了

根据新数组的容量重新计算索引，将这个对象赋值给新数组

无参构造

清除这个位置的元素oldTab[j] = null

退化为链表，将返回的node对象添加到数组对应的位置 也就是第一次for循环的变量

先扩容没有必要转换成红黑树

do/while 循环循环条件for循环每一次遍历的node对象e.next!=null

如果插入的是一个重复的key

(e.hash & oldCap) == 0

就一个节点

将Node对象转换成TreeNode，调用 putTreeVal()

如果newThr==0

如果该位置node对象的next==null

如果是treeNode对象

需要拆分两条链表根据节点个数进行树化或者退化

第一步: 设置数组扩容后容量、阈值

如果oldCap>0

值传递将 for循环遍历的node对象 e.next赋值给扩容后声明的next

生成hash

如果高位的头结点不为空，和低位逻辑一致，只不过给数组里面添加元素的位置是原来位置加上旧数组的长度

do/while循环遍历结束

HashMap扩容机制

有参构造

for循环遍历红黑树根节点

调用

设置阈值threshold

第二步:将旧数组的元素添加到新数组

for循环结束返回新数组

(e.hash & bit) == 0

高位/低位

如果 oldThr>0

HashMap中put方法源码

如果节点个数小于等于6

按位与运算区分高位、低位

如果旧数组不为空

将头结点添加到数组对应位置

else第一个if如果插入的是一个重复的key

如果达到数组的上限

调用treeifyBin（tab，hash）树化

第一个if语句如果数组为空或者长度等于0

putVal(int hash，K key，V value )