Map-JAVA面试常问

1.HashMap底层实现

底层实现在jdk1.7和jdk1.8是不一样的

jdk1.7采用数组加链表的方式实现 jdk1.8采用数组加链表或者红黑树实现

1.png2.png

HashMap中每个元素称之为一个哈希桶(bucket),哈希桶包含的内容有以下4项

  • hash值(哈希函数计算出来的值)

  • Key

  • value

  • next(下一个节点默认).

默认情况下,在jdk1.8+版本中,HashMap使用的是数组加链表的形式存储的,而当数组的长度大于64,并且链表的长度大于8时,就会将链表升级成红黑树,以增加HashMap的查询时的性能

初始容量:HashMap的初始容量为0,这是一种懒加载的方式,直到第一次put操作才会初始化数组大小默认为16

2.ConcurrentHashMap原理?为什么要这样改进

ConcurrentHashMap在不同的JDK版本中实现也是不同的。

在JDK1.7中它使用的是数组加链表的形式实现的,而数组分为:大数组Segment和小数组HashEntry。 而大数组Segment可以理解为MYSQL中的数据库,而每个数据库(Segment)中又有很多张表HashEntry,每一个HashEntry又有多条数据,这些数据用链表连接的,如下图所示:

33.webp

而在JDK1.7中,ConcurrentHashMap是通过在Segment加锁来保证其安全性的,所以我们把它称为分段锁或片段锁,如下图所示

444.webp

它实现的源码如下:

555.webp

从上面的源码可以看出,JDK1.7时,ConcurrentHashMap主要用ReentrantLock进行加锁来实现线程安全的。 而在JDK1.8中,它是使用了数组+链表/红黑树的方式优化了concurrentHashMap的实现,具体结构如下

666.png

链表升级为红黑树的规则:当链表长度大于8,并且数组的长度大于64时,链表就会升级为红黑树的结构。

注意:ConcurrentHashMap在jdk1.8+虽然保留了Segment的定义,但这只是为了保证序列化时的兼容性,不再有任何结构上的用处了。

在JDK1.8中的ConcurrentHashMap使用的是CAS+volatile或者syncHronized的方式来保证线程安全的,他的核心实现源码如下。

//ConcurrentHashMap使用volatile修饰节点数组,保证其可见性,禁止指令重排。
//而HashMap没有使用volatile,  transient Node<K,V>[] table; 
transient volatile Node<K,V>[] table;
public V put(K key, V value) {return putVal(key, value, false);
}final V putVal(K key, V value, boolean onlyIfAbsent) {// key和value都不能为nullif (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {  //死循环,可视为乐观锁Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)// 如果tab未初始化或者个数为0,则初始化node数组tab = initTable();else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))// 如果使用CAS插入元素时,发现已经有元素了,则进入下一次循环,重新操作// 如果使用CAS插入元素成功,则break跳出循环,流程结束break;                   // no lock when adding to empty bin}else if ((fh = f.hash) == MOVED)// 如果要插入的元素所在的tab的第一个元素的hash是MOVED,则当前线程帮忙一起迁移元素tab = helpTransfer(tab, f);else {   //发生hash冲突// 如果这个tab不为空且不在迁移元素,则锁住这个tab(分段锁)// 并查找要插入的元素是否在这个tab中// 存在,则替换值(onlyIfAbsent=false)// 不存在,则插入到链表结尾或插入树中V oldVal = null;synchronized (f) {// 再次检测第一个元素是否有变化,如果有变化则进入下一次循环,从头来过if (tabAt(tab, i) == f) {// 如果第一个元素的hash值大于等于0(说明不是在迁移,也不是树)// 那就是tab中的元素使用的是链表方式存储if (fh >= 0) {// tab中元素个数赋值为1binCount = 1;// 遍历整个tab,每次结束binCount加1for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {// 如果找到了这个元素,则赋值了新值(onlyIfAbsent=false),并退出循环oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}Node<K,V> pred = e;if ((e = e.next) == null) {// 如果到链表尾部还没有找到元素,就把它插入到链表结尾并退出循环pred.next = new Node<K,V>(hash, key,value, null);break;}}}else if (f instanceof TreeBin) {// 如果第一个元素是树节点Node<K,V> p;// tab中元素个数赋值为2binCount = 2;// 调用红黑树的插入方法插入元素,如果成功插入则返回null,否则返回寻找到的节点if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {// 如果找到了这个元素,则赋值了新值(onlyIfAbsent=false),并退出循环oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}// 如果binCount不为0,说明成功插入了元素或者寻找到了元素if (binCount != 0) {// 如果链表元素个数达到了8,则尝试树化// 因为上面把元素插入到树中时,binCount只赋值了2,并没有计算整个树中元素的个数,所以不会重复树化if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);// 如果要插入的元素已经存在,则返回旧值if (oldVal != null)return oldVal;// 退出外层大循环,流程结束break;}}}// 成功插入元素,元素个数加1(是否要扩容在这个里面)addCount(1L, binCount);// 成功插入元素返回nullreturn null;
}
public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 计算hashint h = spread(key.hashCode());// 判断数组是否为空,通过key定位到数组下标是否为空if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {// 如果第一个元素就是要找的元素,直接返回if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}else if (eh < 0)// hash小于0,说明是树或者正在扩容// 使用find寻找元素,find的寻找方式依据Node的不同子类有不同的实现方式return (p = e.find(h, key)) != null ? p.val : null;// 遍历整个链表寻找元素while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null;
}
public V remove(Object key) {// 调用替换节点方法return replaceNode(key, null, null);
}final V replaceNode(Object key, V value, Object cv) {// 计算hashint hash = spread(key.hashCode());// 循环遍历数组for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;//校验参数if (tab == null || (n = tab.length) == 0 ||(f = tabAt(tab, i = (n - 1) & hash)) == null)break;else if ((fh = f.hash) == MOVED)// 如果正在扩容中,协助扩容tab = helpTransfer(tab, f);else {V oldVal = null;// 标记是否处理过boolean validated = false;//用 synchronized 同步锁,保证并发时元素移除安全synchronized (f) {// 再次验证当前tab元素是否被修改过if (tabAt(tab, i) == f) {if (fh >= 0) {// fh>=0表示是链表节点validated = true;// 遍历链表寻找目标节点for (Node<K,V> e = f, pred = null;;) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {V ev = e.val;if (cv == null || cv == ev ||(ev != null && cv.equals(ev))) {oldVal = ev;if (value != null)e.val = value;else if (pred != null)pred.next = e.next;elsesetTabAt(tab, i, e.next);}break;}pred = e;// 遍历到链表尾部还没找到元素,跳出循环if ((e = e.next) == null)break;}}else if (f instanceof TreeBin) {// 如果是树节点validated = true;TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> r, p;// 遍历树找到了目标节点if ((r = t.root) != null &&(p = r.findTreeNode(hash, key, null)) != null) {V pv = p.val;if (cv == null || cv == pv ||(pv != null && cv.equals(pv))) {oldVal = pv;if (value != null)p.val = value;else if (t.removeTreeNode(p))setTabAt(tab, i, untreeify(t.first));}}}}}// 如果处理过,不管有没有找到元素都返回if (validated) {// 如果找到了元素,返回其旧值if (oldVal != null) {// 如果要替换的值为空,元素个数减1if (value == null)addCount(-1L, -1);return oldVal;}break;}}}// 没找到元素返回空return null;
}

从上述代码可以看出,在JDK1.8中,添加元素首先会判断容器是否为空,如果为空则使用volatile加cas来初始化。如何容器不为空则根据存储的元素计算改位置是否为空,如果为空则利用cas设置该节点;如果不为空则使用synchronize加锁,遍历桶中的数据,替换或新增节点到桶中,最后再判断是否需要转为红黑树,这样就能保证并发访问时的线程安全了。

put操作总结

做插入操作时,首先进入乐观锁,在乐观锁中判断容器是否初始化,
如果没初始化则初始化容器;如果已经初始化,则判断该hash位置的节点是否为空,
如果为空,则通过CAS操作进行插入。
如果该节点不为空,再判断容器是否在扩容中,如果在扩容,则帮助其扩容。如果没有扩容,则进行最后一步,先加锁,然后找到hash值相同的那个节点(hash冲突),
循环判断这个节点上的链表,决定做覆盖操作还是插入操作。
循环结束,插入完毕。

get操作总结

步骤如下:

  • 判断数组是否为空,通过key定位到数组下标是否为空;
  • 判断node节点第一个元素是不是要找到,如果是直接返回;
  • 如果是红黑树结构,就从红黑树里面查询;
  • 如果是链表结构,循环遍历判断。

ConcurrentHashMapget()方法没有加synchronized锁,为什么可以不加锁?因为tablevolatile关键字修饰,保证每次获取值都是最新的。

【Hashtable的get(Object key)方法加了synchronized锁,性能较差】

总结:我们把上述流程简化一下,可以简单的认为在JDK1.8中,ConcurrentHashMap是在头节点加锁来保证线程安全的,锁的粒度相比JDK1.7的Segment来说就更小了,发生冲突和加锁的频率降低了,并发操作的性能就提高了,而且JDK1.8使用的红黑树优化了之前的固定链表,那么当数据量比较大的时候,查询效率也得到了很大的提升,从之前的O(n)优化到了O(logn)的时间复杂度,具体加锁示意图如下所示:

v2-8b6082ae13a579cc0bb38d679aacfbad_720w.png

3.HashMap为什么是线程不安全的

  • 在jdk1.7中,在多线程的环境下,扩容时会出现死循环,数据丢失 的问题
  • 在jdk1.8+中,在多线程的环境下,会发生数据覆盖的问题

原因:

  • 在jdk1.7中,HashMap扩容时使用的是头插法插入元素 。具体原因:在HashMap出发扩容时,正好两个线程同时在操作同一个链表,当线程A被挂起,线程B完成数据插入,等cpu资源释放,线程A重新执行之前的逻辑,数据已经发生改变,线程A,B,数据会形成环形链表造成死循环,数据丢失问题

  • 在jdk1.8中,HashMap扩容使用了尾插法 这样避免了死循环问题,由于多线程对HashMap进行put操作,调用了HashMap#putVal(),如果两个线程并发执行 put 操作,并且两个数据的 hash 值冲突,就可能出现数据覆盖。具体原因:线程 A 判断 hash 值位置为 null,还未写入数据、由于时间片耗尽导致被挂起,此时线程 B 正常插入数据。接着线程 A 获得时间片,由于线程 A 之前已进行hash碰撞的判断,所以此时不会再进行判断、而是直接进行插入,就会把刚才线程 B 写入的数据覆盖掉

jdk1.7扩容代码如下

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}}

在多线程下安全使用HashMap,可以使用一下策略

  1. 使用线程安全替代类 :ConcurrentHashMap集合类,强烈推荐
  2. 使用线程局部变量 : 为每个线程维护一个独立的HashMap实例,以避免线程间竞争。ThreadLocal<Map<String, Integer>> threadLocalMap = ThreadLocal.withInitial(HashMap::new);

4.HashMap和ConcurrentHashMap区别

  • 线程是否安全

  • HashMap不是线程安全的

  • concurrentHashMap是线程安全的,是通过segment分段锁-继承ReentrantLock(JDK1.7可重入锁),cas和synchronized(jdk1.8内置锁)来进行加锁,实现线程安全

  • 底层数据结构

  • HashMap:在jdk1.7时,数组+链表,jdk1.8时采用数组+链表+红黑树

  • ConcurrentHashMap:JDK1.8之前Segment+数组+链表,JDK1.8之后数组+链表+红黑树

5.HashMap和HashTable区别

Hashtable和HashMap都是 基于hash表实现的K-V结构的集合,Hashtable是jdk1.0引入的一个线程安全的集合类,内部使用数组+链表的形式来实现

从功能特性的角度来说

1、Hashtable是线程安全的(HashTable 对每个方法都增加了 synchronized),而HashMap不是

2、HashMap的性能要比Hashtable更好,因为Hashtable采用了全局同步锁来保证安全性,对性能影响较大

从内部实现的角度来说

1)Hashtable使用数组加链表,HashMap JDK1.7数组+链表、JDK1.8 数组+链表+红黑树

2)HashMap初始容量是16,Hashtable初始容量是11

3)HashMap可以使用null作为key;而Hashtable不允许 null 作为 Key,会抛出NullPointerException异常

他们两个的key的散列算法不同:Hashtable直接是使用key的hashcode对数组长度取模;而HashMap对key的hashcode做了二次散列,从而避免key的分布不均匀影响到查询性能

6.HashMap、Hashtable、ConcurrentHashMap区别

HashMap、Hashtable、ConcurrentHashMap都是 基于hash表实现的K-V结构的集合,在线程安全、底层数据结构方面有所区别

  • HashMap:线程不安全,因为HashMap中操作都没有加锁,因此在多线程环境下会导致数据覆盖之类的问题,所以,在多线程中使用HashMap是会抛出异常的
  • Hashtable:线程安全,但是Hashtable只是单纯的在添加put、删除remove、查询get方法上加synchronized,保证插入时阻塞其他线程的插入操作。虽然安全,但因为设计简单,所以性能低下(HashMap的性能要比Hashtable更好,因为Hashtable采用了全局同步锁来保证安全性,对性能影响较大)
  • ConcurrentHashMap:线程安全,ConcurrentHashMap并非锁住整个方法,而是通过原子操作和局部加锁的方法保证了多线程的线程安全,且尽可能减少了性能损耗。Segment分段锁–继承 ReentrantLock(JDK1.7重入锁)、CAS和synchronized(JDK1.8内置锁)

7.为什么 HashMap 采用拉链法而不是开放地址法?

Java 给予 HashMap 的定位是一个相对通用的散列表容器,它应该在面对各种输入的时候都表现稳定。而开发地址法相对来说容易出现数据堆积,在数据量较大时可能出现连续冲突的情况,性能不够稳定。

我们可以举个反例,在 Java 原生的数据结构中,也存在使用开放地址法的散列表 —— 就是 ThreadlLocal。因为项目中不会大量使用 ThreadLocal 线程局部存储,所以它是一个小规模数据场景,这里使用开发地址法是没问题的。

8.Map对比

实现类数据结构是否线程安全key是否可为null是否有序
HashMap哈希表结构,jdk1.7 数组+链表,jdk1.8 数组+链表+红黑树
ConcurrentHashMap哈希表结构,jdk1.7 数组+链表,jdk1.8 数组+链表+红黑树
Hashtable哈希表结构,数组+链表
LinkedHashMap继承自HashMap,数组+链表+红黑树+双重链接列表
TreeMap红黑树

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/361116.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

超简单的nodejs使用log4js保存日志到本地(可直接复制使用)

引入依赖 npm install log4js 新建配置文件logUtil.js const log4js require(log4js);// 日志配置 log4js.configure({appenders: {// 控制台输出consoleAppender: { type: console },// 文件输出fileAppender: {type: dateFile,filename: ./logs/default, //日志文件的存…

.NET C# 使用GDAL将mdb转换gdb数据

.NET C# 使用GDAL将mdb转换gdb数据 目录 .NET C# 使用GDAL将mdb转换gdb数据1 环境2 Nuget3 Code 1 环境 VisualStudio2022 .NET6 GDAL 3.8.5 2 Nuget 3 Code FeatureExtension.cs public static class FeatureExtension {[DllImport("gdal.dll", EntryPoint &…

中文+Midjourney,能描画出什么样的作品呢?保姆级上手指南送给你

中文Midjourney&#xff0c;能描画出什么样的作品呢&#xff1f; 中文版Midjourney来了&#xff01; 没有一点预热&#xff0c;Midjourney中文版&#xff08;以下简称 MJCN&#xff09;在本周开放了两次内测邀请&#xff0c;只需用 QQ 扫描邀请码&#xff0c;就可以在 QQ 频道…

VB列表框

移动是将列表框1中选中的数字移动到列表框2中。 全部是将列表框1中所有数字移动到列表框2中。 Public Class Form1Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.LoadDim i As Integer, a As IntegerRandomize()For i 0 To 9a Int(Rnd() * 90) …

51单片机STC8H8K64U通过RA8889/RA8876如何控制彩屏(源码下载)

【硬件部份】 一、硬件连接实物&#xff1a; STC8H系列单片机不需要外部晶振和外部复位&#xff0c;在相同的工作频率下&#xff0c;速度比传统的8051单片机要快12倍&#xff0c;具有高可靠抗干扰的优秀特性&#xff0c;与瑞佑的RA8889/RA8876控制芯片刚好可以完美搭配用于工…

Ubuntu24.04下安装docker,并pull ubuntu22.04,然后编译安装vpp

一、docker安装说明 解决官方源无法下载的问题 二、使用步骤 1.更新软件包索引 sudo apt update2.安装必要的软件包&#xff0c;以允许apt通过HTTPS使用仓库 sudo apt install apt-transport-https ca-certificates curl software-properties-common3.添加Docker的官方GPG…

【Chapter7】虚拟存储系统,计算机操作系统教程,第四版,左万利,王英

文章目录 [toc]零、前言一、外存资源管理1.1 外存空间划分1.2 外存空间分配1.2.1 空闲块链(慢)1.2.2 空闲块表(UNIX)1.2.3 字位映像图 1.3 进程与外存对应关系 二、虚拟页式存储系统2.1 基本原理2.2 内存页框分配策略2.3 外存块的分配策略2.4 页面调入时机2.5 置换算法2.5.1 最…

探索AI世界系列:俗说AI智能体

AI agent&#xff0c;翻译为中文就是AI智能体。 什么是AI智能体呢&#xff1f; 一&#xff0c;GPT对AI智能体的定义 AI智能体&#xff0c;即人工智能体&#xff08;Artificial Intelligence Agent&#xff09;&#xff0c;是具有自主性、学习能力和推理能力的计算机程序。 …

手把手教你使用kimi创建流程图【实践篇】

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 引言 在昨日的文章中&#xff0c;我们介绍了如何使用Kimi生成论文中的流程图。今天&#xff0c;我们将更进一步&#xff0c;通过实践案例来展示Kimi在生成流程图方面的应用。这不仅将加…

基于 JuiceFS 构建高校 AI 存储方案:高并发、系统稳定、运维简单

中山大学的 iSEE 实验室&#xff08;Intelligence Science and System) Lab&#xff09;在进行深度学习任务时&#xff0c;需要处理大量小文件读取。在高并发读写场景下&#xff0c;原先使用的 NFS 性能较低&#xff0c;常在高峰期导致数据节点卡死。此外&#xff0c;NFS 系统的…

[SAP ABAP] 汇总内表数据

在加入新数据记录时&#xff0c;将非数值字段具有相同内容记录的数值字段汇总 语法格式 COLLECT <wa> INTO <itab>. <wa>&#xff1a;代表工作区 <itab>&#xff1a;代表内表 示例1 结果显示&#xff1a;

django restframework 多对多模型 —— python

模型 图书和作者是多对多关系 class Book(models.Model):book_namemodels.CharField(max_length40)pricemodels.DecimalField(max_digits4,decimal_places2)publishmodels.ForeignKey(to"Publish",on_deletemodels.CASCADE,related_name"publish")authorm…

ModuleNotFoundError: No module named ‘gdal‘

第一步检查gdal包是否正确安装&#xff1a; conda list 已经安装显示如下 若查找不到&#xff1a;请按照此说明步骤进行安装&#xff1a;ModuleNotFoundError: No module named ‘osgeo‘_modulenotfounderror: no module named osgeo-CSDN博客 第二步&#xff1a;检查是否可以…

VSCode运行前端项目-页面404

背景&#xff1a; 通过VSCode运行前端本地项目&#xff0c;运行成功后打开本地链接&#xff1a;http://1x.xxx.x.xxx:9803/ &#xff0c;发现打开的页面重定向到404&#xff1a;http//1xx.xxx.x.xxx:9803/404&#xff1b; 并且控制台出现&#xff1a;Failed to load resource: …

C语言 | 文件操作(下)【必收藏】

文件操作&#xff08;下&#xff09; 5、文件的顺序读写5.1 顺序读写函数介绍5.1.1 fputc与fgetc5.1.2 fputs与fgets5.1.3 fprintf与fscanf5.1.4 fread与fwrite 5.2 对比一组函数 6. 文件的随机读写6.1 fseek6.2 ftell6.3 rewind 7. 文件读取结束的判定7.1 被错误使用的feof 8.…

Redis 备份恢复以及数据迁移

昨晚老板突然在群里发了一张图片&#xff0c;说昨天才用的&#xff0c;怎么今天还要登录&#xff1f;相关人赶紧看看。 我心想让你登录就登录呗&#xff0c;哪来那么多事&#xff1f;本想洗洗睡了。老大突然微信问我说&#xff0c;是不是 Redis 出问题了&#xff1f;怎么用户…

筑梦未来:高考后,专业与学校的天秤两端

前言 2024 年高考落幕&#xff0c;几人欢喜几人愁&#xff0c;作为一个过来人&#xff0c;希望每一个努力的悻悻学子都能得偿所愿&#xff0c;不负年华&#xff0c;报的心仪的志愿。 接下来我将从三个方向进行一些分析建议&#xff0c;在专业与大学排名间做出适当的权衡。 专…

智能语音抽油烟机:置入WTK6900L离线语音识别芯片 掌控厨房新风尚

一、抽油烟机语音识别芯片开发背景 在繁忙的现代生活中&#xff0c;人们对于家居生活的便捷性和舒适性要求越来越高。传统的抽油烟机操作方式往往需要用户手动调节风速、开关等功能&#xff0c;不仅操作繁琐&#xff0c;而且在烹饪过程中容易分散注意力&#xff0c;增加安全隐…

【深度学习】基于因果表示学习的CITRIS模型原理和实验

1.引言 1.1.本文的主要内容 理解动态系统中的潜在因果因素&#xff0c;对于智能代理在复杂环境中进行有效推理至关重要。本文将深入介绍CITRIS&#xff0c;这是一种基于变分自编码器&#xff08;VAE&#xff09;的框架&#xff0c;它能够从时间序列图像中提取并学习因果表示&…

Kafka入门-基础概念及参数

一、Kafka术语 Kafka属于分布式的消息引擎系统&#xff0c;它的主要功能是提供一套完备的消息发布与订阅解决方案。可以为每个业务、每个应用甚至是每类数据都创建专属的主题。 Kafka的服务器端由被称为Broker的服务进程构成&#xff0c;即一个Kafka集群由多个Broker组成&#…