HashMap扩容原理

简介: HashMap扩容原理

扩容原理

HashMap的扩容方法resize()高达70行代码,可谓是相当多了,很多初次接触的同学面对这么多代码可能会直接劝退,但如果静下心来梳理的话,其实也就两部分:

  • 确定扩容后的新容量和下次扩容的阈值,并根据新容量创建一个新数组。
  • 将原数组中的数据放在新数组中

现在我们根据梳理出来的两部分,看一下完整的源码:

final Node<K,V>[] resize() {
   
   
    // 确定扩容后的新容量和下次扩容的阈值
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
   
   
        if (oldCap >= MAXIMUM_CAPACITY) {
   
   
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
   
                  // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
   
   
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({
   
   "rawtypes","unchecked"})
    //根据新容量创建一个新数组。
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];


    // 将原数组中的数据放在新数组中
    table = newTab;
    if (oldTab != null) {
   
   
        for (int j = 0; j < oldCap; ++j) {
   
   
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
   
   
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
   
    // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
   
   
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
   
   
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
   
   
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
   
   
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
   
   
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

下面我们以梳理出来的两部分内容,来看一下其中的细节

1、确认新的容量和阈值

我们把这一部分源码再次贴出来具体分析一下其中的细节

    // 确定扩容后的新容量和下次扩容的阈值
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
   
   
        if (oldCap >= MAXIMUM_CAPACITY) {
   
   
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
   
                  // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
   
   
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({
   
   "rawtypes","unchecked"})
    //根据新容量创建一个新数组。
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  • 首先,获取原数组的容量oldCap,即原数组的长度。

    由于HashMap对底层结构采用延迟初始化的策略,就是说实例化HashMap对象时,其实并没有立即对底层结构实例化,底层数组依然为空,因此当我们首次像该HashMap对象中put数据时,才会通过扩容来创建底层数组的实例。而当底层数组为空时,就认为数组长度为0即可。

    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    
  • 获取原阈值,即threshold

    我们在聊构造方法时,如果我们指定了数组的初始容量,HashMap使用tableSizeFor()方法重新确定容量时,将确定的容量赋值给阈值threshold了,如下所示:

    public HashMap(int initialCapacity, float loadFactor) {
         
         
        // ......
        this.threshold = tableSizeFor(initialCapacity);
    }
    

    因此,阈值threshold可能表示其本省的含义此时为0,也可能暂时表示底层数组长度。

  • 确定新数组的长度newCap下次扩容时的阈值threshold

        if (oldCap > 0) {
         
         
            if (oldCap >= MAXIMUM_CAPACITY) {
         
         
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {
         
                        // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    
        if (newThr == 0) {
         
         
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    
    • 如果原数组容量大于0,说明原数组已经初始化了,相应的阈值也已经设置过了。

      此时只需要将原数组容量 2作为新数组容量,原阈值 2作为新阈值。

    • 如果原数组容量为0,说明原数组还没有初始化,这种情况针对的是两个参数的构造方法。

      这时如果原阈值大于0,说明该原阈值目前只是暂时表示数组长度,就回到了上面的问题了,只需要将该原阈值作为新数组容量就可以了。然后再根据 数组容量 * 加载因子loadFactor的值 作为 新的阈值即可。

    • 如果原数组容量为0,原阈值也为0,这种情况针对的是无参构造方法。

      这是只需要将新数组容量设置为默认的初始容量,新阈值设置为默认的初始容量与加载因子的乘积即可。

    扩容新数组.png

2、将原数组中的数据放在新数组中

同样,我们也把这一部分源码再次贴出来具体分析一下其中的细节,看起来很复杂吧,别慌。

其中判断节点位于原数组和新数组中的下标是否变化,下一节会详细介绍

    Node<K,V>[] oldTab = table;
    table = newTab;
    if (oldTab != null) {
   
   
        // 遍历原数组
        for (int j = 0; j < oldCap; ++j) {
   
   
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
   
   
                // 获取原数组中下标为j的节点e
                // 并将原数组中下标为j的节点设置为空
                oldTab[j] = null;
                if (e.next == null)
                    // 如果节点e没有后置节点,即表示该位置不存在链表或红黑树
                    // 通过节点e的hash值与新数组的容量计算出节点e在新数组中的下标
                    // 并将e放在该下标处
                    // 以下代码处理该位置仅有一个节点的情况
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 节点e为TreeNode对象,即表示该位置存在以节点e为根的红黑树
                    // 以下代码处理红黑树情况
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
   
    // preserve order
                    // 节点e既有后置节点,又不是TreeNode对象,即表示该位置存在以节点e为头节点的链表
                    // 以下代码处理链表情况

                    // loHead表示从原数组移动至新数组的过程中下标不变的链表的头节点
                    // loTail表示从原数组移动至新数组的过程中下标不变的链表的尾节点
                    // 简单点说,以loHead为头节点的链表在原数组与新数组的下标相同,loTail是该链表的尾节点
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead表示从原数组移动至新数组的过程中下标变化的链表的头节点
                    // hiTail表示从原数组移动至新数组的过程中下标变化的链表的尾节点
                    // 简单点说,以hiHead为头节点的链表在原数组与新数组的下标不同,hiTail是该链表的尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
   
   
                        // 遍历以节点e为头节点的链表
                        next = e.next;
                        // 如果下标不变,则为true
                        if ((e.hash & oldCap) == 0) {
   
   
                            // 通过尾插法,将原链表以原本的节点顺序逐个插入到新链表中。
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
   
   
                            // 下标变化
                            // 通过尾插法,将原链表以原本的节点顺序逐个插入到新链表中。
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
   
   
                        // 下标不变的情况,将链表放在数组中
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
   
   
                        // 下标变化的情况,将链表放在数组中
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }

3、扩容时对红黑树的处理

上面代码中直接处理单节点和链表这两种情况,而当遇到红黑树时调用split()方法单独处理,该方法由HashMap内部类TreeNode提供。

注意:虽然当前处理的是红黑树,但是别忘了TreeNode中依然存在一个next属性,也就是说,当我们以leftright遍历时,它是红黑树;当我们以next遍历时,它是链表。这对下面的方法实现很重要。

下面我们看一下此方法如何实现

// map - hashMap对象
// tab - hashMap对象中的新数组
// index - 红黑树根节点位于hashMap对象中原数组的下标
// bit - hashMap对象中原数组的长度
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
   
   
    // 红黑树的根节点
    TreeNode<K,V> b = this;
    // 下面四个对象的含义与上面遇到的相同
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    // lc和hc都表示当前红黑树中节点数量,它两个的区别与上面四个对象的区别一样
    int lc = 0, hc = 0;

    // 通过next,将红黑树以链表的形式遍历,并记录红黑树中的节点数量
    // 遍历结果,获得以loHead为头结点、以loTail为尾节点的链表,或以hiHead为头结点、以hiTail为尾结点的链表
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
   
   
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
   
   
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
   
   
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    // 下面两个if块代码逻辑相同,分别处理位于数组的下标不变和变化两种情况。只会处理一个,
    // 并且根据红黑树中节点数量是否小于UNTREEIFY_THRESHOLD,来判断是否将红黑树退化为链表
    if (loHead != null) {
   
   
        if (lc <= UNTREEIFY_THRESHOLD)
            // 将红黑树退化为链表,因为当前已经将红黑树遍历成链表了
            // 因此只需要将各个节点从treeNode对象转为Node对象即可
            tab[index] = loHead.untreeify(map);
        else {
   
   
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                // 将遍历出的链表再转为红黑树
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
   
   
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
   
   
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

如何将链表转为红黑树,其实它的原理与HashMap的关系不大了,可以参考一下我们之前的文章红黑树

4、通过图例理解扩容细节

现在我们通过图片好好分析一下扩容原理,以下图为例,对其进行扩容,其实按照扩容阈值threshold = capcity * 0.75早就应该扩容了,这里只是为了演示。

扩容新数组.png

  • 首先遍历到原数组的下标为0的节点W,发现该位置存在链表,如下图所示

    扩容 - 遍历第一个.png

  • 遍历到原数组的下标为1的节点X,发现该位置仅有一个节点X,不存在链表和红黑树,如下图所示

    扩容 - 遍历第二个.png

  • 遍历到原数组的下标为3的节点X,发现该位置存在链表,如下图所示

    扩容 - 遍历第三个.png

  • 遍历到原数组的下标为7的节点Z,发现该位置存在红黑树,如下图所示

    扩容 - 遍历第四个.png

5、如何判断出下标是否变化

在源码中,我们看到,节点位于原数组与新数组的下标是否相同,可以通过(e.hash & oldCap) == 0来判断,

例如我们有一个原数组oldTab.length = 8,一个新数组newTab.length = 16。在原数组中有两个节点A和B,且A.hash=9B.hash=3

如下图所示

扩容 - 判断节点下标是否变化.png





以上就是HashMap的扩容原理啦,我们下期再见。

相关文章
|
2月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
57 5
|
2月前
|
算法 索引
让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)
`HashMap`的`resize()`方法主要用于数组扩容,包括初始化或加倍数组容量。该方法首先计算新的数组容量和扩容阈值,然后创建新数组。接着,旧数组中的数据根据`(e.hash & oldCap)`是否等于0被重新分配到新数组中,分为低位区和高位区两个链表,确保数据迁移时的正确性和高效性。
66 3
|
2月前
|
算法 索引
HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导
HashMap在扩容时,会创建一个新数组,并将旧数组中的数据迁移过去。通过(e.hash & oldCap)是否等于0,数据被巧妙地分为两类:一类保持原有索引位置,另一类索引位置增加旧数组长度。此过程确保了数据均匀分布,提高了查询效率。
39 2
|
2月前
|
机器学习/深度学习 算法
让星星⭐月亮告诉你,HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)
`HashMap` 的 `tableSizeFor(int cap)` 方法用于计算一个大于或等于给定容量 `cap` 的最小的 2 的幂次方值。该方法通过一系列的无符号右移和按位或运算,逐步将二进制数的高位全部置为 1,最后加 1 得到所需的 2 的幂次方值。具体步骤包括: 1. 将 `cap` 减 1,确保已经是 2 的幂次方的值直接返回。 2. 通过多次无符号右移和按位或运算,将最高位 1 后面的所有位都置为 1。 3. 最终加 1,确保返回值为 2 的幂次方。 该方法保证了 `HashMap` 的数组容量始终是 2 的幂次方,从而优化了哈希表的性能。
33 1
|
3月前
|
设计模式 安全 Java
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
假如有T1、T2两个线程同时对某链表扩容,他们都标记头结点和第二个结点,此时T2阻塞,T1执行完扩容后链表结点顺序反过来,此时T2恢复运行再进行翻转就会产生环形链表,即B.next=A;采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。JDK8中,HashMap采用尾插法,扩容时链表节点位置不会翻转,解决了扩容死循环问题,但是性能差了一点,因为要遍历链表再查到尾部。例如15(即2^4-1)的二进制为1111,31的二进制为11111,63的二进制为111111,127的二进制为1111111。
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
|
7月前
|
存储 安全 算法
【JAVA】HashMap扩容性能影响及优化策略
【JAVA】HashMap扩容性能影响及优化策略
|
6月前
|
存储 安全 Java
深入解析Java HashMap的高性能扩容机制与树化优化
深入解析Java HashMap的高性能扩容机制与树化优化
152 1
|
6月前
|
索引
HashMap扩容为什么每次都是之前的2倍
HashMap扩容为什么每次都是之前的2倍
93 0
|
7月前
|
Java 索引
HashMap的扩容看这一篇足够
HashMap的扩容看这一篇足够
82 2
|
7月前
HashMap和ArrayList初始大小和扩容后的大小
HashMap和ArrayList初始大小和扩容后的大小