HashMap

本文源码基于 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时,原来一个槽里的元素只会重新分配到两个槽位上去:joldCap + j ,因此上面的代码维护了对两个链表的首尾引用。

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

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据