万字长文！深入剖析HashMap，Java基础笔试题大全带答案

2021-08-08 22:14:25

java 后端程序员

采用Hashtable
调用Collections.synchronizeMap()方法来让HashMap具有多线程能力
采用ConcurrentHashMap

前两个方案的思路是相似的，均是每个方法中，对整个对象进行上锁。Hashtable是老一代的集合框架，很多的设计均以及落后，他在每一个方法中均加上了synchronize关键字保证线程安全


// Hashtable
public synchronized V get(Object key) {...}
public synchronized V put(K key, V value) {...}
public synchronized V remove(Object key) {...}
public synchronized V replace(K key, V value) {...}
...


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.

第二种方法是返回一个SynchronizedMap对象，这个对象默认每个方法会锁住整个对象。如下源码：

这里的mutex是什么呢？直接看到构造器：

final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
// 默认为本对象
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

可以看到默认锁的就是本身，效果和Hashtable其实是一样的。这种简单粗暴锁整个对象的方式造成的后果是：

锁是非常重量级的，会严重影响性能。
同一时间只能有一个线程进行读写，限制了并发效率。

ConcurrentHashMap的设计就是为了解决此问题。他通过降低锁粒度+CAS的方式来提高效率。简单来说，ConcurrentHashMap锁的并不是整个对象，而是一个数组的一个节点，那么其他线程访问数组其他节点是不会互相影响，极大提高了并发效率；同时ConcurrentHashMap读操作并不需要获取锁，如下图：

关于ConcurrentHashMap和Hashtable的更多内容，限于篇幅，我会在另一篇文章讲解。

那么，使用了上述的三种解决方案是不是绝对线程安全？先观察下面的代码：

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("abc","123");
Thread1:
if (map.containsKey("abc")){
String s = map.get("abc");
}
Thread2:
map.remove("abc");























当Thread1调用containsKey之后释放锁，Thread2获得锁并把“abc”移除再释放锁，这个时候Thread1读取到的s就是一个null了，也就出现了问题了。所以ConcurrentHashMap类或者Collections.synchronizeMap()方法或者Hashtable都只能在一定的限度上保证线程安全，而无法保证绝对线程安全。

关于线程安全，还有一个fast-fail问题，即快速失败。当使用HashMap的迭代器遍历HashMap时，如果此时HashMap发生了结构性改变，如插入新数据、移除数据、扩容等，那么Iteractor会抛出fast-fail异常，防止出现并发异常，在一定限度上保证了线程安全。如下源码：

创建Iteractor对象时会记录HashMap的modCount变量，每当HashMap发生结构性改变时，modCount会加1。在迭代时判断HashMap的modCount和自己保存的expectedModCount是否一致即可判断是否发生了结构性改变。

fast-fail异常只能当做遍历时的一种安全保证，而不能当做多线程并发访问HashMap的手段。若有并发需求，还是需要使用上述的三种方法。

小结

HashMap并不能保证线程安全，在多线程并发访问下会出现意想不到的问题，如数据丢失等

HashMap1.8采用尾插法进行扩容，防止出现链表环导致的死循环问题

解决并发问题的的方案有Hashtable、Collections.synchronizeMap()、ConcurrentHashMap。其中最佳解决方案是ConcurrentHashMap

上述解决方案并不能完全保证线程安全

快速失败是HashMap迭代机制中的一种并发安全保证

源码解析

[](

)关键变量的理解

HashMap源码中有很多的内部变量，这些变量会在下面源码分析中经常出现，首先需要理解这些变量的意义。

// 存放数据的数组
transient Node<K,V>[] table;
// 存储的键值对数目
transient int size;
// HashMap结构修改的次数，主要用于判断fast-fail
transient int modCount;
// 最大限度存储键值对的数目(threshodl=table.length*loadFactor)，也称为阈值
int threshold;
// 装载因子，表示可最大容纳数据数量的比例
final float loadFactor;
// 静态内部类，HashMap存储的节点类型；可存储键值对，本身是个链表结构。
static class Node<K,V> implements Map.Entry<K,V> {...}

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.

[](

)扩容

HashMap源码中把初始化操作也放到了扩容方法中，因而扩容方法源码主要分为两部分：确定新的数组大小、迁移数据。详细的源码分析如下，我打了非常详细的注释，可选择查看。扩容的步骤在上述已经讲过了，读者可以自行结合源码，分析HashMap是如何实现上述的设计。

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) {
// 如果已经超过了设置的最大长度(1<<30,也就是最大整型正数)
if (oldCap >= MAXIMUM_CAPACITY) {
// 直接把阈值设置为最大正数
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 设置为原来的两倍
newThr = oldThr << 1;
}
// 原数组长度为0，但最大限度不是0，把长度设置为阈值
// 对应的情况就是新建HashMap的时候指定了数组长度
else if (oldThr > 0)
newCap = oldThr;
// 第一次初始化，默认16和0.75
// 对应使用默认构造器新建HashMap对象
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果原数组长度小于16或者翻倍之后超过了最大限制长度，则重新计算阈值
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);
// 新的位置只有两种可能：原位置，原位置+老数组长度
// 把原链表拆成两个链表，然后再分别插入到新数组的两个位置上
// 不用多次调用put方法
else {
// 分别是原位置不变的链表和原位置+原数组长度位置的链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历老链表，判断新增判定位是1or0进行分类
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);
// 最后赋值给新的数组
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新数组
return newTab;
}

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.

[](

)添加数值

调用put()方法添加键值对，最终会调用putVal()来真正实现添加逻辑。代码解析如下：

public V put(K key, V value) {
// 获取hash值，再调用putVal方法插入数据
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent表示是否覆盖旧值，true表示不覆盖，false表示覆盖，默认为false
// evict和LinkHashMap的回调方法有关，不在本文讨论范围
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是HashMap内部数组，n是数组的长度，i是要插入的下标，p是该下标对应的节点
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，若是则创建节点直接插入，若不是，进入下面else逻辑
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// e表示和当前key相同的节点，若不存在该节点则为null
// k是当前数组下标节点的key
Node<K,V> e; K k;
// 判断当前节点与要插入的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) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 长度大于等于8时转化为红黑树
// 注意，treeifyBin方法中会进行数组长度判断，
// 若小于64，则优先进行数组扩容而不是转化为树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到相同的直接跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果找到相同的key节点，则判断onlyIfAbsent和旧值是否为null
// 执行更新或者不操作，最后返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 如果不是更新旧值，说明HashMap中键值对数量发生变化
// modCount数值+1表示结构改变
++modCount;
// 判断长度是否达到最大限度，如果是则进行扩容
if (++size > threshold)
resize();
// 最后返回null（afterNodeInsertion是LinkHashMap的回调）
afterNodeInsertion(evict);
return null;
}

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.

代码中关于每个步骤有了详细的解释，这里来总结一下：

总体上分为两种情况：找到相同的key和找不到相同的key。找了需要判断是否更新并返回旧value，没找到需要插入新的Node、更新节点数并判断是否需要扩容。
查找分为三种情况：数组、链表、红黑树。数组下标i位置不为空且不等于key，那么就需要判断是否树节点还是链表节点并进行查找。
链表到达一定长度后需要扩展为红黑树，当且仅当链表长度>=8且数组长度>=64。

最后画一张图总体再加深一下整个流程的印象：

最后

看完上述知识点如果你深感Java基础不够扎实，或者刷题刷的不够、知识不全面

小编专门为你量身定制了一套<Java一线大厂高岗面试题解析合集：JAVA基础-中级-高级面试+SSM框架+分布式+性能调优+微服务+并发编程+网络+设计模式+数据结构与算法>

针对知识面不够，也莫慌！还有一整套的<Java核心进阶手册>，可以瞬间查漏补缺

全都是一丢一丢的收集整理纯手打出来的——收整在***【我的学习笔记大全】***，有需要的朋友可以自取

更有纯手绘的各大知识体系大纲，可供梳理：Java筑基、MySQL、Redis、并发编程、Spring、分布式高性能架构知识、微服务架构知识、开源框架知识点等等的xmind手绘图~

版权声明

本文为[程序员夏亚]所创，转载请带上原文链接，感谢

https://blog.51cto.com/u_15308638/3314566

文章推荐