本文源码基于 JDK 1.8.0_101 。

在 JDK 1.8 之前，HashMap 采用 槽数组 + 单链表 来实现；

在 JDK 1.8 开始采用 槽数组 + 单链表 + 红黑树 来实现。

1. 为什么引入红黑树？

解决哈希冲突时、链表过长导致访问效率低下的问题。

为什么是红黑树不是其他树：
二叉排序树在极端情况下会退化成线性结构。
平衡二叉树（AVL树）是严格平衡树，在增加或删除节点时，旋转次数比红黑树要多。红黑树的统计性能高于 AVL 树。

红黑树特性，RBT树上的每个节点，都要遵循下面的规则：
① 每个节点都是红色或者黑色；
② 根节点必须始终是黑色；
③ 没有两个相邻的红色节点；
④ 对每个结点，从该结点到其子孙节点的所有路径上包含相同数目的黑结点。

2. 为什么不直接使用红黑树？

• 红黑树节点的内存占用大约是链表节点的两倍，尽量使用链表可以节约内存；
• 红黑树的维护比链表复杂很多，如果链表很短，使用红黑树对访问效率也不会有大的提升。

3. hash 算法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

该算法基于一个假设：大部分元素的哈希值在低位是相同的，通过与高位进行异或运算可以引入更多的随机性。

通过 hash & (table.length - 1) 计算出目标槽位，因为数组的长度总是 2 的幂。

4. 链表与红黑树之间的转换机制

• 当链表的长度达到 TREEIFY_THRESHOLD（默认值 8）、且槽数组的长度 大于等于 MIN_TREEIFY_CAPACITY(默认值 64) 时，扩容时把链表转换为红黑树；
• 当红黑树中的节点由于移除或 resize 减少至 UNTREEIFY_THRESHOLD(默认值 6)，变回普通链表。
  > 在理想情况下，hashCode 分布良好，链表长度符合泊松分布，各个长度的命中率依次递减，当长度为 8 时，概率小于千万分之一，通常 Map 里不会存这么多数据，也就不会发生链表到红黑树的转换。
  > UNTREEIFY_THRESHOLD 默认取 6 是因为长度适中，取 7 则会频繁地发生红黑树转化与逆转化。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果数组很小，进行扩容，而不是直接转换为红黑树
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 把节点包装成红黑树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                // 把树节点链成一个链表
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);

        if ((tab[index] = hd) != null)
            hd.treeify(tab);    // 将链表进行树化
    }
}

5. put 逻辑

1. 如果槽数组为空或长度为 0，通过 resize 方法进行初始化或扩容。
2. 通过 hash & (table.length - 1) 计算出目标槽位。
3. 如果目标槽位为空，创建结点并设置到槽位上。
4. 槽位非空，执行如下查找与 key 相同的节点：

• 4.1 如果槽上第一个节点的 key 相同，找到。
• 4.2 如果槽上第一个节点是红黑树，在红黑树上插入，返回原来的与 key 系统相同的节点。
• 4.3 槽上第一个节点是链表，遍历：如果 key 相同，中断循环，找不到则插入到链表末尾，插入后如果达到转为红黑树的阈值 TREEIFY_THRESHOLD，则尝试转换。

1. 如果找到目标节点，根据参数决定是否替换为新值，并返回旧值。
2. 元素计数加 1，如果元素数量超过 扩容的阈值，进行 resize 。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 初始化或扩容
    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;
        // 目标槽位第一个节点就是匹配的 key
        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;
                }
                // 与已有节点的key匹配，跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

6. resize 逻辑

1. 根据旧槽数组计算新的槽数组长度、扩容阈值，默认扩容为原来的两倍。
2. 创建新的数组并替换旧数组。
3. 把旧数组上的元素转移到新数据上：遍历槽数组，对非空的数组元素 e 进行如下处理：

• 3.1 如果 e.next 为空，表示只有一个节点，直接转移到新的槽位上。
• 3.2 如果 e 是红黑树，把红黑树逆转、拆分到高低两棵树，分别追加到 table[index], table[index+oldCap] 槽上。
• 3.3 如果节点是链表，把链表拆分为高低两个链表，分别追加到 table[index], table[index+oldCap] 槽上。

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 &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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;
    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
                    // 这里保持原来的顺序可以避免并发 resize 时出现死循环。
                    // 之前的版本以逆序的方式重新插入，容易出现死循环
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // j < oldCap 时 == 0，是低位的
                        // 14 & 16 == 0, 17&16=1 
                        // 把原来的单链表拆分为两个链表
                        // 哈希值小于 oldCap 的在低位链表，其他在高位链表
                        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 重新分配槽位时要保证：新的槽位与 put/get 方法使用的槽位计算逻辑生成到同一个槽位，否则元素就找不到了。

put/get 方法的槽位算法是：index = (table.length - 1) & hash 。

数组长度 n	n-1 的比特表示
8	00111
16	01111

对于hash 值 25，其二进制表示为 11001，
数组长度为 8，它的槽位是 25 & (8 - 1) == 11001 & 00111 = 1，
如果数组长度为 16，槽位是 25 & (16 - 1) = 11001 & 01111 = 9，

当数组从长度 8 扩容到 16时，它的旧槽位是 1，oldCap = 8, 25 & oldCap 不为 0，新的槽位为 旧槽位+oldCap = 1+8 = 9，与 put/get 方法算的是一样的。

当resize时，原来一个槽里的元素只会重新分配到两个槽位上去：j ， oldCap + j ，因此上面的代码维护了对两个链表的首尾引用。

7. 为什么 HashMap 的 table 数组用 transient 修饰？

1. table 多数情况下是未填满的，序列化未使用部分，浪费空间。
2. 同一个键在不同的 JVM 下算出来的哈希值可能不同，所处的槽位也就不同，在不同的 JVM 下反序列化 table 可能出错。
3. 通过实现 readObject/writeObject 来定制序列化行为。

---

欢迎关注我的微信公众号: coderbee笔记 。