| 失效链接处理 |
|
HashMap与ConcurrentHashMap面试要点 PDF 下载
本站整理下载：
相关截图：
主要内容：
JDK8: 数组+链表+红⿊树（看过源码的同学应该知道JDK8中即使⽤了单向链表，也使⽤了双向链表，双
向链表主要是为了链表操作⽅便，应该在插⼊，扩容，链表转红⿊树，红⿊树转链表的过程中都要操作链
表）
当元素个数⼩于⼀个阈值时，链表整体的插⼊查询效率要⾼于红⿊树，当元素个数⼤于此阈值时，链表整
体的插⼊查询效率要低于红⿊树。此阈值在HashMap中为8
这个题很容易答错，⼤部分答案就是：当链表中的元素个数⼤于8时就会把链表转化为红⿊树。但是其实还
有另外⼀个限制：当发现链表中的元素个数⼤于8之后，还会判断⼀下当前数组的⻓度，如果数组⻓度⼩于
HashMap
HashMap底层数据结构
JDK8中的HashMap为什么要使⽤红⿊树？
JDK8中的HashMap什么时候将链表转化为红⿊树？
2
64时，此时并不会转化为红⿊树，⽽是进⾏扩容。只有当链表中的元素个数⼤于8，并且数组的⻓度⼤于
等于64时才会将链表转为红⿊树。
上⾯扩容的原因是，如果数组⻓度还⽐较⼩，就先利⽤扩容来缩⼩链表的⻓度。
1. 根据key⽣成hashcode
2. 判断当前HashMap对象中的数组是否为空，如果为空则初始化该数组
3. 根据逻辑与运算，算出hashcode基于当前数组对应的数组下标i
4. 判断数组的第i个位置的元素（tab[i]）是否为空
a. 如果为空，则将key，value封装为Node对象赋值给tab[i]
b. 如果不为空：
i. 如果put⽅法传⼊进来的key等于tab[i].key，那么证明存在相同的key
ii. 如果不等于tab[i].key，则：
1. 如果tab[i]的类型是TreeNode，则表示数组的第i位置上是⼀颗红⿊树，那么将key和
value插⼊到红⿊树中，并且在插⼊之前会判断在红⿊树中是否存在相同的key
2. 如果tab[i]的类型不是TreeNode，则表示数组的第i位置上是⼀个链表，那么遍历链表寻
找是否存在相同的key，并且在遍历的过程中会对链表中的结点数进⾏计数，当遍历到最
后⼀个结点时，会将key,value封装为Node插⼊到链表的尾部，同时判断在插⼊新结点之
前的链表结点个数是不是⼤于等于8，如果是，则将链表改为红⿊树。
iii. 如果上述步骤中发现存在相同的key，则根据onlyIfAbsent标记来判断是否需要更新value值，
然后返回oldValue
5. modCount++
6. HashMap的元素个数size加1
7. 如果size⼤于扩容的阈值，则进⾏扩容
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
