关于HashMap扩容机制

HashMap的底层有数组 + 链表(红黑树)组成数组的大小可以在构造方法时设置默认大小为16数组中每一个元素就是一个链表jdk7之前链表中的元素采用头插法插入元素jdk8之后采用尾插法插入元素由于插入的元素越来越多查找效率就变低了所以满足某种条件时链表会转换成红黑树。随着元素的增加HashMap的数组会频繁扩容如果构造时不赋予加载因子默认值那么负载因子默认值为0.75,数组扩容的情况如下:

1:当添加某个元素后数组的总的添加元素数大于了 数组长度 * 0.75(默认,也可自己设定),数组长度扩容为两倍。(如开始创建HashMap集合后数组长度为16临界值为16 * 0.75 = 12当加入元素后元素个数超过12数组长度扩容为32临界值变为24)

2在没有红黑树的条件下添加元素后数组中某个链表的长度超过了8数组会扩容为两倍.(如开始创建HashMAp集合后假设添加的元素都在一个链表中当链表中元素为8时再在链表中添加一个元素此时若数组中不存在红黑树则数组会扩容为两倍变成32假设此时链表元素排列不变再在该链表中添加一个元素数组长度再扩容两倍变为64假设此时链表元素排列还是不变则此时链表中存在10个元素这是HashMap链表元素数存在的最大值此时再加入元素满足了链表树化的两个条件(1:数组长度达到64, 2:该链表长度达到了8)该链表会转换为红黑树

HashMap创建的底层原理

1:首先创建HashMap集合时在不手动赋值的情况下会先设置默认负载因子0.75

2.向集合值添加元素会调用putVal()方法前三个参数分别为hash(key),key,value即hash值键值对。

 3.hash(key)方法计算hash值

 计算方法是键的hashCode()方法与高位16进行异或运算得到hash值

 4.进入putVal方法首先看上半部分

 首先判断数组中是否已经创建此时还创建数组所以此时调用

resize()方法设置初始容量

若未在构造方法时设置初始容量则初始容量设置为16.(注意容量只能为2的倍数即使输入的不是2的倍数也会自动转换)

将元素存储在i = (n - 1) & hash的下标链表中因为此时为加入元素所以table[i]一定是null,元素一定会存入到数组中。

 5.接着会跳过之后的判断语句

size代表了此时集合中已经加入的元素个数当其值大于了临界值

threshold(此时为12)时会调用resize()方法进行二倍扩容

6.添加完第一个元素后继续添加下一个元素因为重写了hashCode()方法让两个元素的hash值相同所以它们会存储在同一个链表中进入putVal()方法后上面的第一个if语句为false,因为已经初始化了数组第二个if也是false因为当前链表下的头元素已经存在它会进入if语句的分支else语句

 7.第一个if语句判断链表中头元素与当前插入的元素是否是同一个元素(hash()方法与equals()方法比较)

 

这里重写了hash()方法所以hash值相同但两种内容不同所以进入else分支判断当前数组中的结点是链表还是红黑树如果是红黑树就按红黑树的添加方式添加。

此时我们还未形成红黑树所以不会执行进入else语句。

8.接下来进入一个死循环死循环结束有两种方式

1.第一种结束方式:链表中没有找到与当前添加元素相同的元素(euqals()方法比较),就会用尾插法在链表末尾插入这个添加的元素然后会进行if判断判断添加元素前当前链表中元素是否达到了8如果达到了进入

treeifyBin(tab, hash)语句在该语句中我们只关注前半部分在数组容量小于64时数组会调用

resize()方法扩容为2倍

 

 2.第二种结束方式

还是在for循环中如果找到了与添加元素相同的元素(euqals()方法比较),直接跳出循环。然后进入if语句覆盖掉链表中元素的“值”(value)

 

 

 9.之后更新集合中元素的个数判断是否超过了临界值超过了就会扩容为2倍