深入理解HashMap(四): 关键源码逐行分析之resize扩容

huatibaba 2019-6-14 139

前言

上一篇我们说明了HashMap的构造函数, 谈到构造函数中并不会初始化table 变量, table 变量是在 resize过程中初始化的.

本篇我们就来聊聊HashMap的扩容: resize

本文的源码基于 jdk8 版本.

resize

resize用于以下两种情况之一

  • 初始化table
  • 在table大小超过threshold之后进行扩容

下面我们直接来对照源码分析:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 原table中已经有值
    if (oldCap > 0) {
    
        // 已经超过最大限制, 不再扩容, 直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 注意, 这里扩容是变成原来的两倍
        // 但是有一个条件: `oldCap >= DEFAULT_INITIAL_CAPACITY`
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    
    // 在构造函数一节中我们知道
    // 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
    // 如果指定了initialCapacity, 该值被初始化成大于initialCapacity的最小的2的次幂
    
    // 这里是指, 如果构造时指定了initialCapacity, 则用threshold作为table的实际大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    
    // 如果构造时没有指定initialCapacity, 则用默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 计算指定了initialCapacity情况下的新的 threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    
    //从以上操作我们知道, 初始化HashMap时, 
    //如果构造函数没有指定initialCapacity, 则table大小为16
    //如果构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
    
    
    // 从下面开始, 初始化table或者扩容, 实际上都是通过新建一个table来完成的
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 下面这段就是把原来table里面的值全部搬到新的table里面
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是清除旧表的引用, 但是真正的node节点还在, 只是现在由e指向它
                oldTab[j] = null;
                
                // 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
                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;
}

resize时的链表拆分

下面我们单独来看看这段设计的很精妙的代码

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;
}

首先我们看源码时要抓住一个大框架, 不要被它复杂的流程唬住, 我们一段一段来看:

第一段

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

上面这段定义了四个Node的引用, 从变量命名上,我们初步猜测, 这里定义了两个链表, 我们把它称为 lo链表 和 hi链表loHead 和 loTail 分别指向 lo链表的头节点和尾节点, hiHead 和 hiTail以此类推.

第二段

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);
上面这段是一个do-while循环, 我们先从中提取出主要框架:

do {
    next = e.next;
    ...
} while ((e = next) != null);

从上面的框架上来看, 就是在按顺序遍历该存储桶位置上的链表中的节点.

我们再看if-else 语句的内容:

// 插入lo链表
if (loTail == null)
    loHead = e;
else
    loTail.next = e;
loTail = e;
// 插入hi链表
if (hiTail == null)
    hiHead = e;
else
    hiTail.next = e;
hiTail = e;

上面结构类似的两段看上去就是一个将节点e插入链表的动作.

最后再加上 if 块, 则上面这段的目的就很清晰了:

我们首先准备了两个链表 lo 和 hi, 然后我们顺序遍历该存储桶上的链表的每个节点, 如果 (e.hash & oldCap) == 0, 我们就将节点放入lo链表, 否则, 放入hi链表.

第三段

第二段弄明白之后, 我们再来看第三段:

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

这一段看上去就很简单了:

如果lo链表非空, 我们就把整个lo链表放到新table的j位置上 
如果hi链表非空, 我们就把整个hi链表放到新table的j+oldCap位置上

综上我们知道, 这段代码的意义就是将原来的链表拆分成两个链表, 并将这两个链表分别放到新的table的 j 位置和 j+oldCap 上, j位置就是原链表在原table中的位置, 拆分的标准就是:

(e.hash & oldCap) == 0
为了帮助大家理解,我画了个示意图:

关于 (e.hash & oldCap) == 0 j 以及 j+oldCap

上面我们已经弄懂了链表拆分的代码, 但是这个拆分条件看上去很奇怪, 这里我们来稍微解释一下:

首先我们要明确三点:

  1. oldCap一定是2的整数次幂, 这里假设是2^m
  2. newCap是oldCap的两倍, 则会是2^(m+1)
  3. hash对数组大小取模(n - 1) & hash 其实就是取hash的低m

例如: 
我们假设 oldCap = 16, 即 2^4, 
16 - 1 = 15, 二进制表示为 0000 0000 0000 0000 0000 0000 0000 1111 
可见除了低4位, 其他位置都是0(简洁起见,高位的0后面就不写了), 则 (16-1) & hash 自然就是取hash值的低4位,我们假设它为 abcd.

以此类推, 当我们将oldCap扩大两倍后, 新的index的位置就变成了 (32-1) & hash, 其实就是取 hash值的低5位. 那么对于同一个Node, 低5位的值无外乎下面两种情况:

0abcd
1abcd

其中, 0abcd与原来的index值一致, 而1abcd = 0abcd + 10000 = 0abcd + oldCap

故虽然数组大小扩大了一倍,但是同一个key在新旧table中对应的index却存在一定联系: 要么一致,要么相差一个 oldCap

而新旧index是否一致就体现在hash值的第4位(我们把最低为称作第0位), 怎么拿到这一位的值呢, 只要:

hash & 0000 0000 0000 0000 0000 0000 0001 0000

上式就等效于

hash & oldCap

故得出结论:

如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j 
如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap

根据这个条件, 我们将原位置的链表拆分成两个链表, 然后一次性将整个链表放到新的Table对应的位置上.

怎么样? 这个设计是不是很巧妙, 反正LZ是无比佩服源码作者的!

总结

  1. resize发生在table初始化, 或者table中的节点数超过threshold值的时候, threshold的值一般为负载因子乘以容量大小.
  2. 每次扩容都会新建一个table, 新建的table的大小为原大小的2倍.
  3. 扩容时,会将原table中的节点re-hash到新的table中, 但节点在新旧table中的位置存在一定联系: 要么下标相同, 要么相差一个oldCap(原table的大小).
原文连接 https://segmentfault.com/a/1190000015812438
最新回复 (0)
返回
发新帖