0%

Java - HashMap

HashMap是基于哈希表实现的一个Key-Value的容器,在Java中应用相当的广泛,并且在JDK8中做了一个重大的改变,在JDK8之前,采用数组+链表的形式存储数据,不过考虑到链表$O(n)$的查询性能,自JDK8开始引入了红黑树的结构进行优化,形成了数组+链表+红黑树形式。

本文相关的HashMap源码都是基于JDK8。

HashMap的数据结构及继承关系如下:

2

Map接口中几乎定义了所有Key-Value数据结构相关的公共接口,同时Map接口中还定义了Entry接口,用来代表Map中存储的元素。HashMap继承自AbstractMap,同时实现了Map接口,HashMap中有个内嵌类Node,实现了Entry接口,用来作为容器中元素的载体。

我们先了解一下HashMap中放入一个元素的流程,然后一步步对流程中核心的部分进行剖析:

3

对应的代码为:

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
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为空,则初始化数组
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值相等,则更新value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 数组下标处元素类型为TreeNode,表示是红黑树,则调用红黑树的put操作
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;
}
}
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;
}

下标计算

HashMap中,使用一个Node数组来保存所有的元素,当需要查询或者添加一个元素时,会通过哈希算法计算出Key在数组中的下标,相关代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap是允许key为null的,因此当key为null时,hash值为0;当key不为null时候,简单来说分为三步:

  • 得到Key的hashCode;
  • 高位与低位进行异或运算;
  • 取模运算。

举个例子:

4

注意这里将高16位与低16位进行了异或,原因在hash函数的注释中也有解释。不管Key的hashCode函数中的哈希算法有多么分散,最终都会与数组大小进行与运算,则hashCode函数返回的值中,始终只有低位有效,这样会增大哈希冲突的概率,因此作者基于多方因素考虑之后,将hashCode的高16位于低16位进行异或,从而让高16位也参与运算,降低哈希冲突的概率。

通过哈希算法,最终可以通过一个输入的Key,计算得到其在数组中的下标。

插入/更新元素

在操作元素之前,会先判断table数组是否有初始化,如果没有,则先初始化数组,初始化之后,会先将下标位置的元素当做数组元素来处理:

  • 判断下标位置是否为空,如果为空,则将元素封装成一个HashMap.Node对象,然后将下标位置指向这个对象;

    1
    2
    if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  • 如果下标位置不为空,则判断下标位置的元素是否与传入的Key相等,若是,则更新Node对象的value;

    1
    2
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    // ...
  • 若下标位置不为空,且与传入的Key不相等,则表示产生了哈希冲突,利用链表或者红黑树来解决冲突:

    通过判断数组下标的节点类型,来判断是红黑树还是链表:

    • 如果节点类型为TreeNode,则是一个红黑树的节点,则进入红黑树的逻辑;
    • 否则,则表示是链表节点,则进入链表的逻辑。

    确定具体的数据结构之后,再进行查找并更新节点,如果没有查询到,则直接新增节点。

当类型为链表时,追加元素之后,还会判断链表的长度,如果超过大于等于(TREEIFY_THRESHOLD),则会将链表转成红黑树。

在链表转红黑树的treeifyBin函数中,转红黑树还有个隐藏条件,如果数组长度小于MIN_TREEIFY_CAPACITY(64),则只进行扩容,不进行转红黑树。

与链表转红黑树相反,当删除元素之后,红黑树节点个数不足UNTREEIFY_THRESHOLD(6)时,红黑树又回转回成链表。

为什么不直接用红黑树

在HashMap的注释中有提到:

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD).

由于红黑树节点占用的空间是链表节点的2倍左右,因此主要是基于空间的考虑,所以当元素很少的时候,使用链表。

链表与红黑树比起来,链表的插入效率更高,只需要更新next字段就可以了,但是查询操作需要$O(n)$的时间复杂度;红黑树的查询效率更高,只需要$O(log_2n)$,但是每次插入元素,都会涉及到节点着色,左旋,右旋等操作。

链表转红黑树的阈值为什么是8

在HashMap的注释中,也提到了这一点:

In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
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

简单来说,一个随机分布的hashCode,节点分布在哈希桶中的概率遵循泊松分布,按照泊松分布可以计算出哈希桶中的元素个数与概率的对照表,可以看到元素个数为8的概率已经非常低了,大于8的概率已经低于千万分之一了,因此将阈值数量定义为8。

扩容

如果一个HashMap的容量是固定的,那么随着元素的不断增加,哈希冲突的概率会越来越大,导致哈希表本身$O(1)$的查询性能优势就不复存在了,因此当HashMap的元素数量达到一定之后,就会进行扩容。简单描述扩容,就是新建一个比原来大一倍的数组,然后把元素从旧数组里挪到新数组里。

触发条件

当插入一个新元素之后,会判断数组长度是否超过阈值(threshold),如果超过阈值,则会触发一次扩容:

1
2
3
// threshold: The next size value at which to resize (capacity * load factor).
if (++size > threshold)
resize();

阈值(threshold)是由数组的当前容量(capacity) * 负载因子(loadFactor)得来,loadFactor默认为0.75。loadFactor为啥默认是0.75?在源码注释中也有解释:

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

如果负载因子过高,则哈希冲突的概率会增大,导致产生链表,红黑树等存储结构,因此这样做虽然会减少空间开销,提高空间利用率,但也增加了查询操作的耗时;负载因子过低,则相反,虽然能减少查询操作耗时,但是空间利用率很低,并且会增加扩容次数。因此最后综合时间和空间的考虑之后,默认值被设置为0.75。

扩容倍数

HashMap在扩容的时候,会以2的n次方进行扩容,即是每次都会将数组容量扩大成原来的两倍(newCap = oldCap << 1),这样做可以在重新计算元素位置时,获得很高的效率,举个例子:

5

当容量扩大一倍的时候,$2n-1$会比$n-1$在高位多出一个1,那么:

  • 如果Key的哈希值在这一位是0,那么与运算之后的结果不会变,则表示Key的下标不变,还是在原来的位置;
  • 如果Key的哈希值在这一位是1,那么与运算之后的结果就会比原来正好多出来一个$n$,则表示Key的下标会偏移$n$。

这个方法很巧妙,使得每次在扩容的时候,只需要判断一下元素的哈希值对应的高位是0还是1,就可以判断出元素要么还是在原来的位置不动,要么就是偏移oldCap个位置,省去了重新计算的步骤。

但是HashMap在初始化的时候,是可以任意传入初始化容量大小的,那么怎么保证哈希桶的数量一直是2的n次方呢?我们来看看构造函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public HashMap(int initialCapacity, float loadFactor) {
// ...
this.threshold = tableSizeFor(initialCapacity);
}

/**
* 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;
}

重点在于tableSizeFor函数,举个例子:

6

不管输入的cap是不是2的n次方的值,函数最终都会返回一个大于等于cap的,最接近2的n次方的值,作为初始化的threshold,然后在哈希桶初始化(table变量)的时候,会将threshold更新为threshold * loadFactor。

扩容流程

扩容函数如下:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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;
}
else if (oldThr > 0)
// oldCap==0,oldThr>0,则说明是刚初始化,则直接用oldThr作为扩容之后的容量
newCap = oldThr;
else {
// 没有任何初始化的信息,则使用默认数据
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 {
// loHead和loTail表示元素在新数组中,下标不变的元素组成的链表
Node<K,V> loHead = null, loTail = null;
// hiHead和loHead表示元素在新数组中,需要偏移oldCap个位置的元素组成的链表
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 判断扩容之后,高位的1与hash的与运算的结果
if ((e.hash & oldCap) == 0) {
// 为0表示下标不变
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 为1表示需要偏移
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的默认初始化容量是16,假设需要往HashMap中存放500个数据,那么需要扩容6次:32 => 64 =>128 =>256 => 512 => 1024(默认负载因子为0.75,500超过了512 * 0.75,因此最后需要扩容到1024),每次扩容的时候,都需要重建哈希表,因此扩容操作是非常耗时的,应当尽量避免发生扩容操作,而正确的设置HashMap的初始容量,可以很好的避免扩容的发生。

假设需要存放的数据个数为$N$,则最佳的初始化数值为:$(int)(N / 0.75f + 1.0f)$。

扩容倍数章节所说,初始化数值会被二次计算,最终得到一个2的n次方的值,作为初始容量。

线程安全问题

由于HashMap中的各种操作都没有被锁或者CAS保护起来,因此当出现多线程操作数据,比如多个线程调用put时,便可能会出现数据不一致的问题。

在JDK7中,HashMap扩容的时候,链表中的元素顺序会倒置,因此在扩容的过程中发生get操作的话,有一定几率造成死循环(具体case可以参考文末的文章),JDK8在扩容的时候,保持了链表中元素的顺序,因此不存在扩容时出现死循环的问题,不过还是有可能在其他地方,由于多线程操作而出现死循环的问题。

如果对线程安全有要求,还是推荐使用ConcurrentHashMap比较安全。

参考



-=全文完=-