HashMap的扩容机制原理

桃扇骨 2024-02-05 22:40 40阅读 0赞

1.7 版本

  1. ⽣成新数组,是原来数组的2倍
  2. 遍历⽼数组中的每个位置上的链表上的每个元素
  3. 取每个元素的key,并基于新数组⻓度,计算出每个元素在新数组中的下标
  4. 将元素添加到新数组中去
  5. 所有元素转移完了之后,将新数组赋值给HashMap对象的table属性
    在这里插入图片描述

1.8 版本
注意:
JDK1.8+在扩容时,不需要重新计算元素的hash进⾏元素迁移。
⽽是⽤原先位置key的hash值与旧数组的⻓度(oldCap)进⾏”与”操作。

  1. 如果结果是0,那么当前元素的桶位置不变。
  2. 如果结果为1,那么桶的位置就是原位置+原数组 ⻓度具体过程:
  3. ⽣成新数组,是原来数组的2倍
  4. 遍历⽼数组中的每个位置上的链表或红⿊树
  5. 如果是链表,则直接将链表中的每个元素重新计算下标,并添加到新数组中去
  6. 如果是红⿊树,则先遍历红⿊树,先计算出红⿊树中每个元素对应在新数组中的下标位置
    a. 统计每个下标位置的元素个数
    b. 如果该位置下的元素个数超过了8,则⽣成⼀个新的红⿊树,并将根节点的添加到新数组的对应位置
    c. 如果该位置下的元素个数没有超过8,那么则⽣成⼀个链表,并将链表的头节点添加到新数组的对应位置
  7. 所有元素转移完了之后,将新数组赋值给HashMap对象的table属性
    在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,40人围观)

还没有评论,来说两句吧...

相关阅读

    相关 HashMap扩容机制原理

    1.7 版本 1. ⽣成新数组,是原来数组的2倍 2. 遍历⽼数组中的每个位置上的链表上的每个元素 3. 取每个元素的key,并基于新数组⻓度,计算出每个元素在新数组中

    相关 hashmap 扩容机制

    hashmap是一种基于数组和链表(或红黑树)的数据结构,它可以存储键值对的映射关系。hashmap的扩容机制是指当hashmap中的元素个数超过数组长度乘以负载因子时,就会重

    相关 HashMap 扩容原理

    今天有个朋友问我, 为啥hashMap扩容之后 数组的位置是 当前位置 或 当前位置 + oldCap 呢? 想了一下,举个例子最清楚了 我们模拟一下就清楚了,分别用两个k