Java源码之HashMap

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/07/24/Java源码之HashMap/

访问原文「Java源码之HashMap

关于HashMap

相信同学们在Coding(搬砖)的过程中经常会用到HashMap,那么HashMap到底是个什么东东呢?
以JDK8来讲,HashMap继承Map接口,在Map接口中描述Map是“An object that maps keys to values. A map cannot contain duplicate keys each key can map to at most one value.” 也就是说Map是一个映射键值的对象。映射中不能包含重复键,并且每个键可以映射到最多一个值。HashMap实现了Map接口,并且为基本操作(如:get、put)提供了常量时间的性能。

HashMap主要成员变量

下面的代码注释里详细的说明了HashMap的几个重要的成员变量。从这几个变量中可以分析得出,所有的键值对都存放在table变量中,而table变量的大小不是固定不变的,是在动态变化的,而且大小始终为2的幂。

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
/**
* HashMap的表结构,在首次使用的时候进行初始化,然后在需要的时候进行大小调整
* 表的大小始终为2的幂
* 初始值为16(DEFAULT_INITIAL_CAPACITY)
*/
transient Node<K,V>[] table;
/**
* 映射项集合
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* Map中映射对的数量
*/
transient int size;
/**
* 这个HashMap已被结构化修改的次数
* 结构修改是改变HashMap中的映射数或者修改其内部结构(例如rehash)的修改次数。
* 此字段用于使HashMap的Collection-views上迭代器更快的失效。 (请参阅ConcurrentModificationException)。
*/
transient int modCount;
/**
* 下一次调整大小的阈值 (capacity * load factor).
*/
int threshold;
/**
* 负载系数,默认为0.75f(DEFAULT_LOAD_FACTOR)
*/
final float loadFactor;

从上面的代码总可以看到,table属性的类型为Node,这个Node实现了Map.Entry接口,所以本质上还是Map.Entry。另外,HashMap包含另外一种TreeNodeTreeNode本身为红黑树结构。在HashMap中,当一个普通Node(Plain Node)的长度大于一定值时会转换为TreeNode,而TreeNode长度小于一定值时会转换普通Node。

从下面的代码中可以看到,Node实现了Map.Entry接口,并且本身为链表结构,这样是为了处理不同键值可能会出现相同Hash的情况。

1
2
3
4
5
6
7
8
9
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
// 下一个Node'指针'
Node<K,V> next;
...
}

HashMap中的get方法

get方法是我们常用的方法之一,下面是这个方法的源码。这个方法非常简单,可以看到它是委托给了getNode方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
*
* 返回键为key对应的值,如果不存在这个键,则返回null
*
* 更正式的说明是,如果这个map包含key到value的映射,这个方法会返回value
* 否则返回null
*
* 当然,返回null并不能说明这个map不包含这个key的映射,可以过containsKey这个方法判断是否包含这个key
*
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

下面是getNode方法,已经在主要代码上面加上了注释,比较好理解。

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
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table为null或者长度不大于0则返回null
// 根据key的hash值判断table中对应下标有没有对应的值,没有的话返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断第一个Node的键是否与查询的key一致,一致的话返回这个映射
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断第一个映射是否为树节点,是的话使用树结构的查询
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 如果不是树结构就是链表结构,然后沿着链表进行查询
// 如果链表节点的key与查询的key一致,返回这个映射
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 没有查询到返回null
return null;
}

HashMap中的put方法

put方法也是我们常用的方法之一,下面是这个方法的源码。这个方法也非常简单,可以看到它是委托给了putVal方法。

1
2
3
4
5
6
7
8
9
10
11
12
/**
*
* 在map中放入key到value的映射
* 如果已经存在key,则更新这个key对应的value
*
* @param key 与指定值相关联的键
* @param value 与指定键关联的值
* @return 与键关联的前一个值,如果没有映射键的键值,则为null。(null返回还可以表明映射之前与键关联的映射。)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

下面是putVal方法,方法比getNode复杂不少,但是整体思路也是很简单的。简单描述就是首先查找时候已经存在键为key的映射,如果存在的话,判断是否允许替换旧值,如果允许则替换;如果不存在键为key的映射,则新建一个这个映射,如果存在hash冲突,则加载对应hash列表的最后。最后判断map的大小是否大于需要调整大小的阈值,大于的话进行resize

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
/**
* 实现了Map.put以及相关方法
*
* @param hash 键的hash值
* @param key 键
* @param value 键对应的值
* @param onlyIfAbsent 如果是true, 不修改已经存在的值
* @param evict 如果是false, 表示在创建模式中
* @return 键对应的旧值,没有旧值返回null
*/
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是null或者空,进行resize
// 实际上HashMap实例初始化的时候不会初始化table,而是在使用的时候初始化,也就是这段代码
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果在table中找不到对应下标为hash值的Node,则新建一个Node,并将这个Node放入在table下标为hash值的地方
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果找到的Node中的键与key一直,那么e=p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果找到的Node为TreeNode,那么调用TreeNode的putTreeVal放入该映射
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 循环判断是否有Node满足键与将要放入的key一致
for (int binCount = 0; ; ++binCount) {
// 如果没有找到与key一致的Node则新建一个Node
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断这个Node列表长度是否大于等于要树形化的阈值
// 大于等于的话将这个Node列表转换为树结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到的Node中的键与key一致,那么e=p
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果有Node满足键与将要放入的key一致
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 是否允许替换旧值,允许则替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果map大小大于阈值,则resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

HashMap中的resize方法

HashMap中很重要的一个函数就是resize,代表HashMap容量的调整。首先是在首次往HashMap中放入数据的时候需要初始化table大小,另外是在map中映射数量大于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
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
90
91
92
93
/**
* 初始化或将大小增加一倍。
* 如果为空,则在字段阈值中分配初始容量目标。
* 否则,由于我们使用的是2的幂次扩展,每个容器中的元素必须保持在相同的索引中,或者在新表中使用2偏移量移动。
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果已经存在容量大于0
if (oldCap > 0) {
// 如果已经存在容量大于最大值,不改变容量大小,改变阈值为Integer最大值
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
}
// 如果旧阈值大于0,新容量为旧阈值
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;
// 将旧table的数据拷贝至新table
@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;
// TreeNode使用本身的方法赋值
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 链表赋值,具体复制的过程中考虑到了hash值的高位修改问题,不是很复杂,不详细说明
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;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 处理'低位'hash列表的尾节点
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 处理'高位'hash列表的尾节点
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

### 小结一下

本篇文章详细介绍了HashMap的相关内容,包含主要成员变量和主要成员方法。但是可以看到的是,HashMap的Node分为普通单链表和树链表,只介绍的单链表,而有一些操作是委托给树链表解决的。首先要说明的是,如果key的hash分散性很好,基本不会将单链表转换为树链表;另外树链表是红黑树,属于比较复杂并且可以单独拿出讲,或者说比较独立不放在HashMap里讲也可以。有时间的话我会对红黑树这块做一个专门的讲解。