Java8 中的 HashMap

Posted on | Edited on | In

JDK1.8 中对HashMap底层进行了改造，例如扩容重散列算法优化、加入链表过长转红黑树结构等。
鉴于日常搬砖靠HashMap打天下，面试题基本跑不了，全面认知散列表必不可少。

结构

散列表的实现方法有两种：

  • 开放地址法(Hashing with linear probing)
    20200930161943
  • 链接地址法(Hashing with separate chaining)
    20200930161836

HashMap用的是链地址法，简单的说就是数组+链表，数组作为桶位索引，链表作为桶。
每个键值对，通过计算Key的Hash值确定索引，再通过对比放入数组下标位引用的链表。

其中JDK1.8新增了红黑树数据结构，在链表过长时，把链表转为树形结构。
如图：”AN EASY QUESTION”
RedBlackTree

在深入前，需要理解HashMap的几个重要属性
HashMap

  • loadFactor 负载因子，触发容量伸缩的比例。ps.可以超载大于1。
  • threshold 所能容纳的key-value对极限，是当前索引容量下的最大阈值。
  • modCount 记录内部结构发生变化的次数，主要用于迭代的快速失败。
  • size 实际存在的键值对数量。

散列

散列表是时空权衡的经典例子。
设想如果存在无限的空间，存在神奇的散列算法可以将键值对完美分配，可以预计搜索的效率将是最高的O(1)。

事实是现实世界没有无限资源，也没有魔法般的散列算法，只能在索引空间、搜索时间之间做权衡。

索引空间有限的情况下，数据在桶位里堆叠，这被称为Hash碰撞。
如何在有限的空间下减少Hash碰撞，答案是好的Hash算法和扩容机制。

HashMap的空间伸缩，大小必须是2的n次方（合数）,这并不是常规的做法，通常是会把桶位的大小设计成素数。素数计算索引的碰撞概率比合数小，具体证明可参考为什么一般hashtable的桶数会取一个素数。简单的说，就是合数的二进制中会出现不参与计算的0，这样Hash算法无法完整地反映Key的特性，键的粒度会在合数0的位置富集。

第一步定位到桶位：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static final int hash(Object key) {
    int h;
    // 1. 取对象hashCode
    // 2. 高位参与异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 1.7
static int indexFor(int h, int length) {
    // 3. 取模
    return h & (length-1);
}

// 1.8
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 3. 取模
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
          ...
    }
    return null;
}

由于length总是2的n次方(除初始值以外)， h & (length - 1) 等价于取模运算。
长度乘方时32比特向左移动，减1后末尾大多为1，“与”运算后即是h对lenght的模。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现：

1
(h = k.hashCode()) ^ (h >>> 16)

这主要是处于速度、功效、质量考虑，对短长度时的散列比较友好。
可以预想，有更友好的叠加方式，将更多的高位叠加至低位，但计算的消耗估计也会增加。

put方法

  1. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
  2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
  3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
  4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
  5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
  6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ...
        // 步骤③：节点key存在，直接覆盖value
        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);
                    // 链表长度大于8转换为红黑树进行处理
                    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;
            }
        }
        ...
}

扩容

扩容就是重新设置容量，无法装入更多元素时，需要扩展索引数组长度。

1.8因为有红黑树的resize逻辑比较复杂，这里以1.7为例便于理解，本质上差别不大

1
2
3
4
5
6
7
8
9
10
11
12
void resize(int newCapacity) {
     Entry[] oldTable = table;                    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;         
     if (oldCapacity == MAXIMUM_CAPACITY) {       //扩容前的数组大小如果已经达到最大(2^30)了
         threshold = Integer.MAX_VALUE;           //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
         return;
     }
     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
     transfer(newTable);                         //！！将数据转移到新的Entry数组里
     table = newTable;                           //HashMap的table属性引用新的Entry数组
     threshold = (int)(newCapacity * loadFactor);//修改阈值
}

基本逻辑就是用容量更大的数组来代替原数组，transfer方法将元素拷贝至新数组。

1.8的优化

JDK1.8的优化点在于充分利用了2倍扩容机制，让拷贝过程不需要重算HashCode：

4d8022db

  • 图（a）表示扩容前key1和key2两种key确定索引位置的示例
  • 图（b）表示扩容后key1和key2两种key确定索引位置的示例

3cc9813a

  • 假设在扩容前有随机的 Key1、Key2 键在同一桶位，有相同散列码
  • 在扩容后长度的比特向左移了一位，意味着最高位有变动
  • 由于Key1 Key2 随机，在当前length最高位上的比特也随机出现0或1
  • 只需要做”与”运算就能将键区分开，将变动的Key拷贝向扩展出的另一半。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    ...
    @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
                    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;
                        }
                        // 原索引 + oldCap
                        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并不是线程安全的类，在多线程场景下直接使用有可能会造成死循环。
1.7 版本下大致的形成死循环的逻辑如下：

  1. 线程A、线程B均在做放入键值对操作
  2. 正好碰到数组需要扩容的情形
  3. 由于1.7版本中，链表resize后会被倒排，先执行的线程会将数组引用指向曾经的链尾。
  4. 假设A先resize，已将链表排好。
  5. 正好这时B开始resize，它所认为的链头已经变成了链尾，排好后将形成环形结构。

1.8 版本同样可能死循环，但由于改了倒排，出现问题的点不同。
1.8 版本在链表转红黑树的步骤上，多线程环境下可能会出现死循环。

均匀Benchmark

377effbf
通过观测测试结果可知，JDK1.8的性能要高于JDK1.7 15%以上，在某些size的区域上，甚至高于100%。
由于Hash算法较均匀，JDK1.8引入的红黑树效果不明显，下面我们看看Hash不均匀的的情况。

极不均匀Benchmark

bd20c215
从表中结果中可知，随着size的变大，JDK1.7的花费时间是增长的趋势，而JDK1.8是明显的降低趋势，并且呈现对数增长稳定。
当一个链表太长的时候，HashMap会动态的将它替换成一个红黑树，这话的话会将时间复杂度从O(n)降为O(logn)。
hash算法均匀和不均匀所花费的时间明显也不相同，这两种情况的相对比较，可以说明一个好的hash算法的重要性。

总结

  1. 扩容是一个特别耗性能的操作，尽量避免map进行频繁的扩容。
  2. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
  3. HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，ConcurrentHashMap不香吗？
  4. JDK1.8引入红黑树大程度优化了HashMap的性能。

Java 8系列之重新认识HashMap
HashMap多线程死循环问题
踩坑了，JDK8中HashMap依然会死循环！