0%

Java集合类-ConcurrentHashMap原理

特点

高性能且线程安全的哈希表。

线程安全是怎么实现的?

Java7中ConcurrentHashMap将哈希表分割成为多个段(Segment),每一个段继承ReentrantLock,对每一段进行加锁。每个Segment里类似又有一个小的HashMap,等于是双重哈希表。

Java8中采用了自旋CAS和synchronzied保证线程安全,锁的粒度调整为对table数组中每个元素进行加锁;put元素时,定位到桶位置后,通过synchronzied给桶中链表首节点或红黑树根节点加锁。这样多线程竞争哈希表同一个桶位置的几率又降低了。

java8的ConcurrentHashMap的数据结构参考java8的HashMap,采用数组+链表+红黑树。

  • put方法里,是一个无限循环,即自旋,修改table数组都是通过cas操作,自旋锁的机制避免了阻塞和恢复线程的上下文切换开销。

  • 只要当前桶位置没有元素,就先自旋CAS进行更新。

  • 存在hash冲突或修改已有的值时,需要进入桶内部的链表或红黑树进行操作时,才开始用synchronized真正加锁。

get是不加锁的,所以与CopyOnWriteArrayList一样,不保证读数据的实时性,数据是弱一致性。

size的求法和LongAdder里的思路一样,将大小数据分段累加,避免多线程竞争,用自旋cas保证数据更新的原子性。

不能解决什么问题?

因为数据是弱一致性的,get时并不加锁,所以对读数据实时性要求高的需求不能满足。

例如线程1在某一时刻执行了put(key, value),先线程2随后立即get(key)不一定能读取到线程1刚put的,因为put可能正在进行中还没结束。

扩容机制是怎样的?

本来一个线程扩容时,其他线程应该都阻塞等待这个线程扩容完成后才能对哈希表进行读写,这就成了并发的瓶颈。

ConcurrentHashMap具体实现是,反正你闲着也是闲着,不如一起来扩容。

扩容时nextTable会指向扩容后的数组,扩容方法transfer里通过自旋进行。

多个线程通过sizeCtl判断当前所处状态,再通过transferIndex协调各线程应该操作哪一些桶。

参考:

跟同样是线程安全的Hashtable有何区别?

Hashtable的线程安全是对整个哈希表上锁(在多数方法上加上sychronized),其中一个线程访问哈希表时,其他线程只能等待,很多没有必要上锁的场景也上锁,因此在多线程竞争激烈的情况下整体访问速度会变慢。

ConcurrentHashMap把哈希表分割成若干个段,修改每一段时仅针对访问的段上锁,不同的线程访问不同的段时互不干扰,减少了多个线程争抢同一把锁的几率,减少了线程等待的时间,所以提高了性能。

分段锁是怎么实现的?

get方法不加锁,结点类里的value设置了volatile保证了value在多线程下的可见性,保证get到value最新的修改值。

总结:

  1. 循环+CAS实现自旋锁,减少线程阻塞恢复的上下文切换消耗
  2. size更新采用LongAdder分段锁思想,减少竞争
  3. LongAdder机制中的字节填充解决伪共享
  4. 多线程协同分组扩容。

与Collections.synchronizedMap()的区别?

Collections.synchronizedMap()对HashMap做了一层装饰,用synchronized锁住整个哈希表,以保证各操作的线程安全,锁的粒度比较大。
性能比ConcurrentHashMap更差,但可以保证读的实时性。

参考资料