回味集合(十一)HashMap中的resize()方法

简介

说起HashMap想必大家都不陌生，在平时开发时应对有映射关系的数据时就会使用HashMap来保存数据之间的关系，通过key获取对应的value，在我们向HashMap中不停put时，有没有想过HashMap是如何存在数据的呢？如何解决哈希冲突的呢，当链表过长时如何解决的呢？带着这些问题我们一起学习HashMap吧，下面是HashMap用于扩容的方法我们一起来看看吧。

源码

// 当哈希表中已经存在数据时，再向hashmap中put数据时，哈希表已经达到扩容的要求(哈希表长度>哈希表长度*负载因子)时就会调用reszie方法
  final Node<K,V>[] resize() {
   
        // 将以存在的哈希数组赋值给oldTab记做老的哈希表
        Node<K,V>[] oldTab = table;
        // 获取之前数组的长度赋值给oldCap
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 获取指定的扩容阙值
        int oldThr = threshold;
        // 定义newCap(新长度),newThr(新阙值)默认为0
        int newCap, newThr = 0;
        // 判断之前的长度是否大于0
        if (oldCap > 0) {
   
             // 判断之前长度是否大于最大值等于1<<30
            if (oldCap >= MAXIMUM_CAPACITY) {
   
                // 大于则扩容阙值为Interger的最大值
                threshold = Integer.MAX_VALUE;
                // 返回旧的哈希数组
                return oldTab;
            }
            // 旧的长度左移一位1赋值给newCap 判断是否小于最大值并且旧的长度大于等于默认初始值16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     // 新的阙值为旧的长度左移1
                newThr = oldThr << 1; // double threshold
        }
        // 旧的长度大于0
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 新的长度等于旧的长度
            newCap = oldThr;
        else {
                  // zero initial threshold signifies using defaults
            // 新的长度等初始值16
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 新的阙值为初始值16*负载因子0.75
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果新的长度等于0
        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数组长度为newCap
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            // 将新的数组赋值给table
        table = newTab;
        // 如果就的数组不为null
        if (oldTab != null) {
   
           // 遍历就的数组
            for (int j = 0; j < oldCap; ++j) {
   
               // 定义一个局部变量e
                Node<K,V> e;
                 // 将旧的数组中每个结点赋值给e并不为null时
                if ((e = oldTab[j]) != null) {
   
                    // 将J对应的结点赋值为null
                    oldTab[j] = null;
                    // 判断当前结点是否存在链表，如果为null
                    if (e.next == null)
                        // 通过在newTab中计算哈希值找到对应的位置将e赋值到当前位置
                        newTab[e.hash & (newCap - 1)] = e;
                    // 当前结点是否是红黑树 
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 当前结点上存在链表时 
                    else {
    // preserve order
                        // 定义局部变量结点 loHead(低结点头) loTail(低结点尾)
                        Node<K,V> loHead = null, loTail = null;
                        // 定义局部变量结点 hiHead(高结点头) hiTail(高结点尾)
                        Node<K,V> hiHead = null, hiTail = null;
                        // 定义局部变量next 记录下一个结点
                        Node<K,V> next;
                        do {
   
                            // 获取当前结点的下一个节点，赋值给next
                            next = e.next;
                            // 结点e计算hash值与旧的哈希数组长度做与运算判断是否等于0
                            // (e.hash & oldCap)其结果要么是旧数组的长度要么就是0
                            if ((e.hash & oldCap) == 0) {
   
                            // 如果低位尾指针为空时
                                if (loTail == null)
                                    //低位头指针指向结点e 
                                    loHead = e;
                                else
                                    // 否则 低位尾指针的下一个结点指向结点e
                                    loTail.next = e;
                                    
                                loTail = e;
                            }
                            else {
   
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 如果低位尾指针不为null
                        if (loTail != null) {
   
                           // 那么低位尾指针下一个指向null
                            loTail.next = null;
                            // 低位头指针指向结点放入新数组中的位置和旧数组中的位置相同
                            newTab[j] = loHead;
                        }
                        // 如果高位尾指针不为null
                        if (hiTail != null) {
   
                           // 那么高位尾指针下一个指向null
                            hiTail.next = null;
                            // 高位头指针指向结点放入新数组中的位置是旧数组中的位置相同再加上旧数组的总长度
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        // 返回新的哈希表
        return newTab;
    }

HashMap扩容时的rehash方法中的(e.hash & oldCap)== 0算法推导

图解最后几步

会将链表阶段分布在数组各个位置