请选择 进入手机版 | 继续访问电脑版
 找回密码
 中文注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

数据结构算法-ConcurrentHashMap源码解析

0
回复
387
查看
[ 复制链接 ]

18

主题

18

帖子

34

积分

小酷一级

Rank: 1

积分
34
2019-4-11 01:03:34 显示全部楼层 阅读模式
作者丨红橙Darren


  • 五个线程同时往 HashMap 中 put 数据会发生什么?
  • ConcurrentHashMap 是怎么保证线程安全的?
在分析 HashMap 源码时还遗留这两个问题,这次我们站在 Java 多线程内存模型和 synchronized 的实现原理,这两个角度来彻底分析一下。至于 JDK 1.8 的红黑树不是本文探讨的内容。
1. Java 多线程内存模型
五个线程同时往 HashMap 中 put 数据会出现两种现象,大概率会出现数据丢失,小概率会出现死循环,我们不妨写个测试代码自己验证一下。那为什么会出现这两种现象,我们先来回顾一下之前的Java 多线程内存模型。请看图:
MB3n3BSTs3hxXzXr.jpg
Java内存模型中规定了所有的变量都存储在主内存中,每条线程还有自己的工作内存,线程的工作内存中保存了该线程使用到的变量到主内存副本拷贝,线程对变量的所有操作(读取、赋值)都必须在工作内存中进行,而不能直接读写主内存中的变量。不同线程之间无法直接访问对方工作内存中的变量,线程间变量值的传递均需要在主内存来完成,线程、主内存和工作内存的交互关系如上图所示。
现在我们来想象一下,假设线程 1 把数据读到了自己的工作内存中,在 tab 角标为 1 的链表头插入了一条新的数据,倘若这时还没来得及将新增的数据刷新到主内中。接着线程 2 就把数据读到了自己的工作内存中,在 tab 角标为 1 的链表头插入了一条新的数据。接着线程 1 把新增数据刷新到主内存中,线程 2 也把数据新增数据刷新到主内存中,那么线程 2 就会覆盖线程 1 的新增数据,从而导致数据丢失的情况。这里需要注意的是,只有两个线程都是操作 tab 的同一个 index 链表才会导致数据丢失的情况,如果不是同一个 index 链表就不会有覆盖和丢失这一说。
2. synchronized 的底层实现原理

关于 HashMap 的线程不安全问题,Java 给我们提供了三种方案,第一种是 HashTable ,第二种是 Collections.synchronizedMap ,第三种是 ConcurrentHashMap 。而第一种和第二种都是通过用 synchronized 同步方法来保证线程安全,性能上有所欠缺不推荐大家使用。ConcurrentHashMap 在 JDK 1.8 之前采用的是 Segment 分段锁来实现的,而 JDK 1.8 之后则采用 synchronized 和 CAS 来实现。

HashTable 通过锁住整个 put 和 get 方法来实现线程安全并不是很合理,因为一个线程在 put 的时候,另外一个线程不能再 put 和 get 必须进入等待状态。同理一个线程在 get 的时候,另外一个线程也不能再 get 和 put 。上面通过分析只有两个线程都是操作 tab 的同一个 index 链表才会导致数据丢失的情况,如果不是同一个 index 链表就不会有覆盖和丢失这一说。因此也没必要锁住整个方法,只需要锁住每个 tab 的 index 链即可。
ConcurrentHashMap 在 JDK 1.8 之前采用的是 Segment 继承自 ReentrantLock 来锁住 tab 的 index 链,而 JDK 1.8 之后则采用 synchronized 来实现,这两者又有什么区别?我们首先看下 synchronized 的底层是怎么实现线程安全的。Java中的每一个对象都可以作为锁。具体表现有以下3种形式。
// 1.对于普通同步方法,锁是当前实例对象。this
public synchronized void method{

}

// 2.对于静态同步方法,锁是当前类的Class对象。this.class
public static synchronized void method{

}

// 3.对于同步方法块,锁是Synchonized括号里配置的对象。object

synchronized(object){

}
}

我们可能会想锁到底存在哪里呢?锁里面会存储什么信息呢?其实 synchronized 同步的代码块,虚拟机在同步代码块开始前会插入一条 monitorenter 指令,在代码块的末尾会插入一条 monitorexit 指令。而每个对象的 Mark Word 头信息里都会存储 Monitor 信息,也就是当前对象的锁信息,当然 Mark Word 头信息还包含对象的 hashCode 和 GC 的分代年龄,具体请看下表:
jst7iK819UqS91E9.jpg
Lock 的实现原理和 synchronized 有些类似,都是通过线程的原子性来保证线程同步,具体的实现的方式大家可以去看下 ReentrantLock 的源码实现。那为什么在 JDK 1.8 之后要采用 synchronized 和 CAS 来实现?在 JDK 1.6 为了减少获得锁和释放锁带来的性能消耗,引入了“偏向锁”和“轻量级锁”,级别从低到高依次是:无锁状态、偏向锁状态、轻量级锁状态和重量级锁状态,这几个状态会随着竞争情况逐渐升级。锁可以升级但不能降级,意味着偏向锁升级成轻量级锁后不能降级成偏向锁。这种锁升级却不能降级的策略,目的是为了提高获得锁和释放锁的效率。当线程 1 进入同步代码块遇到 monitorenter 指令,首先判断锁的状态发现是 0 ,采用 CAS 将锁的状态设置为 1,偏向锁设置为 1,锁的标致位设置为 1 ,继续执行同步代码块里面的指令。这是若线程 2 也来到了同步代码块,也会遇到 monitorenter 指令,首先判断锁的状态发现是 1 进入等待中,等线程 1 执行完同步代码块遇到 monitorenter 指令,首先会清空锁的状态然后唤醒线程 2 。如此反复即可保证线程安全。
偏向锁
大多数情况下,锁不仅不存在多线程竞争,而且总是由同一线程多次获得,为了让线程获得锁的代价更低而引入了偏向锁。当一个线程访问同步块并获取锁时,会在对象头和栈帧中的锁记录里存储锁偏向的线程 ID,以后该线程在进入和退出同步块时不需要进行 CAS 操作来加锁和解锁,只需简单地测试一下对象头的 Mark Word 里是否存储着指向当前线程的偏向锁。如果测试成功,表示线程已经获得了锁。如果测试失败,则需要再测试一下 Mark Word 中偏向锁的标识是否设置成1(表示当前是偏向锁):如果没有设置,则使用 CAS 竞争锁;如果设置了,则尝试使用CAS将对象头的偏向锁指向当前线程。
轻量级锁
线程在执行同步块之前,JVM 会先在当前线程的栈桢中创建用于存储锁记录的空间,并将对象头中的 Mark Word 复制到锁记录中。然后线程尝试使用 CAS 将对象头中的 Mark Word 替换为指向锁记录的针。如果成功,当前线程获得锁,如果失败,表示其他线程竞争锁,当前线程便尝试使用自旋来获取锁。
重量级锁
轻量级锁采用自旋的方式不断的尝试获取锁,如果长时间获取不到锁势必会不断消耗 CPU 的资源。所以当线程竞争比较激烈或者线程迟迟获取不到锁,就会升级为重量级的锁状态,此时线程是阻塞的,且响应时间缓慢。
3. ConcurrentHashMap 源码分析

table;

// 新增元素的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException;
// 二次 hash
int hash = spread(key.hashCode);
int binCount = 0;
for (Node tab = table;;) {
Node f; int n, i, fh;
// 如果 tab 为空,初始化 tab
if (tab == null || (n = tab.length) == 0){
tab = initTable;
}
// 当前 tab 的 index 链表为 null
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 锁住当前 tab 的 index 链表(分段锁)
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// ......

public V get(Object key) {
Node tab; Nodee, p; int n, eh; K ek;
int h = spread(key.hashCode);
if ((tab = table) != null && (n = tab.length) > 0 &&
// CAS 操作
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 遍历当前列表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
最后值得一提的是 table 和 Node 对象中的 next 和 val 都是采用 volatile 来修饰的。
本文转载自【程序员大咖】
公众号内回复“1”带你进粉丝群

酷微米 - 社区版权 - 免责声明1、根据二○一三年一月三十日《计算机软件保护条例》2次修订第17条规定
2、为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件;
3、可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!
4、本主题所有言论和图片纯属会员个人意见,与本论坛立场无关
5、本站所有主题由该帖子作者发表,该帖子作者与酷微米享有帖子相关版权
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和酷微米的同意
7、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任
8、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
9、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意
10、酷微米管理员和版主有权不事先通知发贴者而删除本文
--- 特别提示:本站资源非代理用户严禁传播倒卖,不遵守规定者,酷微米有权封号而不作另行通知! ---

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 中文注册

本版积分规则

酷微米 你我共享 为兴趣而生,全网资源一网打尽。 立即登录 中文注册
发布主题 快速回复 收藏帖子 返回列表 官方QQ群