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，更大程度上减少了碰撞率。
注意：这里的加锁操作是针对某个具体的 Segment，锁定的是该 Segment 而不是整个 ConcurrentHashMap。因为插入键 / 值对操作只是在这个 Segment 包含的某个桶中完成，不需要锁定整个ConcurrentHashMap。此时，其他写线程对另外 15 个Segment 的加锁并不会因为当前线程对这个 Segment 的加锁而阻塞。同时，所有读线程几乎不会因本线程的加锁而阻塞（除非读线程刚好读到这个 Segment 中某个 HashEntry 的 value 域的值为 null，此时需要加锁后重新读取该值）。 相比较于 HashTable 和由同步包装器包装的 HashMap每次只能有一个线程执行读或写操作，ConcurrentHashMap 在并发访问性能上有了质的提高。在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设置为 16），及任意数量线程的读操作。
ConcurrentHashMap 是 HashMap 的多线程版本，HashMap 在并发操作时会有各种问题，比如死循环问题、数据覆盖等问题。而这些问题，只要使用 ConcurrentHashMap 就可以完美解决了，那问题来了，ConcurrentHashMap 是如何保证线程安全的？它的底层又是如何实现的？接下来我们一起来看。
HashMap类中有一个非常重要的字段，就是Node[] table，即哈希桶数组:
之前一直都在使用 HashMap 做一些操作，心里常常默认 HashMap 很快 ，从未做过深究。现在看过源码之后才发现 HashMap 的效率并没有想象中的那么高，O(1) O(n) O(tab数据length * 链表length) 均有可能，并且也不太适合存储大量数据。
《HashMap》中已经分析了HashMap的实现，jdk1.7与jdk1.8的实现有很多区别，现在我们分析一下两个版本的差异：
本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中，底层基于散列算法实现。HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。
HashMap的底层数据结构是数组+链表+红黑树，数组的作用显而易见，时间复杂度最低O(1)，默认大小是16，数组的下标索引是通过key的hashcode计算出来的，当多个key计算出的hashcode相同时，数组元素就会转化为链表，时间复杂度升为O(n)，当链表的长度大于8并且数组的大小超过64时，链表会转化为红黑树，时间复杂度为O(log(n))，从源码角度来分析下HashMap的几个核心方法。
在jdk1.7以前，HashMap在进行扩容时采用的是头插法，可能当时别人觉得这样比较高效，但是也带来了线程安全问题。 刚开始时HashMap是这样的：
重写equals是为了在业务逻辑上判断实例之间是否相等。重写hascode是为了让集合快速判重。
Set是一个接口，最常用的实现类就是HashSet，今天我们就拿HashSet为例。
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技术，底层实现也是使用数组+链表+红黑树。
环境是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原理(深度好文) 。
HashMap的相关面试题一直是BAT大厂面试官的高频面试题，笔者最近接到的阿里和开源中国面试官的面试题中都有问到有关HashMap底层实现的一些面试题，当时回答的不是很好。于是抽个时间来捋一捋HashMap的相关面试题并分析其中的部分源码，希望对我的读者粉丝们也会有一定的帮助。
ConcurrentHashMap虽然为并发安全的组件，但是使用不当仍然会导致程序错误。我们这里通过一个简单的案例来复现这些问题，并给出开发时如何避免的策略。
Java提供了不同层面的线程安全支持。在传统集合框架内部，除了 Hashtable等同步容器，还提供了所谓的同步包装器(Synchronized Wrapper)，我们可以调用Collections工具类提供的包装方法，来获取一个同步的包装容器(如 Collections.synchronizedMap），但是它们都是利用非常粗粒度的同步方式，在高并发情况下，性能比较低下。其实可以利用并发包提供的线程安全容器。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
