Map大家族的那点事儿(4) ：HashMap – 动态扩容与添加元素

动态扩容

散列表以数组的形式组织bucket，问题在于数组是静态分配的，为了保证查找的性能，需要在Entry数量大于一个临界值时进行扩容，否则就算散列函数的效果再好，也难免产生碰撞。

所谓扩容，其实就是用一个容量更大（在原容量上乘以二）的数组来替换掉当前的数组，这个过程需要把旧数组中的数据重新hash到新数组，所以扩容也能在一定程度上减缓碰撞。

HashMap通过负载因子（Load Factor）乘以buckets数组的长度来计算出临界值，算法： threshold = load_factor * capacity 。比如，HashMap的默认初始容量为16（ capacity = 16 ），默认负载因子为0.75（ load_factor = 0.75 ），那么临界值就为 threshold = 0.75 * 16 = 12 ，只要Entry的数量大于12，就会触发扩容操作。

还可以通过下列的构造函数来自定义负载因子，负载因子越小查找的性能就会越高，但同时额外占用的内存就会越多，如果没有特殊需要不建议修改默认值。

/**
 * 可以发现构造函数中根本就没初始化buckets数组。
 * （之前说过buckets数组会推迟到第一次调用put()时进行初始化）
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // tableSizeFor()确保initialCapacity必须为一个2的N次方
    this.threshold = tableSizeFor(initialCapacity);
}

buckets数组的大小约束对于整个HashMap都至关重要，为了防止传入一个不是2次幂的整数，必须要有所防范。 tableSizeFor() 函数会尝试修正一个整数，并转换为离该整数最近的2次幂。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

还记得数组索引的计算方法吗？ index = (table.length - 1) & hash ，这其实是一种优化手段，由于数组的大小永远是一个2次幂，在扩容之后，一个元素的新索引要么是在原位置，要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算，之前提到过&运算只会关注n – 1（n = 数组长度）的有效位，当扩容之后，n的有效位相比之前会多增加一位（n会变成之前的二倍，所以确保数组长度永远是2次幂很重要），然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置，如果是0，那么索引没有发生变化，如果是1，索引就为原索引加上扩容前的容量。

这样在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开。下面是 resize() 的源码：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // table就是buckets数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // oldCap大于0，进行扩容，设置阈值与新的容量
    if (oldCap > 0) {
        // 超过最大值不会进行扩容，并且把阈值设置成Interger.MAX_VALUE
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值，扩容为原来的2倍
        // 向左移1位等价于乘2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap = 0，oldThr大于0，那么就把阈值做为新容量以进行初始化
    // 这种情况发生在用户调用了带有参数的构造函数（会对threshold进行初始化）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // oldCap与oldThr都为0，这种情况发生在用户调用了无参构造函数
    // 采用默认值进行初始化
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果newThr还没有被赋值，那么就根据newCap计算出阈值
    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;
    // 如果oldTab != null，代表这是扩容操作
    // 需要将扩容前的数组数据迁移到新数组
    if (oldTab != null) {
        // 遍历oldTab的每一个bucket，然后移动到newTab
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 索引j的bucket只有一个Entry（未发生过碰撞）
                // 直接移动到newTab
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是一个树节点（代表已经转换成红黑树了）
                // 那么就将这个节点拆分为lower和upper两棵树
                // 首先会对这个节点进行遍历
                // 只要当前节点的hash & oldCap == 0就链接到lower树
                // 注意这里是与oldCap进行与运算，而不是oldCap - 1(n - 1)
                // oldCap就是扩容后新增有效位的掩码
                // 比如oldCap=16，二进制10000，n-1 = 1111，扩容后的n-1 = 11111
                // 只要hash & oldCap == 0，就代表hash的新增有效位为0
                // 否则就链接到upper树（新增有效位为1）
                // lower会被放入newTab[原索引j]，upper树会被放到newTab[原索引j + oldCap]
                // 如果lower或者upper树的节点少于阈值，会被退化成链表
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 下面操作的逻辑与分裂树节点基本一致
                    // 只不过split()操作的是TreeNode
                    // 而且会将两条TreeNode链表组织成红黑树
                    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;
}

使用HashMap时还需要注意一点，它不会动态地进行缩容，也就是说，你不应该保留一个已经删除过大量Entry的HashMap（如果不打算继续添加元素的话），此时它的buckets数组经过多次扩容已经变得非常大了，这会占用非常多的无用内存，这样做的好处是不用多次对数组进行扩容或缩容操作。不过一般也不会出现这种情况，如果遇见了，请毫不犹豫地丢掉它，或者把数据转移到一个新的HashMap。

添加元素

我们已经了解了HashMap的内部实现与工作原理，它在内部维护了一个数组，每一个key都会经过散列函数得出在数组的索引，如果两个key的索引相同，那么就使用分离链接法解决碰撞冲突，当Entry的数量大于临界值时，对数组进行扩容。

接下来以一个添加元素（ put() ）的过程为例来梳理一下知识，下图是 put() 函数的流程图：

然后是源码：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table == null or table.length == 0
    // 第一次调用put()，初始化table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 没有发生碰撞，直接放入到数组
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 发生碰撞（头节点就是目标节点）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 节点为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 节点为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 未找到目标节点，在链表尾部链接新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表过长，转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到目标节点，退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 节点已存在，替换value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // afterNodeXXXXX是提供给LinkedHashMap重写的函数
            // 在HashMap中没有意义
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过临界值，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}