HashMap的扩容机制原理
1.7 版本
- ⽣成新数组,是原来数组的2倍
- 遍历⽼数组中的每个位置上的链表上的每个元素
- 取每个元素的key,并基于新数组⻓度,计算出每个元素在新数组中的下标
- 将元素添加到新数组中去
- 所有元素转移完了之后,将新数组赋值给HashMap对象的table属性
1.8 版本
注意:
JDK1.8+在扩容时,不需要重新计算元素的hash进⾏元素迁移。
⽽是⽤原先位置key的hash值与旧数组的⻓度(oldCap)进⾏”与”操作。
- 如果结果是0,那么当前元素的桶位置不变。
- 如果结果为1,那么桶的位置就是原位置+原数组 ⻓度具体过程:
- ⽣成新数组,是原来数组的2倍
- 遍历⽼数组中的每个位置上的链表或红⿊树
- 如果是链表,则直接将链表中的每个元素重新计算下标,并添加到新数组中去
- 如果是红⿊树,则先遍历红⿊树,先计算出红⿊树中每个元素对应在新数组中的下标位置
a. 统计每个下标位置的元素个数
b. 如果该位置下的元素个数超过了8,则⽣成⼀个新的红⿊树,并将根节点的添加到新数组的对应位置
c. 如果该位置下的元素个数没有超过8,那么则⽣成⼀个链表,并将链表的头节点添加到新数组的对应位置 - 所有元素转移完了之后,将新数组赋值给HashMap对象的table属性
还没有评论,来说两句吧...