Java - 线程安全的 HashMap 实现方法及原理

妖狐艹你老母 2022-05-30 23:21 366阅读 0赞

转载自 http://liqianglv2005.iteye.com/blog/2025016

Java HashMap 是非线程安全的。在多线程条件下，容易导致死循环，具体表现为CPU使用率100%。因此多线程环境下保证 HashMap 的线程安全性，主要有如下几种方法：

1.  使用 java.util.Hashtable 类，此类是线程安全的。
2.  使用 java.util.concurrent.ConcurrentHashMap，此类是线程安全的。
3.  使用 java.util.Collections.synchronizedMap() 方法包装 HashMap object，得到线程安全的Map，并在此Map上进行操作。
4.  自己在程序的关键方法或者代码段加锁，保证安全性，当然这是严重的不推荐。

为什么 HashMap 非线程安全, 可以参考大神陈皓（weibo账号：左耳朵耗子）在他自己技术网站Coolshell上的文章，写的非常详细。文章链接（[直通车][Link 1]）：[http://coolshell.cn/articles/9606.html][Link 1]

这里重点分析下上面列举的几种方法实现并行安全性的原理：

（一）java.util.Hashtable类：类的主要数据结构如下：

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

1.      /\*\* 
2.       \* The hash table data. 
3.       \*/  
4.      **private** **transient** Entry\[\] table;  
5.    
6.  **private** **static** **class** Entry<K,V> **implements** Map.Entry<K,V> \{  
7.      **int** hash;  
8.      K key;  
9.      V value;  
10.     Entry<K,V> next;

可见，Hashtable 的实现是一个数组，每个数组元素是一个LinkList结构，因此类的数据实际上保存在一个散列表中。这个实现和 HashMap 的实现是一致的。数据结构如下：  
![e2aae6de-1e4e-31dc-9cd9-0f319a48fec2.jpg][]

那么Hashtable如何保证线程安全性的哪？下面是 Hashtable的源码：

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

1.  **public** **synchronized** V get(Object key) \{  
2.      Entry tab\[\] = table;  
3.      …… //此处省略，具体的实现请参考 jdk实现  
4.      \}  
5.    
6.  **public** **synchronized** V put(K key, V value) \{  
7.      …… //具体实现省略，请参考jdk实现  
8.      \}  
9.    
10.   
11. **public** **synchronized** V remove(Object key) \{  
12.     …… //具体实现省略，请参考jdk实现  
13.     \}  
14.   
15.      
16.     **public** **synchronized** **void** putAll(Map<? **extends** K, ? **extends** V> t) \{  
17.         **for** (Map.Entry<? **extends** K, ? **extends** V> e : t.entrySet())  
18.             put(e.getKey(), e.getValue());  
19.     \}  
20.   
21.   
22.     **public** **synchronized** **void** clear() \{  
23.     …… //具体实现省略，请参考jdk实现  
24.     \}

上面是 Hashtable 提供的几个主要方法，包括 get(), put(), remove() 等。注意到**每个方法本身都是 synchronized 的，不会出现两个线程同时对数据进行操作的情况，因此保证了线程安全性，但是也大大的降低了执行效率**。因此是不推荐的。

（二）使用 java.util.Collections.synchronizedMap(Map<K,V>) 方法进行封装。 方法源代码如下：

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

1.  **public** **static** <K,V> Map<K,V> synchronizedMap(Map<K,V> m) \{  
2.      **return** **new** SynchronizedMap<K,V>(m);  
3.      \}  
4.    
5.    
6.  **private** **static** **class** SynchronizedMap<K,V>  
7.      **implements** Map<K,V>, Serializable \{  
8.      // use serialVersionUID from JDK 1.2.2 for interoperability  
9.      **private** **static** **final** **long** serialVersionUID = 1978198479659022715L;  
10.   
11.     **private** **final** Map<K,V> m;     // Backing Map  
12.         **final** Object      mutex;    // Object on which to synchronize  
13.   
14.     SynchronizedMap(Map<K,V> m) \{  
15.             **if** (m==**null**)  
16.                 **throw** **new** NullPointerException();  
17.             **this**.m = m;  
18.             mutex = **this**;  
19.         \}  
20.   
21.     SynchronizedMap(Map<K,V> m, Object mutex) \{  
22.             **this**.m = m;  
23.             **this**.mutex = mutex;  
24.         \}  
25.   
26.     **public** **int** size() \{  
27.         **synchronized**(mutex) \{ **return** m.size();\}  
28.         \}  
29.     **public** **boolean** isEmpty()\{  
30.         **synchronized**(mutex) \{ **return** m.isEmpty();\}  
31.         \}  
32.     **public** **boolean** containsKey(Object key) \{  
33.         **synchronized**(mutex) \{ **return** m.containsKey(key);\}  
34.         \}

从实现源代码可以发现，**其封装的本质和 Hashtable 的实现是完全一致的，即对原Map本身的方法进行加锁**，加锁的对象或者为外部指定共享对象mutex，或者为包装后的线程安全的Map本身。Hashtable 可以理解为 SynchronizedMap mutex=null 时候的特殊情况。因此**这种同步方式的执行效率也是很低的**。

既然已经有了Hashtable， 为什么还需要Collections 提供的这种静态方法包装哪？很简单，这种包装是Java Collection Framework提供的统一接口，除了用于 HashMap 外，还可以用于其他的Map。当然 除了对Map进行封装，Collections工具类还提供了对 Collection（比如Set，List）的线程安全实现封装方法，具体请参考 java.util.Colletions 实现，其原理和 SynchronizedMap 是一致的。

（三） 使用 java.util.concurrent.ConcurrentHashMap 类。并发编程大师 Doug Lea 出品，绝对精品。这是 HashMap 的线程安全版，同 Hashtable 相比，ConcurrentHashMap 不仅保证了访问的线程安全性，而且在效率上有较大的提高。

ConcurrentHashMap的数据结构如下（引用图片地址[http://www.yupoo.com/photos/goldendoc/81556254/][http_www.yupoo.com_photos_goldendoc_81556254]）：

![3d9bb93b-3ddf-338b-a1f6-f473be035b84.png][]

可以看出，相对 HashMap 和 Hashtable， ConcurrentHashMap 增加了Segment 层，每个Segment 原理上等同于一个 Hashtable， ConcurrentHashMap 为 Segment 的数组。下面是 ConcurrentHashMap 的 put 和 get 方法：

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

1.  **final** Segment<K,V> segmentFor(**int** hash) \{  
2.          **return** segments\[(hash >>> segmentShift) & segmentMask\];  
3.      \}  
4.    
5.  **public** V put(K key, V value) \{  
6.          **if** (value == **null**)  
7.              **throw** **new** NullPointerException();  
8.          **int** hash = hash(key.hashCode());  
9.          **return** segmentFor(hash).put(key, hash, value, **false**);  
10.     \}  
11.   
12. **public** V get(Object key) \{  
13.         **int** hash = hash(key.hashCode());  
14.         **return** segmentFor(hash).get(key, hash);  
15.     \}

向 ConcurrentHashMap 中插入数据或者读取数据，首先都要讲相应的 Key 映射到对应的 Segment，**因此不用锁定整个类， 只要对单个的 Segment 操作进行上锁操作就可以了**。理论上如果有 n 个 Segment，那么最多可以同时支持 n 个线程的并发访问，从而大大提高了并发访问的效率。另外 **rehash() 操作也是对单个的 Segment 进行的**，所以由 Map 中的数据量增加导致的 rehash 的成本也是比较低的。

单个 Segment 的进行数据操作的源码如下：

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

1.  V put(K key, **int** hash, V value, **boolean** onlyIfAbsent) \{  
2.              lock();  
3.              **try** \{  
4.                  **int** c = count;  
5.                  **if** (c++ > threshold) // ensure capacity  
6.                      rehash();  
7.    
8.                   …… // 代码省略，具体请查看源码                  
9.    
10.             \} **finally** \{  
11.                 unlock();  
12.             \}  
13.         \}  
14.   
15. V replace(K key, **int** hash, V newValue) \{  
16.             lock();  
17.             **try** \{  
18.                 HashEntry<K,V> e = getFirst(hash);  
19.                 
20.                  …… // 代码省略，具体请查看源码     
21.                  
22.             \} **finally** \{  
23.                 unlock();  
24.             \}  
25.         \}

**   可见对 单个的 Segment 进行的数据更新操作都是 加锁的，从而能够保证线程的安全性。**

ConcurrentHashMap 的更具体实现和分析见（[直通车][Link 2]） [http://www.iteye.com/topic/1103980][Link 2]， 非常详细。

几种线程同步实现方法的效率比较，可以参考（[直通车][Link 3]）  [http://blog.sina.com.cn/s/blog\_734a77160100yku1.html][Link 3]

[Link 1]: http://coolshell.cn/articles/9606.html
[icon_star.png]: /images/20220531/dfd21f6132eb4cba8e0ddb8cd1cfaf6d.png
[e2aae6de-1e4e-31dc-9cd9-0f319a48fec2.jpg]: /images/20220531/e5e9b64df3934de5b06ca42685829f54.png
[http_www.yupoo.com_photos_goldendoc_81556254]: http://www.yupoo.com/photos/goldendoc/81556254/
[3d9bb93b-3ddf-338b-a1f6-f473be035b84.png]: /images/20220531/ba9f18632b5b49ac9956ed1df0373cb1.png
[Link 2]: http://www.iteye.com/topic/1103980
[Link 3]: http://blog.sina.com.cn/s/blog_734a77160100yku1.html