ConcurrentHashMap学习

60次阅读

共计 2339 个字符,预计需要花费 6 分钟才能阅读完成。

一、为什么要用 ConcurrentHashMap?
1、HashMap 线程不安全,并且进行 put 操作会导致死循环(由于 HashMap 的 Entry 链表形成环形数据结构,Entry 下的 next 节点永远不为空)2、HashTable 多线程效率低下,主要表现在数据操作方法头采用 synchronized 互斥锁,使得其他线程访问同步方法会进入阻塞或者是轮询状态(就是线程会无限循环查看锁是否被释放)3、ConcurrentHashMap 的锁分段技术可提升并发访问效率(表现在吞吐量)
二、结构

解析:Segment 是一种可重入锁,在 ConcurrentHashMap 中扮演锁的角色,HashEntry 则是用于存储键值对数据。ConcurrentHashMap 与 Segment 和 HashEntry 是一一对应的,Segment 对 HashEntry 充当锁的角色,每当对 HashEntry 数组的数据进行修改时,首先要获取对应的 Segment 锁解决散列冲突的方式是采用分离链表法:分散链表法使用链表解决冲突,将散列值相同的元素都保存到一个链表中。当查询的时候,首先找到元素所在的链表,然后遍历链表查找对应的元素,也就是会根据 key 定位到链表的某个位置,所以不管是 hashMap 还是 concurrentHashMap 相同 key 是只取最后插入的值图片来自 http://faculty.cs.niu.edu/~fr…
三、初始化
capacity:当前数组容量,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍,默认为 16,即默认允许 16 个线程同时访问。loadFactor:负载因子,默认为 0.75。threshold:扩容的阈值,等于 capacity * loadFactor 初始化 Segment 数组,该长度 ssize 是通过 concurrencyLevel 计算得出,需要能通过按位与的散列算法来定位数组的索引,故必须要保证 Segment 的长度为 2 的 N 次方,故 concurrencyLevel 为 14、15、16,ssize 都等于 15,即容器锁的格式也是 16 初始化 segment,initialCapacity 为 ConcurrentHashMap 初始化容量,loadfactor 是每个 segment 的负载因子
四、定位 Segment
由于 ConcurrentHashMap 使用分段锁 Segment 来保护不同段的数据,那么在插入和读取元素的时候,必须先通过 Wang/Jenkins hash 的变种算法对元素的 hashCode 进行再次散列那么为什么需要再次散列呢?为了减少散列冲突,使得元素能够均匀分布在不同的 segment 中,从而达到提高容器的存取效率,那么不再次散列会出现什么结果?会导致不同数值它的散列值可能会相同,从而导致所有数值都存在同一个 segment 中,从而导致 segment 失去分段锁的意义并且存取缓慢如果进行再次散列,那么所有的数值都会散列开,之前的问题迎刃而解
五、get、put、size 操作
ConcurrentHashMap 高效的原因之一在于 get 操作不需要加锁,因为它所有共享变量都定义成 volatile,能够保证在多线程之间的可见性,能够被多线程同时读,并且保证不会读到过期值,并且由 volatile 修饰的共享变量均不需要回写主内存 put 操作时由于对共享变量进行了写的操作,故必须加锁,那么 put 方法首先会定位到 segment(因为 segment 相当于装载元素的桶),然后进行插入操作,操作分为 2 步:1、在插入元素之前会先判断是否需要扩容(所有容器都是需要判断扩容),做法是如果 capacity *loadFactor 大于 threshold 则扩容,2、扩容多少呢?首先会创建一个容量为原来 2 倍的数组,将原有元素进行散列后插入新的数组,为了高效,只会针对某个 segment 进行扩容那这个就是负载因子的作用,这个操作和 HashMap 不一致,HashMap 是在插入完之后进行判断是否需要扩容,就会导致如果下次没有插入数据,那么这个空间就浪费了,在 jdk1.8 还做了部分修改 size 操作:就是为了统计 segment 的所有大小,那么 segment 的 count 是个全局变量是用 volatile 修饰,最快速的做法是,把所有的 segment 的 count 加起来,但是如果在这期间出现了修改操作,那么 count 的统计就不精确了,如果把 segment 的 put、remove、clean 全部锁住,那么效率太低,目前的做法是,尝试 2 次不锁住 segment 来统计 count,如果统计过程中出现容器变化,那么就加锁,来统计,ConcurrentHashMap 是如何知道统计过程中容器发生了变化,用 modCount 变量,在 put、remove、clean 方法里操作元素前会将 modCount 进行加 1,比较前后变化
jdk1.8 不再采用 segment 作为锁的粒度,而是直接将 HashEntry 作为锁,从而降低锁的粒度、jdk1.8 使用内置锁 synchronized 来代替重入锁 ReentrantLock 因为粒度降低了,在相对而言的低粒度加锁方式,synchronized 并不比 ReentrantLock 差,在粗粒度加锁中 ReentrantLock 可能通过 Condition 来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition 的优势就没有了 JVM 的开发团队从来都没有放弃 synchronized,而且基于 JVM 的 synchronized 优化空间更大,使用内嵌的关键字比使用 API 更加自然在大量的数据操作下,对于 JVM 的内存压力,基于 API 的 ReentrantLock 会开销更多的内存,虽然不是瓶颈,但是也是一个选择依据

正文完
 0