JoJo的个人博客

记录精彩的程序人生

目录
ConcurentHashMap
/  

ConcurentHashMap

Jdk1.7 实现

使用分段锁机制,由一个Segment数组和多个HashEntry数组组成

Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,而每一个Segment元素存储的是HashEntry数组+链表。

初始化

Segment的大小size默认为16

put 操作

ConcurrentHashMap在进行put操作时,先通过keyhash值来定位在Segment数组的位置。插入的时候,通过继成ReentrantLock类的tryLock()方法尝试获取锁,如果获取成功就直接插入,如果获取失败,就循环调用trylock()方法尝试获取锁,超过指定次数就调用lock()方法阻塞等待

get 操作

Key通过 Hash 之后定位到具体的Segment ,再通过一次Hash 定位到具体的元素上

由于HashEntry中的value 属性是用 volatile 关键词修饰的,保证了内存可见性,所以每次获取时都是最新值。

ConcurrentHashMapget 方法是非常高效的,因为整个过程都不需要加锁

size 操作

第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMapsize,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的

第二种方案是如果第一种方案不符合,他就会给每个Segment 加上锁,然后计算ConcurrentHashMapsize返回

Jdk1.8 实现

JDK1.8的实现抛弃了原有的 Segment分段锁,而采用了 CAS + synchronized 来保证并发安全性。

ConcurrentHashMap 的数据结构(数组+链表+红黑树),桶中的结构可能是链表,也可能是红黑树,红黑树是为了提高查找效率

Node

存储结构的基本单元为 Node,继承于HashMap中的 Entry,用于存储数据

TreeNode

TreeNode 继承与 Node,但是数据结构换成了二叉树结构,它是红黑树的数据的存储结构,用于红黑树中存储数据,当链表的节点数大于8时会转换成红黑树的结构

put 操作

在并发处理中使用的是乐观锁,当有冲突的时候才进行并发处理

  • 如果没有初始化先初始化table
  • 如果对应位置没有元素,尝试CAS自旋插入
  • 如果需要扩容先进行扩容
  • 否则 通过synchronized加锁来写入数据,如果长度大于8,转化成红黑树进行插入

get 操作

get方法不需要加锁

  • 计算hash值,定位到该table索引位置,如果是首节点符合就返回

  • 如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNodefind方法,查找该节点,匹配就返回

  • 以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null

参考文章

ConcurrentHashMap 底层实现原理(JDK1.7 & 1.8)

HashMap?ConcurrentHashMap?相信看完这篇没人能难住你!


标题:ConcurentHashMap
作者:SunnySky
地址:https://www.tianyang.pub/articles/2020/06/02/1591097003160.html

评论