目录

1.了解HashMap底层插入原理

2.ConcurrentHashMap 是什么？

HashTable的实现

3.ConcurrentHashMap 1.7和1.8的区别

4、JDK1.7 中的ConcurrentHashMap实现原理

6、JDK1.8中的ConcurrentHashMap

7.链表转红黑树条件

1.8 put方法

8.并发扩容

9.总结

---

首先呢，想要了解ConcurrentHashMap， 你得先了解HashMap，

1.了解HashMap底层插入原理

(1)  put方法插入数据时，它的底层是putVal方法，该方法有五个参数

key 的hash值===（key的低16位异或key的高16位）、key、value、onlyIfAbsent默认为false，为true的话表明不能修改已存在的值、evict(不用关注)

(2)  进入putVa方法后，会先判断数组是否为空，若为空，会先调用resize的值来进行扩容

(3)  若不为空的话，根据hash(key)找到key在数组中的下标位置，判断当前下标位置是否    已存元素，若没存，该key的value值直接存进该下标位置，判断是否达到阈值的大小，若达到 则resize进行扩容，否则数组不变

(4) 若当前下标位置已经存了一个元素，

则判断 新值的key是否等于已存值的key，若等，则直接做值的覆盖处理，

否则（hash值相等 key值不等），如果底层是红黑树，则将该数直接插进红黑树中，

如果底层是链表，就把新节点插到链表的尾部，而后判断是否达到树化的条件，若达到，则将链表转化为红黑树

总结：数组+链表+红黑树

2.ConcurrentHashMap 是什么？

​ ConcurrentHashMap 是JDK1.5之后新出一个在并发包里面类，包名叫 java.util.current；简称JUC，既然叫并发包，那肯定就意味着它是线程安全的，里面有一个概念：分而治之，这是ConcurrentHashMap的核心思想，并且在jdk7里面用到一个非常新颖且时髦的技术 ：分段锁；由此可见，ConcurrentHashMap的出现就是为了高并发而准备的；并且使用方式和HashMap一样，用key-value方式存储数据；连方法名都一样；只不过区别是一个线程安全，一个线程不安全。

HashTable的实现

但是不对啊，线程的安全的map不是已经有HashTable了吗？为什么还要正处一个ConcurrentHashMap出来呢？这是个好问题，首先我们先来看看HashTable的实现；

HashTable 的每个修饰为 public 的方法都加上了 synchronized 的同步方法，也就是说，不管我对map的增删改查都会上锁，也正因为它的锁简单粗暴，不管你干嘛我都给你锁住，造成一个原因就是效率低下；高并发场景下，只要有一个线程对HashTable操作，其他线程都会进入阻塞状态，线程数量太多的情况下会造成响应时间缓慢

3.ConcurrentHashMap 1.7和1.8的区别

1、整体结构

1.7：Segment + HashEntry + Unsafe

1.8: 移除Segment，使锁的粒度更小，Synchronized + CAS + Node + Unsafe(Unsafe提供了compareAndSwapObject、compareAndSwapInt等方法，用于实现CAS（Compare-And-Swap）操作。这些操作在ConcurrentHashMap中被广泛用于无锁更新，例如更新节点、计数器等。)

2、put（）

1.7：先定位Segment，再定位桶，put全程加锁，没有获取锁的线程提前找桶的位置，并最多自旋64次获取锁，超过则挂起（头插）。

1.8：由于移除了Segment，类似HashMap，可以直接定位到桶，拿到first节点后进行判断，1、为空则CAS插入；2、为-1则说明在扩容，则跟着一起扩容；3、else则加锁put（类似1.7）

3、get（）

基本类似，由于value声明为volatile，保证了修改的可见性，因此不需要加锁。

1.7

public V get(Object key) {Segment<K,V> s; // manually integrate access methods to reduce overheadHashEntry<K,V>[] tab;int h = hash(key);//根据哈希值确定 segment 的位置long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;//使用 Unsafe 类的 getObjectVolatile 方法获取对应的 Segment：if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&(tab = s.table) != null) {//计算 key 在 table 中的位置，并获取对应的 HashEntry：//遍历 HashEntry 链表，查找匹配的 key：for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);e != null; e = e.next) {K k;if ((k = e.key) == key || (e.hash == h && key.equals(k)))return e.value;}}return null;
}

4、resize（）

1.7：跟HashMap步骤一样，只不过是搬到单线程中执行，避免了HashMap在1.7中扩容时死循环的问题，保证线程安全。

1.8：支持并发扩容，HashMap扩容在1.8中由头插改为尾插（为了避免死循环问题），ConcurrentHashmap也是，迁移也是从尾部开始，扩容前在桶的头部放置一个hash值为-1的节点，这样别的线程访问时就能判断是否该桶已经被其他线程处理过了。

5、size（）

1.7：很经典的思路：计算两次哈希，如果不变则返回计算结果，若不一致，则锁住所有的Segment求和。

1.8：用baseCount来存储当前的节点个数，这就设计到baseCount并发环境下修改的问题

4、JDK1.7 中的ConcurrentHashMap实现原理

​ 在jdk1.7及其以下的版本中，结构是用Segments数组 + HashEntry数组 + 链表实现的，

Segment 继承了ReentrantLock，所以它除了是一个独占锁之外，还是一种可重入锁（ReentrantLock)，多个锁同时存在时会自动合并为一把锁来操作，ConcurrentHashMap 使用了分段锁技术来保证线程安全，它把数据分成一段一段的，也就是Segments [] 数组，Segments数组中每一个元素就是一个段，每个元素里面又存储了一个Enter数组，这个enter数组就相当于是一个HashMap，所以在高并发场景下，每次修改内容时只会锁住segment数组的每个元素，多个元素之间各自负责自己的锁，分段后，多个段（元素）之间的插入修改不会有任何影响，既做到了并发，又提升了效率；按照默认的并发级别 concurrentLevel 来说 ，默认是16，所以理论上支持同时16个线程并发操作，并且还互不冲突

put方法

通过源码可以看到，在进入put方法后，会先判断key和value是否为空，ConcurrentHashMap是不允许key/value为空的；下一步就是定位segment数组的下标位置，通过hash按位与算法得出，并确保segments下标位置的HashEnter数组已初始化；（头插）

public V put(K key, V value) {Segment<K,V> s;//concurrentHashMap不允许key/value为空if (value == null)throw new NullPointerException();//hash函数对key的hashCode重新散列，避免差劲的不合理的hashcode，保证散列均匀int hash = hash(key);//返回的hash值无符号右移segmentShift位与段掩码进行位运算，定位segmentint j = (hash >>> segmentShift) & segmentMask;if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck(segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegments = ensureSegment(j);return s.put(key, hash, value, false);}

get方法

get方法无需加锁，由于其中涉及到的共享变量都使用volatile修饰，volatile可以保证内存可见性，且防止了指令重排序，所以不会读取到过期数据。

size方法

size操作是先统计2次，如果2次的结果不一样，就代表着有线程正在修改数据，然后对put、remove、clean进行加锁后，在统计一次，之后unlock。所以最多会统计3次，

6、JDK1.8中的ConcurrentHashMap

​ 在JDK1.8中，对ConcurrentHashMap的结构做了一些改进，其中最大的区别就是jdk1.8抛弃了Segments数组，摒弃了分段锁的方案，而是改用了和HashMap一样的结构操作，也就是数组 + 链表 + 红黑树结构，比jdk1.7中的ConcurrentHashMap提高了效率，在并发方面，使用了cas + synchronized的方式保证数据的一致性；因为去掉了分段锁，所以在高并发时锁住的就是数组的节点了，使得结构更加简单了；

7.链表转红黑树条件

​ 要知道，链表在遍历的时候一定是从头遍历到尾的，如果很不巧，get方法中我们要找的元素恰好在尾部，那每次获取元素的时候都得遍历一次链表，所以为了避免链表过长的情况发生，在jdk1.8中，在map的结构达到一定条件之后，将会把链表自动转为红黑树的结构，这2个条件分别是：

数组中任意一个链表的长度超过8个

数组长度大于64个时

转为红黑树后的结构如下图

1.8 put方法

jdk8中的ConcurrentHashMap 的结构看起来虽然简单了，但是源代码却不那么容易读懂，我们先来看看put方法都做了哪些逻辑

8.并发扩容

jdk8中的ConcurrentHashMap最复杂的就是扩容机制了，因为它不是一个个地扩容，它可以并发扩容，也就是同时进行多个节点的扩容，在默认情况下，每个cpu可以负责16个元素的长度进行扩容，比如node数组的长度为32，那么线程A负责0-16下标的数组扩容， 线程B负责17-31下标的扩容，并发扩容在transfer方法中进行，这样，2个线程分别负责高16位和低16位的扩容，不管怎样都不会产生冲突，提升了效率；

3.4、计算数组索引公式

​ 当我们put一个元素之后，把这个元素放到数组的哪个元素下是需要通过计算得出的，在此之前，先通过 spread() 方法计算出hash值，

计算Hash值公式： key的hashcode的低十六位 异或 高十六位，然后与Hash_bits相与（与hashmap唯一不同）

// 用16进制表示，转为数字后数值为：2147483647   

static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

   

//计算hash值

static final int spread(int h) {

    return (h ^ (h >>> 16)) & HASH_BITS;

}

9.总结

JDK7的put过程

首先对key进行第一次hash，通过hash值确定segment的值；

如果此时segment未初始化，则利用自旋CAS操作来创建对应的segment；

获取当前segment的hashentry数组后进行对key进行第2次hash，通过值确定在hashentry数组的索引位置。

通过继承ReetrantLock的tryLock方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该segment的锁，那么当前线程会以自旋的方式去继续调用tryLock方法去获取锁，超过指定次数就挂起，等待唤醒。

然后对当前索引的hashentry链进行遍历，如果有重复的key，则替换；如果没有重复的，则插入到链头。

释放锁。

JDK8的put过程

如果没有初始化就先调用initTable()方法对其初始化；

对key进行hash计算，求得值没有哈希冲突的话，则利用自旋CAS操作来进行插入数据；

如果存在hash冲突，那么就加synchronized锁来保证线程安全

如果存在扩容，那么就去协助扩容

加完数据之后，再判断是否还需要扩容

JDK7的get过程

与JDK7的put过程类似，也是需要两次hash，不过不需要加锁，因为将存储元素都标记成了volatile，对内存都是可见性的。

JDK8的get过程

计算hash值，定位table索引位置，也是不需要加锁，通过volatile关键字进行保证了。

JDK7的扩容过程

其Segment初始化之后就不能扩容，所以扩容都是在其的hashentry[]数组中，而其继承了ReentrantLock的可重入锁，保证了线程安全性。

JDK8的扩容过程(见上)

JDK7的求解size过程

size操作就是遍历了两次所有的segments, 每次记录segment的modCount值，然后将两次的modCount进行比较，如果相同，则表示期间没有发生过写入操作，就将原先遍历的结果返回。

如果经判断发现两次统计出的modCount并不一致，要重新启用全部segment加锁的方式来进行count的获取和统计，这样在此期间每个segment都被锁住，无法进行其他操作，统计出来的count自然很准确。

JDK8的求解size过程

JDK8求解size有两个重要变量：一个是baseCount用于记录节点的个数，是个volatile变量；counterCells是一个辅助baseCount计数的数组，每个counterCell存着部分的节点数量，这样做的目的就是尽可能地减少冲突。ConcurrentHashMap节点的数量=baseCount+counterCells每个cell记录下来的节点数量。统计数量的时候并没有加锁。

总体的原则就是：先尝试更新baseCount，失败再利用CounterCell。

通过CAS尝试更新baseCount ，如果更新成功则完成，如果CAS更新失败会进入下一步

线程通过随机数ThreadLocalRandom.getProbe() & (n-1) 计算出在counterCells数组的位置，如果不为null，则CAS尝试在couterCell上直接增加数量，如果失败，counterCells数组会进行扩容为原来的两倍，继续随机，继续添加（说实话没看懂）