注:行尾注释是为了方便调试jdk源码

resize源码注释

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */

上述的未知语言翻译成人话

首先,如果当前的哈希表 table 为 null,表示哈希表尚未进行初始化,需要根据 threshold 字段中的初始容量目标分配空间,这个初始容量目标决定了哈希表的初始大小。
否则,如果哈希表 table 已经存在,表示需要对哈希表进行扩容。由于HashMap使用的是2的幂次扩容,每个哈希桶中的元素要么保持在相同的索引位置,要么以2的幂次偏移移动到新的哈希表中。(英语渣渣,只能翻译成这样了!)


流程简述

[图片链接](https://www.west999.com/info/upload/20200430/vdddikmcwiu.png)

流程:进行一些边界判断之后,创建新tab,遍历原tab,逐个节点判断类型(普通节点,链表,红黑树,)进行放入
图片链接

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 &&  // 边界判断:原数组长度大于等于初始化长度16,并且原数组长度扩大1倍也小于2^30次方
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold  // 阈值扩大一倍
    }
    else if (oldThr > 0) // initial capacity was placed in threshold  旧阈值大于0
        newCap = oldThr;  // 旧阈值大于0,则直接将新容量=旧阈值
    else {               // zero initial threshold signifies using defaults  旧阈值等于0
        newCap = DEFAULT_INITIAL_CAPACITY;                                // 说明没有进行初始化 , 将新容量赋值为初始化容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);   // 新阈值 = 16* 加载因子
    }
    if (newThr == 0) {           // 新阈值 = 0
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);                                 // 边界值判断,正常情况下newThr = newCap * 加载因子
    }
    threshold = newThr;                         // 新阈值来啦
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];   // 创建新的table
    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; //loHead:下标不变情况下的链表头  loTail:下标不变情况下的链表尾  /*这个下标是指hash索引.*/
                    Node<K,V> hiHead = null, hiTail = null; //hiHead:下标改变情况下的链表头  hiTail:下标改变情况下的链表尾
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // 由于1.8采用的是原来两倍的扩容策略,所以不需要像1.7那样重新计算hash,扩容后的元素不是在原来的位置,就是在原来的位置的2次幂位置,所以只需要看hash新增的bite 是1还是0
                            if (loTail == null)       // 是bite是0,在原来位置。
                                loHead = e;           // 1.8按顺序添加,不是1.7头添加。
                            else
                                loTail.next = e;
                            loTail = e;               // 链表尾索引移到e
                        }
                        else {                        // bite是1,索引变成原索引+oldCap
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;           // hash索引不变的情况下,将后来的链表头放到新数组的原容量索引位置, 挂上去
                    }
                    if (hiTail != null) {             // tail->null
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;  // hash索引改变情况下,在新数组中的索引位置变为 /*原索引位置 + 原容量*/
                    }
                }
            }
        }
    }
    return newTab;
}
分类: java

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26860 人次

浙公网安备33011302000604

辽ICP备20003309号