【面试题系列】CurrentHashMap 的实现原理

CurrentHashMap 的实现原理

JDK8 实现原理

1，实现方式：synchronized+CAS+HashEntry+红黑树

2，线程安全：内部大量采用 CAS 机制操作+Synchronized 保证线程安全

3，数据结构：数组+链表+红黑树

4，锁颗粒度：Node：保存 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 修饰，保证并发的可见性。

5.查询时间复杂度：遍历红黑树 O(logN)。

其并发数量为数组长度

JDK1.7 实现原理

1，实现方式：数组+Segment+分段锁的方式实现。

2，线程安全：采用 segment 的分段锁机制实现线程安全，其中 segment 继承 ReentrantLock

3，数据结构：数组+Segment 分段锁的数据结构

4，锁颗粒度：对需要进行数据操作的 Segment 加锁

5，查询时间复杂度：遍历链表 O(n)。

其并发为 16，因为分了 16 个 Segment 分段锁

SegmentConcurrentHashMap 中的分段锁称为 Segment，它即类似于 HashMap 的结构，即内部拥有一个 Entry 数组，数组中的每个元素又是一个链表,同时又是一个 ReentrantLock（Segment 继承了 ReentrantLock）。

CAS

AS 是 compare and swap 的缩写，即所说的比较交换。

cas 是一种基于锁的操作，而且是乐观锁。

在 java 中锁分为乐观锁和悲观锁。

悲观锁：是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。

乐观锁：采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加 version 来获取数据，性能较悲观锁有很大的提高。

CAS 操作包含三个操作数：

1. 内存位置（V）

2. 预期原值（A）

3. 和新值(B)

如果内存地址里面的值和 A 的值是一样的，那么就将内存里面的值更新成 B。

CAS 是通过无限循环来获取数据的：如果在第一轮循环中，a 线程获取地址里面的值被 b 线程修改了，那么 a 线程需要自旋，到下次循环才有可能机会执行。

Synchronized 原理：

Synchronized 进过编译，会在同步块的前后分别形成 monitorenter 和 monitorexit 这个两个字节码指令。

在执行 monitorenter 指令时，首先要尝试获取对象锁。如果这个对象没被锁定，或者当前线程已经拥有了那个对象锁，把锁的计算器加 1。

相应的，在执行 monitorexit 指令时会将锁计算器就减 1，当计算器为 0 时，锁就被释放了。如果获取对象锁失败，那当前线程就要阻塞，直到对象锁被另一个线程释放为止。

monitorenter ：

每个对象有一个监视器锁（monitor）。当 monitor 被占用时就会处于锁定状态，线程执行 monitorenter 指令时尝试获取 monitor 的所有权，过程如下：

1、如果 monitor 的进入数为 0，则该线程进入 monitor，然后将进入数设置为 1，该线程即为 monitor 的所有者。

2、如果线程已经占有该 monitor，只是重新进入，则进入 monitor 的进入数加 1.

3.如果其他线程已经占用了 monitor，则该线程进入阻塞状态，直到 monitor 的进入数为 0，再重新尝试获取 monitor 的所有权。

monitorexit：

执行 monitorexit 的线程必须是 objectref 所对应的 monitor 的所有者。

指令执行时，monitor 的进入数减 1，如果减 1 后进入数为 0，那线程退出 monitor，不再是这个 monitor 的所有者。

其他被这个 monitor 阻塞的线程可以尝试去获取这个 monitor 的所有权。