神刀安全网

ConcurrentHashMap,一条长着熊掌的鱼

在现实开发中,不可避免地会碰到一些多线程并发访问的情况。为了解决这个问题,HashTable 和HashMap 先后诞生。

问题也随之而来,使用后发现HashTable 虽然能保证线程安全但是效率低下,而HashMap 虽然效率高于hashTable 但是是非线程安全的。这个很像一个鱼与熊掌的问题,真的不可兼得吗?

于是人们就考虑有没有一种及支持并发有能保证线程安全的方法。终于,在JDK1.5中,伟大的Doug Lea 给我们带来了concurrent 包,从此Map 也有安全的了,这就是ConcurrentHashMap。安全且高效,像一条长了熊掌的鱼。

为了更好的理解ConcurrentHashMap的优点,我们先了解下它的两个前辈HashTable 和HashMap。

效率低下的HashTable

在多线程并发访问的场景中,如何保证线程的安全很重要。

容器HashTable 使用Synchronize 来确保线程的安全,其将所有对容器状态的访问都串行化了,一个线程访问其他线程都需要等待。

ConcurrentHashMap,一条长着熊掌的鱼

HashTable 只有一把锁,当一个线程访问HashTable 的同步方法时,会将整张table 锁住,当其他线程也想访问HashTable 同步方法时,就会进入阻塞或轮询状态。也就是确保同一时间只有一个线程对同步方法的占用,避免多个线程同时对数据的修改,确保线程的安全性。

但HashTable 对get,put,remove 方法都使用了同步操作,这就造成如果两个线程都只想使用get 方法去读取数据时,因为一个线程先到进行了锁操作,另一个线程就不得不等待,这样必然导致效率低下,而且竞争越激烈,效率越低下。

线程不安全的HashMap

JDK1.2 引进了Map 接口的一个实现HashMap,它是HashTable 的轻量级实现,并不是Synchronize 的所以效率高于HashTable,同时也导致HashMap 是非线程安全的。

ConcurrentHashMap,一条长着熊掌的鱼

HashMap的本质:数组+链表。

根据key 调用hashCode() 方法取得hash 值,然后计算出数组下标,如果多个key 对应到同一个下标,就用链表串起来,新加入的节点会从头结点加入。

Javadoc 中关于hashmap 有一段这样的描述:此实现不是同步的。如果多个线程同时访问一个哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步。

即多线程访问时必须为之提供外同步(Collections.synchronizedMap)。

ConcurrentHashMap,一条长着熊掌的鱼

在hashmap 做put 操作的时候会调用到以上的方法。假如A线程和B线程同时对同一个数组位置调用addEntry,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。同理,当多线程对同一数组位置进行remove操作时也会产生覆盖。

因此如果不进行额外的外同步操作,HashMap 是非线程安全的。

并发又安全的ConcurrentHashMap

ConcourrentHashMap 保证线程安全的方法是分段锁技术

ConcurrentHashMap,一条长着熊掌的鱼

如上图,在hashMap 的基础上,ConcurrentHashMap 将数据分为多个segment(默认16个),然后每次操作对一个segment 加锁,HashTable 在竞争激烈的并发环境下表现出效率低下的原因是,由于所有访问HashTable的线程都必须竞争同一把锁,而ConcurrentHashMap 将数据分到多个segment 中(默认16,也可在申明时自己设置,不过一旦设定就不能更改,扩容都是扩充各个segment 的容量),每个segment 都有一个自己的锁,只要多个线程访问的不是同一个segment 就没有锁争用,就没有堵塞,也就是允许16个线程并发的更新而尽量没有锁争用。

ConcurrentHashMap 的segment 就类似一个HashTable,但比HashTable 更加优化,前面说过HashTable 对get,put,remove 方法都会使用锁,而ConcurrnetHashMap 中get 方法是不涉及到锁的,如下:

ConcurrentHashMap,一条长着熊掌的鱼

在并发读取时,除了key 对应的value 为null 外,并没有用到锁,所以对于读操作无论多少线程并发都是安全高效的。

ConcurrentHashMap,一条长着熊掌的鱼

ConcurrentHashMap,一条长着熊掌的鱼

ConcurrentHashMap,一条长着熊掌的鱼

这里除了加锁操作,其他与普通HashMap 原理上无太大区别。

ConcurrentHashMap 只有put 和remove 这种更新操作要使用锁。

ConcurrentHashMap 实现技术是保证HashEntry 几乎是不可变的,HashEntry 代表每个hash 链中的一个节点。

static final class HashEntry {

final K key;

final int hash;

volatile V value;

final HashEntry next;

可以看到除了value 不是final 的,其他的值都是final 的,这意味着不能从hash 链的中间或尾部添加或删除节点,因为这需要修改next 引用值,所有的节点的修改只能从头部开始。对于put 操作,可以一律添加到Hash 链的头部。但是对于remove 操作,可能需要从中间删除一个节点,这就需要将要删除节点的前面所有节点整个复制一遍,最后一个节点指向要删除结点的下一个结点。

而将value 设成volatile 的可以确保读操作看到最新的值,即ConcurrentHashMap 支持一边更新一边遍历。

本文作者:熊舜 (点融黑帮),毕业于武汉大学,现就职于点融网Financial Core部门,Java开发工程师,喜欢篮球,旅行,骑行。

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » ConcurrentHashMap,一条长着熊掌的鱼

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址