多线程下使用HashMap

今天药忘吃喽~ 2023-01-21 14:23 119阅读 0赞

### 多线程下使用HashMap ###

如果在被问及：“HashMap是否线程安全，如何线程安全地使用HashMap?”，你会如何回答，以前的话我会这样回答：“HashMap是非线程安全的，如果要保证线程安全的话，就需要使用Hashtable。”但是经过最近的学习，我又了解到了`ConcurrentHashMap`和`SyschronizedMap`，其实这个问题的本质就是：`HashMap`、`Hashtable`、`ConcurrentHashMap`、`SyschronizedMap`的原理与区别。接下来我就总结一下的我的学习成果：

### 1. 为什么HashMap不安全？ ###

我们大家总说HashMap不安全，那么它到底为什么不安全呢？首先来看看HashMap的实现，HashMap内部使用一个数组链表的方式来实现，使用的存储结构如下(基于JDK1.7)：

transient Entry<K,V>[] table ;
    static class Entry<K,V> implements Map.Entry<K,V> {
        
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
            ...
    }

从源码中可以看出HashMap使用了一个Entry数组，而Entry类又包含一个类型为Entry的next变量，也就相当于是一个链表，所有根据 hash 值计算的 bucket 一样的 key 会存储到同一个链表里(即产生了冲突)，大概就是下图的样子：  
![在这里插入图片描述][20210516215351254.png]

#### HashMap的自动扩容机制 ####

HashMap 内部的 Entry 数组默认的大小是16，假设有100万个元素，那么最好的情况下每个 hash 桶里都有62500个元素，这时get(),put(),remove()等方法效率都会降低。为了解决这个问题，HashMap 提供了自动扩容机制，当元素个数达到`数组大小*loadFactor` 后会扩大数组的大小，在默认情况下，数组大小为16，loadFactor 为0.75，也就是说当 HashMap 中的元素超过16\\0.75=12时，会把数组大小扩展为2\*16=32，并且重新计算每个元素在新数组中的位置。如下图所示:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70]

#### 为什么线程不安全 ####

简单来说：假设两个线程同时进行put操作，并且两个put操作元素的key发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 hashMap 的实现，这两个值将会添加到数组的同一个地方，那么就会有一个值被覆盖，因为造成了数据丢失，所以 HashMap 线程不安全，如下图示：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 1][]

> HashMap 中更为危险的是，HashMap 在并发执行扩容操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致 HashMap 的 Entry 链表形成环形数据结构，一旦形成环形数据结构，Entry 的 next 节点永远不为空，就会在获取 Entry 时产生死循环。形成环形链表的原因主要跟 JDK1.7 下 HashMap 发生碰撞后，链表是前序插入有关，后续文章会详细讲述。  
> 具体更为细节方面的原因，大家可以自行查阅资料。

### 如何线程安全的使用HashMap ###

了解了 HashMap 为什么线程不安全，那现在看看如何线程安全的使用 HashMap。这个无非就是以下三种方式：

*  Hashtable
 *  Sysnchronized Map
 *  ConcurrentHashMap

#### Hashtable ####

首先，Hashtable 是将绝大部分方法都加上 synchronized 来保证线程安全的，由于绝大部分方法都同步，所以它的性能低下，是jdk1.0遗弃的类，不建议使用，部分源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 2]

#### Sysnchronized Map ####

Sysnchronized Map 和 Hashtable 相似，也是采用 synchronized 来保证线程安全的，唯一不同的是，SysnchronizedMap使用一个 Object 对象进行同步，并且它也没有被没遗弃，部分源码如下：

private static class SynchronizedMap<K,V>
            implements Map<K,V>, Serializable {
        
    
            private final Map<K,V> m;     // Backing Map
            final Object      mutex;
            ...

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 3]

#### ConcurrentHashMap ####

ConcurrentHashMap 是 java.util.concurrent 包下的一个类，该包下拥有许多线程安全、测试良好、高性能的类，大家有兴趣可以去看看。同 Hashtable 相比，ConcurrentHashMap 不仅保证了访问的线程安全性，而且在效率上有较大的提高。ConcurrentHashMap 的数据结构图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 4]

可以看出，相对 HashMap 和 Hashtable， ConcurrentHashMap 增加了Segment 层，每个 Segment 原理上等同于一个 Hashtable。

final Segment<K,V> segmentFor(int hash) {
        
            return segments[(hash >>> segmentShift) & segmentMask];
        }
    public V put(K key, V value) {
        
            if (value == null)
                throw new NullPointerException();
            int hash = hash(key.hashCode());
            return segmentFor(hash).put(key, hash, value, false);
        }
    public V get(Object key) {
        
            int hash = hash(key.hashCode());
            return segmentFor(hash).get(key, hash);
        }

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

### 性能对比 ###

孰优孰劣，空口无凭，下面的代码分别通过`Hashtable`、`SynchronizedMap`、`ConcurrentHashMap`三种方式创建 Map 对象，使用来并发运行5个线程，每个线程`添加/获取`500K个元素。

public class CrunchifyConcurrentHashMapVsSynchronizedMap {
        
        public final static int THREAD_POOL_SIZE = 5;
        public static Map<String, Integer> crunchifyHashTableObject = null;
        public static Map<String, Integer> crunchifySynchronizedMapObject = null;
        public static Map<String, Integer> crunchifyConcurrentHashMapObject = null;
        public static void main(String[] args) throws InterruptedException {
        
            // Test with Hashtable Object
            crunchifyHashTableObject = new Hashtable<>();
            crunchifyPerformTest(crunchifyHashTableObject);
            // Test with synchronizedMap Object
            crunchifySynchronizedMapObject = Collections.synchronizedMap(new HashMap<String, Integer>());
            crunchifyPerformTest(crunchifySynchronizedMapObject);
            // Test with ConcurrentHashMap Object
            crunchifyConcurrentHashMapObject = new ConcurrentHashMap<>();
            crunchifyPerformTest(crunchifyConcurrentHashMapObject);
        }
        public static void crunchifyPerformTest(final Map<String, Integer> crunchifyThreads) throws InterruptedException {
        
            System.out.println("Test started for: " + crunchifyThreads.getClass());
            long averageTime = 0;
            for (int i = 0; i < 5; i++) {
        
                long startTime = System.nanoTime();
                ExecutorService crunchifyExServer = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
                for (int j = 0; j < THREAD_POOL_SIZE; j++) {
        
                    crunchifyExServer.execute(new Runnable() {
        
                        @SuppressWarnings("unused")
                        @Override
                        public void run() {
        
                            for (int i = 0; i < 500000; i++) {
        
                                Integer crunchifyRandomNumber = (int) Math.ceil(Math.random() * 550000);
                                // Retrieve value. We are not using it anywhere
                                Integer crunchifyValue = crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));
                                // Put value
                                crunchifyThreads.put(String.valueOf(crunchifyRandomNumber), crunchifyRandomNumber);
                            }
                        }
                    });
                }
                // Make sure executor stops
                crunchifyExServer.shutdown();
                // Blocks until all tasks have completed execution after a shutdown request
                crunchifyExServer.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
                long entTime = System.nanoTime();
                long totalTime = (entTime - startTime) / 1000000L;
                averageTime += totalTime;
                System.out.println("2500K entried added/retrieved in " + totalTime + " ms");
            }
            System.out.println("For " + crunchifyThreads.getClass() + " the average time is " + averageTime / 5 + " ms\n");
        }
    }

测试数据结果如下，可以明显看出`HashTable`、`SynchronizedMap`两者的效率接近，而`ConcurrentHashMap`的效率是明显比另外两者高的：

Test started for: class java.util.Hashtable
    2500K entried added/retrieved in 4238 ms
    2500K entried added/retrieved in 3806 ms
    2500K entried added/retrieved in 3992 ms
    2500K entried added/retrieved in 3725 ms
    2500K entried added/retrieved in 4040 ms
    For class java.util.Hashtable the average time is 3960 ms
    
    Test started for: class java.util.Collections$SynchronizedMap
    2500K entried added/retrieved in 5618 ms
    2500K entried added/retrieved in 3759 ms
    2500K entried added/retrieved in 3921 ms
    2500K entried added/retrieved in 3626 ms
    2500K entried added/retrieved in 3791 ms
    For class java.util.Collections$SynchronizedMap the average time is 4143 ms
    
    Test started for: class java.util.concurrent.ConcurrentHashMap
    2500K entried added/retrieved in 2884 ms
    2500K entried added/retrieved in 2272 ms
    2500K entried added/retrieved in 2383 ms
    2500K entried added/retrieved in 2221 ms
    2500K entried added/retrieved in 3975 ms
    For class java.util.concurrent.ConcurrentHashMap the average time is 2747 ms

PS: 写于 2018 年 6 月 6 日

[20210516215351254.png]: /images/20221020/d6d673dbaef3455c83cca3efd7552abe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70]: /images/20221020/4996f581528a4ab4a11fc0743ab911d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 1]: /images/20221020/2b352e29ef2d4e65a132b9f46a23660b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 2]: /images/20221020/afde0c41544f4d8ebfe147a44a184d15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 3]: /images/20221020/179740d6ca2c4a3d8d5bf6e4b483f0d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTA0NDUz_size_16_color_FFFFFF_t_70 4]: /images/20221020/d223f515a5e94c6f953915742a38bf89.png