阅读笔记:HashMap

HashMap可以算是最常用的数据结构了,而它的实现没想到还挺有学问在里面。

基本实现

哈希映射

在HashMap中使用数组来存储元素,根据元素的hash值一一映射到一个节点上。其中使用的哈希方法为:

static final int hash(Object key) {
    int h;
    // 将哈希值无符号右移16位是因为取index使用了length作为掩码,这样当哈希值在掩码外的部分相同的时候就会发生冲突
    // 这样将高位混杂到低位上,可以尽可能将这种影响消除
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

举例来说对于容量为4的HashMap,插入"a"、"b"、"c"、"d"后在数组中的分布就是:

"a".hashCode() = 97 = 00000000000000000000000001100001
hash("a") = 00000000000000000000000001100001 ^ 00000000000000000000000000000000
          = 00000000000000000000000001100001
index = hash("a") & (4 - 1)
      = 00000000000000000000000001100001 & 00000000000000000000000000000011
      = 00000000000000000000000000000001

如此则数组中对应的序号为1,2,3,0。

HashMap resize

Load Factor(负载因子)和Threshod(阈值)

因为HashMap的底层实际上是使用数组进行存储,那么始终存在着一个动态内存分配的问题:数组的大小是固定的,但是HashMap实际存储多少数据是未知的(可以一直向HashMap中进行插入),那么当数组塞满了(实际上还有一个问题是发生哈希冲突)之后如何处理?

解决这个问题最简单的做法就是,一旦数组满了之后,就对数组进行扩容。扩容也很简单,重新申请一个大一点的数组,再把原来数组里面的数据复制过去即可。这里涉及到另外一个问题就是,扩容的时候选择一个怎么样的容量进行扩容呢?这个操作是有代价的,如果频繁的扩容就涉及到频繁的数组复制操作,性能上会受到影响;如果一次扩容选择一个很大的空间,但实际之后这些空间又没有使用到,那么久造成了资源浪费。怎么解决这一个问题呢?

在HashMap的构造中有两个关键的参数:

  • initialCapacity:初始化容量,即可以装多少条数据
  • loadFactor:负载因子,用来描述HashMap中可以变得多“满”(到达什么程度开始扩容)

实际上,HashMap并不会根据你提供的initial capacity来初始化一个数组,而是找到一个值 \(t\) 并满足 \(t >= i \&\& t==2^{n}\)(比如3对应得到4, 15对应得到16),并在第一次插入的时候进行初始化。

为什么数组在初始化的时候一定是2的倍数?这是因为方便扩容的时候直接将数组大小变成原来的二倍,同时也简化了一些其他的操作,比如如何定位到一个值所在的索引:

int index = (length - 1) & hash

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

正常的做法是,abs(hash) % SIZE像这样取余操作。但是如果除数是2的n次幂,则可以简化为位运算操作。

而至于为什么默认的负载因子是0.75,有人根据二项式分布算出最佳的load factor是 \(log(2)=0.693\) ,然后拍脑袋给出的0.75(乘以容量还可以得个整数...)。

树化(红黑树)

TREEIFY_THRESHOLD(树化阈值)

所以使用0.75作为负载因子,那么出现的情况是如果当前容量达到这个值的时候就会resize到原来的两倍。对于一个容量为4的Map来说,理想情况下元素均匀分布,是这样:

最好情况                                 极端情况
bucket | elements                      bucket | elements     
-------+---------                      -------+---------    
     0 | Z                                  0 |   
     1 | X                                  1 | Z -> X -> Y 
     2 |                                    2 |  
     3 | Y                                  3 | 

理想状况下(假设基于随机hash算法节点在桶中均匀分布,且节点的个数占桶的50%,那么单个节点出现在桶中的概率为0.5),节点在hash桶中的出现的频率遵循泊松分布\(λ = 0.5\) )

\[ P(X=k)=\frac{e^{-\lambda}\lambda^k}{k!}=\frac{e^{-0.5}0.5^k}{k!} \]

意味着在load factor=0.75的情况下,hash桶中出现 \(k\) 个节点(冲突)的概率大致为:

* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

可见哈希冲突导致一个桶中出现8个节点情况已经几乎小之又小的事情了,这是TREEIFY_THRESHOLD = 8的原因,当大于8的时候转换为红黑树。

Treeify(树化)

通常情况下,当哈希冲突产生的时候,会被当成链表存储。这个改变是通过JEP 180: Handle Frequent HashMap Collisions with Balanced Trees引入的。在下面的情况下,会转换为红黑树:

  • 链表中的节点数达到TREEIFY_THRESHOLD(8)
  • 容量至少达到MIN_TREEIFY_CAPACITY(64),否则只是单纯扩容到到原来的两倍

现实中哈希冲突的场景并不多,不过如果非要测试这种场景也很容易。比如Aa和字符串BB就拥有相同的哈希值,把他们随机组合到一起,还是一样。于是我们构建了很多个哈希值相同的key值,来演示哈希冲突的场景:

Treeify

尾插入

从上面的图可以注意到:哈希冲突的节点在链表中是插入到链表尾部的

在Java8之前是插入到前面的,但是Java8改成插入到尾部了,这样做的原因(据说)是因为扩容时会改变链表的顺序,在多线程条件下会导致形成闭环(从而可能引起死循环)。

fail-fast机制

在HashMap中存在一个变量记录修改的次数modCount,当这个次数和期待的不一致的时候就会抛出ConcurrentModificationException。这种机制被称之为"Fail-Fast”,意味着出现错误的时候尽早结束。通常在java.util下面的迭代器都是这类的,如果在迭代的中途数据被其他线程修改了,那么就会(尽可能的,当然并不能保证)触发这个检测。

java.util.concurrent包下的迭代器是"Fail-Safe"的,例如ConcurrentHashMap、CopyOnWriteArrayList等。

性能分析

HashMap对于getput操作的复杂度是常数级 \(\displaystyle{O(1)}\) ,在最坏的情况下,因为使用了红黑树进行查找,复杂度为 \(\displaystyle{O(log(n))}\)