写点什么

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

作者:颜淡慕潇
  • 2022-11-02
    上海
  • 本文字数:1213 字

    阅读完需:约 4 分钟

【面试题系列】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 的所有权。

发布于: 刚刚阅读数: 7
用户头像

颜淡慕潇

关注

欢颜如炼,悲苦如戟; 浓尽必枯,淡者屡深 2019-04-14 加入

后端技术领域

评论

发布
暂无评论
【面试题系列】CurrentHashMap的实现原理_Java_颜淡慕潇_InfoQ写作社区