万字长文!深入剖析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");

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

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

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


final Node<K,V> nextNode() {
...
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
...
}

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

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

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

小结

  1. HashMap并不能保证线程安全,在多线程并发访问下会出现意想不到的问题,如数据丢失等
  1. HashMap1.8采用尾插法进行扩容,防止出现链表环导致的死循环问题
  1. 解决并发问题的的方案有HashtableCollections.synchronizeMap()ConcurrentHashMap。其中最佳解决方案是ConcurrentHashMap
  1. 上述解决方案并不能完全保证线程安全
  1. 快速失败是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.

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

  1. 总体上分为两种情况:找到相同的key和找不到相同的key。找了需要判断是否更新并返回旧value,没找到需要插入新的Node、更新节点数并判断是否需要扩容。

  2. 查找分为三种情况:数组、链表、红黑树。数组下标i位置不为空且不等于key,那么就需要判断是否树节点还是链表节点并进行查找。

  3. 链表到达一定长度后需要扩展为红黑树,当且仅当链表长度>=8且数组长度>=64。

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

最后

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

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

image

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

image

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

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

image

image

版权声明
本文为[程序员夏亚]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15308638/3314566

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云