0%

Java-HashMap

本章属于持续学习、长期更修。

HashMap

特征

  • HashMap 允许null键和null值,null键哈西值为0.
  • HashMap 并不是有序的存放。在使用iterate迭代的时候,并不能得到存放顺序。
  • HashMap使用它的内部类Node <K,V>来存储映射。
  • HashMap将entries存储到多个单链表中,称为存储桶或存储桶。默认的箱数为16,默认负载因子0.75,它的扩展系数为2,当键值对数量大于阈值,则容量扩容到原来的2倍。
  • HashMap不是线程安全的,对于多线程环境,您应该使用ConcurrentHashMap类或使用Collections.synchronizedMap()方法获取同步映射。
  • 底层实现是链表,但是jdk1.8后添加了红黑谁的转换。
  • HashMap的Key用存放,所以key默认不允许重复的,如果想重复就重写key的hashcode和equals方法。
  • 查找方法,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

源码分析

HashMap中的常量以及变量

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
// 未指定容量大小的情况下,默认初始化16。容量都是2的幂。第一次扩容大概率情况下是64。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 容量最大长个数。
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子,
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// HashMap使用单链表来存储元素,这些元素称为bin或buckets。当我们调用put方法时,key的hashCode用于确定将用于存储映射的存储区。
// 链表转换红黑树的阀值。当某个bin\buckets的长度大于8的时候进行转换。
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换链表的阀值。当某个bin\buckets的长度小于8的时候进行转换。
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中bin最小hash容量,如果大于这个值会进行resize扩容操作,此值至少是TREEIFY_THRESHOLD的4倍
static final int MIN_TREEIFY_CAPACITY = 64;

// 被transient修饰的变量不回被序列化。
// HashMap内部类实现了Map的内部类Entry,用于存储K,V,第一次使用的时候被创建,根据需要可以进行resize。分配长度为2的冥次方
transient Node<K,V>[] table;
// 当被调用entrySet时被赋值。通过keySet()方法可以得到map key的集合,通过values方法可以得到map value的集合
transient Set<Map.Entry<K,V>> entrySet;

// size表示HashMap中存放KV的数量(为链表和树中的KV的总和)。
transient int size;

// 操作次数,通常用过fail-fast。每次扩容和更改map结构的计数器
transient int modCount;

// threshold=capacity*loadFactor threshold表示当HashMap的size大于threshold时会执行resize操作。
int threshold;

// Load Factor用于确定何时重新散列HashMap并增加存储桶大小。存储桶或容量的默认值为16,负载系数为0.75。通过乘以容量和负载因子来计算重新散列的阈值
final float loadFactor;

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
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // node哈希值
final K key;
V value;
Node<K,V> next; // 下一个node的地址

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; }
// 这里重写方法,所以map.toString()不是内存地址。
public final String toString() { return key + "=" + value; }

// 这里重写了hashCode()方法
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;
//Map.Entry 相等的条件:键相等、值相等、个数相等、顺序相等
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;
}
}
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
@Test
public void testConstructor(){
log.info("Map test");
// 1
Map m = new HashMap();
// 2
Map m1 = new HashMap(10);
// 3
Map m2 = new HashMap(10,0.75f);
// 4
Map m3 = new HashMap(map1);
// put
HashMap map = new HashMap<String,Object>();
map.put("1","1");
map.put("2","2");
map.put("3","3");
map.put("4","4");
log.info("map {}",map);
map.put("1",3);
log.info("map {}",map);
map.put("1",null);
log.info("map {}",map);
map.put(null,null);
log.info("map {}",map);
Set<String> keySet = map.keySet();
log.info("keySet {}",keySet);
Collection<String> list = map.values();
log.info("list {}",list);
log.info("map.get {}",map.get("1"));
}


16:16:25.020 [main] INFO cn.z201.java.test.map.HashMapTest - map {1=1, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - map {1=3, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - map {1=null, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - map {null=null, 1=null, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - keySet [null, 1, 2, 3, 4]
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - list [null, null, 2, 3, 4]
12:37:27.533 [main] INFO cn.z201.java.test.map.HashMapTest - map.get null

源码方法跟踪

  • HashMap 源码中三个重要方法:查询、新增和数据扩容。
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305

// 1 构造方法为空,loadFactor 将取默认系数。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 2 构造方法一个参数, 将指定Capacity的大小。其实调用的是另外的一个构造方法。但是指定了默认的负载因子。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 3 构造方法两个参数, 将指定Capacity的大小,和负载因子。
public HashMap(int initialCapacity, float loadFactor) {
// 如果指定的容量大小不合法直接抛出异常。
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 如果指定的容量大于最大的容量大小限制,则直接赋值为最大。并不抛出异常。
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 如果指定的负载因子不合法,则直接抛出异常。
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 合法赋值
this.loadFactor = loadFactor;
// 计算容量的扩展阀值
this.threshold = tableSizeFor(initialCapacity);
}

// 4 创建一个与指定Map具有相同映射并且指定负载因子系数为0.75的Map
public HashMap(Map<? extends K, ? extends V> m) {
// 直接指定默认的负载因子。
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

// tableSizeFor(int) 来根据指定的容量设置阈值,这个方法经过若干次无符号右移、求异运算,得出最接近指定参数 cap 的 2 的 N 次方容量。假如你传入的是 5,返回的初始容量为 8 。
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;
}


// 将目标map的桶插入当前map中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获得bin(桶)的长度。
int s = m.size();
// 如果桶长度大0则进行复制,否则什么都不做。
if (s > 0) {
// 如果当前位数的痛数组为空。也就是未初始化
if (table == null) { // pre-size

float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果 则指定的容量设置阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
//数组不为空,桶数量超过阈值就扩容
else if (s > threshold)
resize();
// 增强循环为当前的table赋值。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 和put调用的是一个方法。//先经过 hash() 计算位置,然后复制指定 map 的内容
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* 插入数据
* Implements Map.put and related methods.
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 声明临时变量 table 数组 p链表
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果当前的桶是null,长度为0。就扩容一次。
if ((tab = table) == null || (n = tab.length) == 0)
// 则n 指向最后一个桶的位置
n = (tab = resize()).length;
// 计算插入的位置有没有node, (n - 1) &hash得到的是key所在的桶的头结点,如果节点不在这个桶。
if ((p = tab[i = (n - 1) & hash]) == null)
// 此时的i = 0 , 新建个节点并放进去
tab[i] = newNode(hash, key, value, null);
else {
//如果插入的位置有元素,就是p != null 被找到了。开始替换value流程。
// 临时变量 e 被替换的元素
Node<K,V> e; K k;
//p 指向要插入的桶第一个 元素的位置,如果 p 的哈希值、键、值和要添加的一样。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// e 指向 p
e = p;
// //如果key hash不一样,判断是否红黑树
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;
}
//如果找到要替换的节点,就停止,此时 e 已经指向要被替换的节点
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;
}

/**
* 扩容
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 获取当前的table
Node<K,V>[] oldTab = table;
// 获取当前table的容量大小。
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取当前table的扩展阀值
int oldThr = threshold;
// 临时变量 新的容量、阀值。
int newCap, newThr = 0;
// 原容量大于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)
//如果旧容量小于等于 16,新的阈值就是旧阈值的两倍
newThr = oldThr << 1; // double threshold
}
// //如果旧容量为 0 ,并且旧阈值>0,说明之前创建了哈希表但没有添加元素
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化容量等于阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//旧容量、旧阈值都是0,说明还没创建哈希表,容量为默认容量,阈值为 容量*加载因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果此时新的阈值为 0 ,就得用 新容量*加载因子 重计算一次
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 覆盖当前扩展阀值
threshold = newThr;

// 创建新链表数组,容量是原来的两倍。newCap上面已经被赋值了。
@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;
// 如果桶里面只有一个元素,next没有得情况下。
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
// 如果桶里面有元素。保留旧哈希表桶中链表的顺序
// 链表复制,JDK 1.8 扩容优化部分
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//do-while 循环赋值给新哈希表
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;
}
// 将原索引 + oldCap 放到哈希桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

// 查询
public V get(Object key) {
Node<K,V> e;
// 对 key 进行哈希操作
return (e = getNode(hash(key), key)) == null ? null : e.value;
}


/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// tab = table) != null 数组桶不为null ,并赋值给临时桶数组 tab。
// (n = tab.length) > 0 桶的长度大于0 ,并赋值给临时桶长度 n。
// (first = tab[(n - 1) & hash]) != null 第一个桶里面有元素。
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果桶里面第一个元素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) {
// 如果第一节点是树结构,则使用 getTreeNode 直接获取相应的数据
if (first instanceof TreeNode)
// 如果第一个元素是红黑树、暂时不深入。
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// do while // 非树结构,循环节点判断 循环便利桶所有的key hash 找到则返回。
do {
// hash 相等并且 key 相同,则返回此节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 没找到。
return null;
}