死磕Jdk源码之HashMap:

本博客目前所有 死磕 Jdk 源码系列都是使用 jdk1.8版本。

简介

HashMapJDK1.8之前的实现方式 数组+链表,但是在JDK1.8后对HashMap进行了底层优化,改为了由 数组+链表+红黑树实现,主要的目的是提高查找效率。

JDK版本实现方式节点数>=8节点数<=6
1.8以前数组+单向链表数组+单向链表数组+单向链表
1.8以后数组+单向链表+红黑树数组+红黑树数组+单向链表
  • HashMap基于哈希表的Map接口实现,是以key-value存储形式存在。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)
  • HashMap 的实现不是同步的,这意味着它不是线程安全的。它的keyvalue都可以为null。此外,HashMap中的映射不是有序的。在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,新增了红黑树作为底层数据结构,结构变得复杂了,但是效率也变的更高效。

特性

数据结构

  1. 数组 HashMap内部维护一个Node数组
  2. 链表HashMapNode节点数小于等于 6 时,Node是单向链表结构
  3. 红黑树HashMapNode节点数大于等于 8 时,Node是红黑树结构

成员变量

继承自 AbstractMap

  • keySet 保存着MapkeySet集合
  • values 保存着MapvalueCollection集合
  • table NodeMap.Entry接口的实现类,在此存储数据的Node数组容量是2次幂,每一个Node本质都是一个单向链表
  • size HashMap大小,它代表HashMap保存的键值对的多少
  • modCount HashMap被改变的次数
  • threshold 下一次HashMap扩容的大小
  • loadFactor HashMap的负载因子。

常量

  • TREEIFY_THRESHOLD 这两个是限定值 当节点数大于8时会转为红黑树存储
  • UNTREEIFY_THRESHOLD 当节点数小于6时会转为单向链表存储
  • MIN_TREEIFY_CAPACITY 红黑树最小长度为 64
  • DEFAULT_INITIAL_CAPACITY HashMap容量初始大小
  • MAXIMUM_CAPACITY HashMap容量极限
  • DEFAULT_LOAD_FACTOR 负载因子默认大小

死磕源码

构造函数

默认无参构造函数,使用默认的负载因子 0.75f ,由于 loadFactorfinal类型,一经设定无法修改。

1
2
3
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

指定初始容量构造 HashMap

1
2
3
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

指定初始化容量和负载因子构造 HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public HashMap(int initialCapacity, float loadFactor) {
// 指定的容量大小不可以小于 0,否则将抛出 IllegalArgumentException 异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 判定指定的容量大小是否大于HashMap的容量极限
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 指定的负载因子不可以小于 0 或为 Null,若判定成立则抛出 IllegalArgumentException 异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
// 设置 HashMap 阈值,当 HashMap 中存储数据的数量达到 threshold 时,就需要将 HashMap 的容量加倍。
this.threshold = tableSizeFor(initialCapacity);
}

从一个Map中构建HashMap

1
2
3
4
5
6
// 传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 此构造方法主要实现了 Map.putAll()
putMapEntries(m, false);
}

Node单向链表的实现

单向链表的实现还是比较简单的

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
static class Node<K,V> implements Map.Entry<K,V> {
// 节点的哈希值
final int hash;
// 节点的 key
final K key;
// 节点的 value
V value;
// 后继节点
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

// 计算哈希值
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

// 设置新值,返回旧值
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

// equals 属性对比
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

TreeNode红黑树实现

红黑树的实现还是比较复杂的,这里就不列出所有源码,不了解红黑树的朋友,可以移步最容易懂得红黑树

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
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 红黑树的根节点
TreeNode<K,V> parent; // red-black tree links
// 左树
TreeNode<K,V> left;
// 右树
TreeNode<K,V> right;
// 上一个节点
TreeNode<K,V> prev; // needed to unlink next upon deletion
// 是否为红色节点
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

/**
* Returns root of tree containing this node.
*/
// 根节点的实现
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}

...
}

哈希值的计算实现

主要是将传入的参数key本身的hashCode与h无符号右移 16 位进行二进制异或运算得出一个新的hash

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put插入新的键值对

put方法调用putVal实现插入操作

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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 key 的哈希值
* @param key key
* @param value 插入的 value
* @param onlyIfAbsent 如果 true,就不需要更改现有值
* @param evict 如果为 false,则该表处于创建模式。
* @return 前一个值,如果没有则为空
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断表是否为 null 或 空,如果是就对表通过 resize 获取新表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 判断数组对应索引位置为 null 就创建新的节点插入该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 说明可能出现相同 key ,也有可能出现哈希碰撞
else {
Node<K,V> e; K k;
// 判断 hash 和 key 是否匹配,如果匹配就是覆盖了。覆盖原有的 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) {
// next 节点为 null,直接创建新节点插入到当前节点的后继节点中
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 是否需要转单链表为红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 判断 hash 和 key 是否匹配,如果是就跳出循环,因为找到了啊
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // p 记录下一个节点
}
}
// e 不为 null ,就是存在对于 key 映射
if (e != null) { // existing mapping for key
// 获取原 value
V oldValue = e.value;
// 如果需要改变现有值 后者 原 value 为 null
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回原 value
return oldValue;
}
}
// 修改次数 +1
++modCount;
// 大小 +1 ,是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

get获取对应值

调用getNode方法获取指定key对应的value,未找到就返回null

1
2
3
4
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

根据key的哈希值和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
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
    final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断数组不为 null,且不为空,且数组对应索引位的节点不为 null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断 hash 和 key 是否匹配,匹配了就直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//节点的后继节点不为 null
if ((e = first.next) != null) {
// 如果是红黑树结构
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 当前节点是链表结构,遍历链表直到找到 hash 和 key 都匹配的节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
```


### `resize`扩容


```java
final Node<K,V>[] resize() {
// 记录旧哈希表
Node<K,V>[] oldTab = table;
// 记录旧哈希表数组大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 记录原 threshold
int oldThr = threshold;
int newCap, newThr = 0;
// 说明 HashMap 已经初始化过
if (oldCap > 0) {
// 旧哈希表大小超过最大允许容量大小,旧将 threshold 置为 Integer.MAX_VALUE,就直接返回旧哈希表
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 原数组大小 * 2 小于最大允许容量大小,且原数组大小超过默认初始化大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新 threshold 就等于原哈希表长度 * 2
newThr = oldThr << 1; // double threshold
}
// 数组为空,第一次初始化,新数组大小就等于 threshold
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// threshold为零表示使用默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的 threshold 为 0
if (newThr == 0) {
// 通过新表大小乘以负载因子获取 threshold
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 得到新的 threshold
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的哈希表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果旧表有数据,就需要把旧表数据重新 put 到新表
if (oldTab != null) {
// 开始遍历哈希表数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 当前索引位置节点不为 null
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;
// e.hash & oldCap 等于 0 ,最高位 为 0,这是索引不变的链表,就说明索引不变
if ((e.hash & oldCap) == 0) {
// 第一次循环,尾节点为 null,将 e 赋值给头节点
if (loTail == null)
loHead = e;
// 将原尾节点的下一个节点设置为当前节点,当前节点就是尾节点了
else
loTail.next = e;
// 尾节点为当前节点
loTail = e;
}
//最高位 为 1 ,说明索引发生了变化
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 尾节点不为 null,说明节点数为 > 1
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// rehash 后节点新的位置一定为 原索引 + oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

总结

HashMap的扩容特别占用系统资源,涉及到内存拷贝。所以我们在使用中尽量避免HashMap触发扩容。当 size > threshold 的时候会触发扩容操作,所以尽量根据实际场景给定HashMap初始化容量。避免因为默认容量过小导致频繁扩容。