ConcurrentHashMap

﹏ヽ暗。殇╰゛Y 2022-09-18 02:58 219阅读 0赞

1 ConcurrentHashMap提供并发的检索和更新操作，功能规范和hashtable一样。

同步策略有区别，使用非全局锁。

2 检索操作get不阻塞，很可能和更新操作重叠，总能得到最近更新完成的值。

3 迭代元素不会抛出并发修改异常，迭代元素只是迭代器创建时数据结构的快照。迭代子同时只能被一个线程使用。

4 更新操作的并发级别是可以配置的，由concurrencyLevel决定，作为hint。这个参数将整个hash表分割成相互独立的子表，无竞争操作。这个concurrencyLevel的设置根据使用场景的并发修改量来确定，过大则浪费内存空间，过小则影响并发性能。最好是在构造的时候就确定。

5 不允许空键、空值。同hashtable,异hashmap。

6 源码解读

6.1   接口结构，同hashmap继承AbstractMap。

Java代码   ![收藏代码][icon_star.png]

1.  public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>  
2.          implements ConcurrentMap<K, V>, Serializable \{

Java代码   ![收藏代码][icon_star.png]

1.  public interface ConcurrentMap<K, V> extends Map<K, V> \{  
2.        
3.      V putIfAbsent(K key, V value);  
4.      boolean replace(K key, V oldValue, V newValue);  
5.      V replace(K key, V value);  
6.  \}

6.2 分段机制，锁粒度细化

段是特殊的hash表

Java代码   ![收藏代码][icon_star.png]

1.  /\*\* 
2.   \* The segments, each of which is a specialized hash table. 
3.   \*/  
4.  final Segment<K,V>\[\] segments;

段是对可重入锁的变形子类，为了简化锁的使用和避免单独构造可重入锁。

Java代码   ![收藏代码][icon_star.png]

1.  static final class Segment<K,V> extends ReentrantLock implements Serializable \{

主要数据由table维护，对hashmap的读写操作最后都落实到java.util.concurrent.ConcurrentHashMap.Segment.table中。

Java代码   ![收藏代码][icon_star.png]

1.  /\*\* 
2.   \* The per-segment table. Elements are accessed via 
3.   \* entryAt/setEntryAt providing volatile semantics. 
4.   \*/  
5.  transient volatile HashEntry<K,V>\[\] table;

java.util.concurrent.ConcurrentHashMap.HashEntry<K, V>为段内部条目实现，对外不可见，功能类似java.util.HashMap.Entry<K, V>。

从代码可以看出，每个段都挂载着一个hashmap,并发hashmap的实现的基本机制就是把一个hashmap拆分为多个hashmap，然后在每个段的hashmap中单独进行同步操作。对key的第一次hash，定位到段，进行二次hash定位到子hash表中的桶。

6.3 ConcurrentHashMap的高性能实现除了依靠分段策略，每段单独同步之外，还使用了强大的非阻塞同步机制，那就是compare and swap基于硬件的CAS算法（引用 [ http://javasourcecode.org/html/open-source/jdk/jdk-6u23/sun/misc/Unsafe.java.html][http_javasourcecode.org_html_open-source_jdk_jdk-6u23_sun_misc_Unsafe.java.html] ）。

Java代码   ![收藏代码][icon_star.png]

1.  // Unsafe mechanics  
2.  private static final sun.misc.Unsafe UNSAFE;  
3.  private static final long SBASE;  
4.  private static final int SSHIFT;  
5.  private static final long TBASE;  
6.  private static final int TSHIFT;  
7.    
8.  static \{  
9.      int ss, ts;  
10.     try \{  
11.         UNSAFE = sun.misc.Unsafe.getUnsafe();  
12.         Class tc = HashEntry\[\].class;  
13.         Class sc = Segment\[\].class;  
14.         TBASE = UNSAFE.arrayBaseOffset(tc);  
15.         SBASE = UNSAFE.arrayBaseOffset(sc);  
16.         ts = UNSAFE.arrayIndexScale(tc);  
17.         ss = UNSAFE.arrayIndexScale(sc);  
18.     \} catch (Exception e) \{  
19.         throw new Error(e);  
20.     \}  
21.     if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)  
22.         throw new Error("data type scale not a power of two");  
23.     SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);  
24.     TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);  
25. \}

Get实现  java.util.concurrent.ConcurrentHashMap.get(Object)

Java代码   ![收藏代码][icon_star.png]

1.  public V get(Object key) \{  
2.          Segment<K,V> s; // manually integrate access methods to reduce overhead  
3.          HashEntry<K,V>\[\] tab;  
4.          int h = hash(key.hashCode());  
5.          long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;  
6.          if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&  
7.              (tab = s.table) != null) \{  
8.              for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile  
9.                       (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);  
10.                  e != null; e = e.next) \{  
11.                 K k;  
12.                 if ((k = e.key) == key || (e.hash == h && key.equals(k)))  
13.                     return e.value;  
14.             \}  
15.         \}  
16.         return null;  
17.     \}

get没有使用锁同步，而是使用轻量级同步volatile原语sun.misc.Unsafe.getObjectVolatile(Object, long)，保证读到的是最新的对象。

PUT 实现java.util.concurrent.ConcurrentHashMap.put(K, V)

Java代码   ![收藏代码][icon_star.png]

1.  @SuppressWarnings("unchecked")  
2.      public V put(K key, V value) \{  
3.          Segment<K,V> s;  
4.          if (value == null)  
5.              throw new NullPointerException();  
6.          int hash = hash(key.hashCode());  
7.          int j = (hash >>> segmentShift) & segmentMask;  
8.          if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck  
9.               (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment  
10.             s = ensureSegment(j);  
11.         return s.put(key, hash, value, false);  
12.     \}

如果段不为空，那么进入java.util.concurrent.ConcurrentHashMap.Segment.put(K, int, V, boolean)，否则构造段。由此可以看出段的构造是以懒加载的方式，按需构造。

Java代码   ![收藏代码][icon_star.png]

1.  final V put(K key, int hash, V value, boolean onlyIfAbsent) \{  
2.              HashEntry<K,V> node = tryLock() ? null :  
3.                  scanAndLockForPut(key, hash, value);  
4.              V oldValue;  
5.              try \{  
6.                  HashEntry<K,V>\[\] tab = table;  
7.                  int index = (tab.length - 1) & hash;  
8.                  HashEntry<K,V> first = entryAt(tab, index);  
9.                  for (HashEntry<K,V> e = first;;) \{  
10.                     if (e != null) \{  
11.                         K k;  
12.                         if ((k = e.key) == key ||  
13.                             (e.hash == hash && key.equals(k))) \{  
14.                             oldValue = e.value;  
15.                             if (!onlyIfAbsent) \{  
16.                                 e.value = value;  
17.                                 ++modCount;  
18.                             \}  
19.                             break;  
20.                         \}  
21.                         e = e.next;  
22.                     \}  
23.                     else \{  
24.                         if (node != null)  
25.                             node.setNext(first);  
26.                         else  
27.                             node = new HashEntry<K,V>(hash, key, value, first);  
28.                         int c = count + 1;  
29.                         if (c > threshold && tab.length < MAXIMUM\_CAPACITY)  
30.                             rehash(node);  
31.                         else  
32.                             setEntryAt(tab, index, node);  
33.                         ++modCount;  
34.                         count = c;  
35.                         oldValue = null;  
36.                         break;  
37.                     \}  
38.                 \}  
39.             \} finally \{  
40.                 unlock();  
41.             \}  
42.             return oldValue;  
43.         \}

进入段中执行最终put的时候，会使用可重入锁进行tryLock可轮询请求锁，如果成功获取锁，那么条目的插入方式和普通hashmap没多大区别。

如果此时有其他线程也再对这个段进行更新操作，那么执行scanAndLockForPut进行重试。

重试的处理逻辑(这里采用的是自旋锁的思路http://baike.baidu.com/view/1250961.htm)

Java代码   ![收藏代码][icon_star.png]

1.  \*/  
2.       private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) \{  
3.           HashEntry<K,V> first = entryForHash(this, hash);  
4.           HashEntry<K,V> e = first;  
5.           HashEntry<K,V> node = null;  
6.           int retries = -1; // negative while locating node  
7.           while (!tryLock()) \{  
8.               HashEntry<K,V> f; // to recheck first below  
9.               if (retries < 0) \{  
10.                  if (e == null) \{  
11.                      if (node == null) // speculatively create node  
12.                          node = new HashEntry<K,V>(hash, key, value, null);  
13.                      retries = 0;  
14.                  \}  
15.                  else if (key.equals(e.key))  
16.                      retries = 0;  
17.                  else  
18.                      e = e.next;  
19.              \}  
20.              else if (++retries > MAX\_SCAN\_RETRIES) \{  
21.                  lock();  
22.                  break;  
23.              \}  
24.              else if ((retries & 1) == 0 &&  
25.                       (f = entryForHash(this, hash)) != first) \{  
26.                  e = first = f; // re-traverse if entry changed  
27.                  retries = -1;  
28.              \}  
29.          \}  
30.          return node;  
31.      \}

一旦未获得锁 while (!tryLock()) 则进行重试循环。

第一次重试中retries < 0，如果桶条目不为空，那么遍历桶中条目链表，如果key已经存在，那么直接进入下一个循环，否则构造新条目，进入下一个循环；如果重试次数达到极限，那么使用阻塞同步方法；每隔一次循环，校验下所在桶有没有更新，如果更新了，那么重试次数重置，重新开始。

一旦获得锁，直接返回，进行常规的hash put操作。

总的来说，put的同步机制是如果没有其他线程在更新该段，那么直接put。否则轮询请求锁，直至获得锁。

[icon_star.png]: /images/20220828/a6bc407c3284480d92f745471d1d6d13.png
[http_javasourcecode.org_html_open-source_jdk_jdk-6u23_sun_misc_Unsafe.java.html]: http://javasourcecode.org/html/open-source/jdk/jdk-6u23/sun/misc/Unsafe.java.html

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关 ConcurrentHashMap

**线程不安全的HashMap** ** ** 因为多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能...

曾经终败给现在/ 2024年04月18日 15:43/ 0 赞/ 54 阅读

相关 concurrenthashmap(concurrenthashmap jdk18)

HashMap HashTable和ConcurrentHashMap的区别 (条理上还需要整理，也是先说相同点，再说不同点) HashMap是Hashtable的轻量

刺骨的言语ヽ痛彻心扉/ 2023年09月26日 13:24/ 0 赞/ 130 阅读

相关 ConcurrentHashMap

ConcurrentHashMap 数组 + 链表 +红黑树的简单梳理初始化数组长度默认长度16，初始化有指定长度，就会返回指定长度（n）的数组

素颜马尾好姑娘i/ 2023年01月01日 02:58/ 0 赞/ 146 阅读

相关 ConcurrentHashMap

这个能看懂的都是大佬了反正我是看懂了一部分，但是对于一些跳出循环呀，跳出if判断的还是很模糊，不过不影响对于hash表整体的理解有完全搞明白的大佬可以指点一波

快来打我*/ 2022年12月19日 00:41/ 0 赞/ 122 阅读

相关 ConcurrentHashMap

1. 简介 ConcurrentHashMap是线程安全的map,通过索引+synchroninzed的分段式锁实现线程安全。在

àì夳堔傛蜴生んèń/ 2022年11月16日 05:46/ 0 赞/ 169 阅读

相关 ConcurrentHashMap

ConcurrentHashMap是Java5中新增加的一个线程安全的Map集合，可以用来替代HashTable。对于ConcurrentHashMap是如何提高其效率的，可能

爱被打了一巴掌/ 2022年09月25日 08:21/ 0 赞/ 202 阅读

相关 ConcurrentHashMap

1 ConcurrentHashMap提供并发的检索和更新操作，功能规范和hashtable一样。同步策略有区别，使用非全局锁。 2 检索操作get不阻塞，很可能和更新操

﹏ヽ暗。殇╰゛Y/ 2022年09月18日 02:58/ 0 赞/ 220 阅读

相关 ConcurrentHashMap

原帖：[点击打开链接][Link 1] hashmap问题：线程不安全 ConcurrentHashMap解决方案:把map拆分成N个segmen(类似

青旅半醒/ 2022年06月09日 05:37/ 0 赞/ 167 阅读

相关 ConcurrentHashMap

HashMap在多线程的情况下，HashMap是不安全的，但Hashtable因为操作的时候会锁住整个table，这就意味着所有的对象在争一把锁，效率极低，在这种情况下推出了C

ゝ一世哀愁。/ 2022年05月26日 05:51/ 0 赞/ 171 阅读

相关 ConcurrentHashMap

ConcurrentHashMap是什么 Concurrent翻译过来是并发的意思，字面理解它的作用是处理并发情况的 HashMap，在介绍它之前先回顾下之前的知识。通过

偏执的太偏执、/ 2022年04月02日 05:58/ 0 赞/ 237 阅读