HashMap的resize()方法注释

小灰灰 2022-12-04 01:08 168阅读 0赞

/** * 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 */
        final Node<K,V>[] resize() { 
            Node<K,V>[] oldTab = table;		// 原数据数组
            int oldCap = (oldTab == null) ? 0 : oldTab.length;  // 原容量，如果原表为空则原容量为0，否则就是它的长度
            int oldThr = threshold;	// 原扩容阈值，初始化为当前扩容阈值
            int newCap, newThr = 0;	// 新容量、新扩容阈值均初始化为0
            if (oldCap > 0) { 	// 如果原扩容阈值大于0，说明原map不是空的
                if (oldCap >= MAXIMUM_CAPACITY) { 	// 如果原容量大于等于最大容量（1<<30）
                    threshold = Integer.MAX_VALUE;	// 当前扩容阈值就等于int类型的最大值
                    return oldTab;	// 由于原来的容量已经很大了，无法进行重新分布，只是单纯的将阈值扩容到最大，返回原数据表
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)	// 如果原容纳量乘以2后小于最大容量（1<<30）且原容量大于等于默认初始化容量（16），那么新容量为原容量的两倍
                    newThr = oldThr << 1; // 新扩容阈值也为原扩容阈值的两倍
            }
            else if (oldThr > 0)	// 如果原扩容阈值大于0
                newCap = oldThr;	// 新容量等于原扩容阈值
            else { 
                newCap = DEFAULT_INITIAL_CAPACITY;	// 新容量等于默认容量（16）
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);	// 新扩容阈值等于默认扩容因子*默认容量 （0.75*16=12）
            }
            if (newThr == 0) { 	 // 如果新扩容阈值等于0
                float ft = (float)newCap * loadFactor;	// 新扩容阈值等于新容量与负载因子的乘积
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);	// 不能太大，太大了只能取上限Integer.MAX_VALUE
            }
            threshold = newThr;	// 扩容阈值等于新扩容阈值
    		// 扩容完成之后需要将原来的表中元素进行重新定位，这就是费时的操作，所以设置容量时最好不要频繁触发resize操作
    		// 以下是节点移动，有兴趣的慢慢看
            @SuppressWarnings({ "rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];	// 根据新的容量构建一个Node数组
            table = newTab;	
            if (oldTab != null) { // 如果原数组不是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;	// 根据元素的哈希值与新容量-1做与运算后得到该元素的位置
                        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 { 	// 链表一个一个链起来就OK
                                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;
        }