ConcurrentHashMap是一个可以用于并发环境的集合,在jdk8中实现的原理是CAS+synchronized
我们知道,HashMap是无法保证线程安全性的,如果在并发环境下插入一个HashMap,哈希桶数组扩容时,有可能会造成链表出现环(美团技术的文章有详解)。若要保证线程安全性,就得使用ConcurrentHashMap。而ConcurrentHashMap在JDK 7和JDK 8中的锁机制设计有相当大的区别,本文来简单谈谈(其实也是老生常谈了)。
ConcurrentHashMap是HashMap的线程安全版本,内部也是使用(数组 + 链表 + 红黑树)的结构来存储元素。
HashSet 不重复主要add 方法实现,使用 add 方法找到是否存在元素,存在就不添加,不存在就添加。HashSet 主要是基于HashMap 实现的,HashMap 的key就是 HashSet 的元素,HashSet 基于hash 函数实现元素不重复。首先看 add 方法:
是用key计算hashCode,然后与key做无符号右移16位 , 是为了让高位移动,让hash均匀
我们使用 put(key, value) 存储对象到 HashMap 中,使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时,我们先对键调用 hashCode() 方法,计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。
并发环境下HashMap是不安全的,容易造成并发修改异常或者死锁现象 而Collections下提供的synchionizedMap虽然因为加了synchionized而变得安全,却也因此极大的降低了性能 由于以上情况,就使得ConcurrentHashMap应运而生
因为通常声明map集合时不会指定大小,或者初始化的时候就创建一个容量很大的map对象,所以这个通过容量大小与key值进行hash的算法在开始的时候只会对低位进行计算,虽然容量的2进制高位一开始都是0,但是key的2进制高位通常是有值的,因此先在hash方法中将key的hashCode右移16位在与自身异或,使得高位也可以参与hash,更大程度上减少了碰撞率。
ConcurrentHashMap 是 HashMap 的多线程版本,HashMap 在并发操作时会有各种问题,比如死循环问题、数据覆盖等问题。而这些问题,只要使用 ConcurrentHashMap 就可以完美解决了,那问题来了,ConcurrentHashMap 是如何保证线程安全的?它的底层又是如何实现的?接下来我们一起来看。
注意:这里的加锁操作是针对某个具体的 Segment,锁定的是该 Segment 而不是整个 ConcurrentHashMap。因为插入键 / 值对操作只是在这个 Segment 包含的某个桶中完成,不需要锁定整个ConcurrentHashMap。此时,其他写线程对另外 15 个Segment 的加锁并不会因为当前线程对这个 Segment 的加锁而阻塞。同时,所有读线程几乎不会因本线程的加锁而阻塞(除非读线程刚好读到这个 Segment 中某个 HashEntry 的 value 域的值为 null,此时需要加锁后重新读取该值)。 相比较于 HashTable 和由同步包装器包装的 HashMap每次只能有一个线程执行读或写操作,ConcurrentHashMap 在并发访问性能上有了质的提高。在理想状态下,ConcurrentHashMap 可以支持 16 个线程执行并发写操作(如果并发级别设置为 16),及任意数量线程的读操作。
本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和 null 值,在计算哈键的哈希值时,null 键哈希值为 0。HashMap 并不保证键值对的顺序,这意味着在进行某些操作后,键值对的顺序可能会发生变化。另外,需要注意的是,HashMap 是非线程安全类,在多线程环境下可能会存在问题。
HashMap类中有一个非常重要的字段,就是Node[] table,即哈希桶数组:
之前一直都在使用 HashMap 做一些操作,心里常常默认 HashMap 很快 ,从未做过深究。现在看过源码之后才发现 HashMap 的效率并没有想象中的那么高,O(1) O(n) O(tab数据length * 链表length) 均有可能,并且也不太适合存储大量数据。
《HashMap》中已经分析了HashMap的实现,jdk1.7与jdk1.8的实现有很多区别,现在我们分析一下两个版本的差异:
HashMap的底层数据结构是数组+链表+红黑树,数组的作用显而易见,时间复杂度最低O(1),默认大小是16,数组的下标索引是通过key的hashcode计算出来的,当多个key计算出的hashcode相同时,数组元素就会转化为链表,时间复杂度升为O(n),当链表的长度大于8并且数组的大小超过64时,链表会转化为红黑树,时间复杂度为O(log(n)),从源码角度来分析下HashMap的几个核心方法。
在jdk1.7以前,HashMap在进行扩容时采用的是头插法,可能当时别人觉得这样比较高效,但是也带来了线程安全问题。 刚开始时HashMap是这样的:
Set是一个接口,最常用的实现类就是HashSet,今天我们就拿HashSet为例。
重写equals是为了在业务逻辑上判断实例之间是否相等。重写hascode是为了让集合快速判重。
Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就是HashSet,今天我们就拿HashSet为例。 先简单介绍一下HashSet类 HashSet类实现了Set接口, 其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素,因此具有比较好的读取和查找性能。 先看下HashSet的几个构造方法。 // 默认构造函数 底层创建一个HashMap
在面试的时候,ConcureentHashMap在JDK1.7的时候线程安全底层具体实现方式是什么?
上一节主要讲述了HashMap的一些基础属性和构造方法,本节将会讲述HashMap的核心方法。
使用concurrentHashMap之前先了解一下HashMap,在该文章中会看到HashMap在并发场景下是不安全的。ConcurrentHash(1.8) 为了解决HashMap不安全的问题,采用了CAS+synchronized技术,底层实现也是使用数组+链表+红黑树。
Java中的HashMap是我们在开发中经常使用的集合之一,它提供了基于哈希表的数据存储方式,使得对数据的插入、删除和查找操作都具有较高的效率。在本文中,我们将深入解析HashMap中的putVal方法,揭示其内部工作原理。通过对代码的逐行分析,我们不仅能够更好地理解HashMap的设计和实现,还能提高我们在实际开发中对HashMap的使用水平。
环境是java8,上述hashMap和ConcurrentHashMap在java7的时候实现会有不同。
put方法其实是调用了putVal方法的,调用方法的同时把计算好的key的哈希值传入,putVal方法:
ConcurrentHashMap是支持并发的HashMap类,可以在多线程环境下保证线程安全。ConcurrentHashMap的核心思想就是减小锁的粒度。传统的线程安全的Hashtable在同步时采用了synchronized关键字,所有对Hashtable的读写操作都要先获取对象锁,在锁竞争比较激烈的情况下会导致性能很低。ConcurrentHashMap在此基础上采用和分段的策略,将一个HashMap最多分为16个段(Segment),对不同段上的操作可以并发执行,只有在同一个段上的读写才使用加锁的策略。通过这种减小锁粒度的方式,大大提高了性能。如ConcurrentHashMap的put方法源码如下:
HashMap中实际是维护了一个Node数组,用来存储数据,下面看一下Node源码:
HashMap 源码很长,面试的问题也非常多,但这些面试问题,基本都是从源码中衍生出来的,所以我们只需要弄清楚其底层实现原理,回答这些问题就会游刃有余。
到目前为止,我们在Java世界里看到了两种实现key-value的数据结构:Hash、TreeMap,这两种数据结构各自都有着优缺点。 Hash表:插入、查找最快,为O(1);如使用链表实现则可实现无锁;数据有序化需要显式的排序操作。 红黑树:插入、查找为O(logn),但常数项较小;无锁实现的复杂性很高,一般需要加锁;数据天然有序。 然而,这次介绍第三种实现key-value的数据结构:SkipList。SkipList有着不低于红黑树的效率,但是其原理和实现的复杂度要比红黑树简单多了。 SkipList
SkipListSkipList的特性SkipList的查找SkipList的插入SkipList的删除ConcurrentSkipListMapput操作get操作remove操作size操作
线性,平方显然很容被人猜出规律,所以最终是随机,那么是不是存在随机会出现取模的值相等的情况?
本文分为两个部分,第一个是对跳表(SKipList)这种数据结构的介绍,第二部分则是对Java中ConcurrentSkilListMap的源码解读.
开始想到单字符,比如a、b、c、d、e这类字符,但是如果一个一个试的话特别繁琐,想到了ASKII码:
了解ConcurrentHashMap 实现原理,建议首先了解下HashMap实现原理。 HashMap 源码解析(JDK1.8) 为什么要用ConcurrentHashMap HashMap线程不安全,而Hashtable是线程安全,但是它使用了synchronized进行方法同步,插入、读取数据都使用了synchronized,当插入数据的时候不能进行读取(相当于把整个Hashtable都锁住了,全表锁),当多线程并发的情况下,都要竞争同一把锁,导致效率极其低下。而在JDK1.5后为了改进Hashta
背景知识 哈希冲突 哈希是指通过某种方法把数据转变成特定的数值,数值根据mod对应到不同的单元上。比如在Java中,字符串就是通过每个字符的编码来计算、数字是本身对应的值等等,不过就算是再好的哈希方法
然后就是调用putMapEntries方法,第二个参数其实可以看作细节,个人认为它和HashMap的子类LinkedHashMap有关,evict是逐出的意思,如果基于LinkedHashMap实现LRU缓存的话,这个evict参数正好就用上了。
其余分支我们后面可以细讲,现在简略讲下分支2,它使用cas无锁模式将元素添加到空桶,代码如下:
前言 还是需要从头阅读下HashMap的源码。目标在于更好的理解HashMap的用法,学习更精炼的编码规范,以及应对面试。 它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使H
HashMap默认的容量是DEFAULT_INITIAL_CAPACITY,16。
整体流程跟HashMap比较类似,大致是以下几步: (1)如果桶数组未初始化,则初始化; (2)如果待插入元素所在的桶为空,则尝试把此元素直接插入到桶的第一个位置; (3)如果正在扩容,则当前线程一起加入到扩容的过程中; (4)如果待插入的元素所在的桶不为空且不在迁移元素,则锁住这个桶(分段锁); (5)如果当前桶中元素以链表方式存储,则在链表中寻找该元素或者插入元素; (6)如果当前桶中元素以红黑树方式存储,则在红黑树中寻找该元素或者插入元素; (7)如果元素存在,则返回旧值; (8)如果元素不存在,整个Map的元素个数加1,并检查是否需要扩容; 添加元素操作中使用的锁主要有(自旋锁 + CAS + synchronized + 分段锁)。 为什么使用synchronized而不是ReentrantLock? 因为synchronized已经得到了极大地优化,在特定情况下并不比ReentrantLock差。
在日常开发工作中,HashMap是使用频率相当高的一个工具,同时「HashMap」的底层实现和原理,也成了面试题中的常客。最近又翻看了一下源码,做个记录。(本文都是基于jdk1.8的源码)
我们都知道HashSet存放的元素是不允许重复的,那么HashSet又是是如何保证元素不可重复的,你知道吗?
今天我们看看JDK1.8中的HashMap的源码,我们就重点看一下其中的常用方法的源码
当我们put的时候,首先计算Key的hash值,这里调用了hash方法,hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以hash函数的一个作用是,高16位不变,低16位和高16位做一个异或,目的是减少碰撞,按照源码中的注释,因为bucket数据大小是2的幂,计算index=(table.length-1)&hash,如果不做hash处理,相当于散列生效的只有几个低bit位,为了减少散列的碰撞,所以使用高16bit和低16bit异或处理来减少碰撞。
所有的方法皆为同步方法,实现线程安全。底层为Object数组,初始容量为10,每次递增为原来的2倍
JDK 1.8中,Hash家族有这么一些存在,HashMap,HashTable,LinkedHashMap,ConcurrentHashMap。这里面支持线程安全的有HashTable以及ConcurrentHashMap。对Hash有一个基本了解可以参考本人的从Hash到一致性Hash原理(深度好文) 。
本文详细解析了Java中线程安全的HashMap实现——ConcurrentHashMap的工作原理。通过深入分析其内部源码,我们阐述了ConcurrentHashMap如何利用分段锁、CAS操作、扩容机制、近似计数等技术实现高并发和线程安全。同时,我们还提供了一些实际的使用示例,帮助读者更好地理解和掌握ConcurrentHashMap的使用方法。
ConcurrentHashMap虽然为并发安全的组件,但是使用不当仍然会导致程序错误。我们这里通过一个简单的案例来复现这些问题,并给出开发时如何避免的策略。
领取专属 10元无门槛券
手把手带您无忧上云