SynchronizedMap与ConcurrentHashMap的对比

谁践踏了优雅 2022-10-05 05:52 127阅读 0赞

### SynchronizedMap与ConcurrentHashMap的对比 ###

*  如何使用
 *   *  1. 概述
     *   *  ConcurrentHashMap：
         *  SynchronizedMap：
     *  2. 两者源码对比
     *   *  哈希表声明：
         *  put()方法：
         *  get()方法：
     *  3. ConcurrentHashMap详解
     *   *  1. 与HashTable容器对比：
         *  2. get()方法：
         *  3. put()方法：
         *  4. 具体实现：
         *  5. 缺点：
     *  4. ConcurrentHashMap底层实现
     *  5. ConcurrentHashMap的读写过程
     *   *  Get方法：
         *  Put方法：
         *  Size方法
     *  6. 锁分段技术：
     *  7. ConcurrentHashMap 1.7和1.8的区别
     *   *  1️⃣ 整体结构
         *  2️⃣ put()
         *  3️⃣ get()
         *  4️⃣ resize()
         *  5️⃣ size()

# 如何使用 #

ConcurrentHashMap<Object, Object> concurrentMap = new ConcurrentHashMap<>();
            concurrentMap.put("", "");
            concurrentMap.get("");
    
            Map<Object, Object> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
            synchronizedMap.put("", "");
            synchronizedMap.get("");

## 1. 概述 ##

*  ### ConcurrentHashMap： ###

1.  线程安全；
2.  其将整个Hash桶进行了分段segment，也就是将这个大的数组分成了几个小的片段segment，而且每个小的片段segment上面都有锁存在，那么在插入元素的时候就要先找到应该插入到哪一个片段segment，然后再在这个片段上面进行插入，而且这里还需要获取segment锁（即锁分段技术）；
3.  ConcurrentHashMap让锁的粒度更精细一些，并发性能更好；

*  ### SynchronizedMap： ###

1.  线程安全；
2.  通过synchronized关键字进行同步控制；
3.  所有单个的操作都是线程安全的，但是多个操作组成的操作序列却可能导致数据争用，因为在操作序列中控制流取决于前面操作的结果。这也被称作是：有条件的线程安全性；
4.  效率低；

## 2. 两者源码对比 ##

### 哈希表声明： ###

通过下面两图对比可以发现，两者的区别在于volatile关键字

--------------------

*  ConcurrentHashMap：  
    ![在这里插入图片描述][20210607132610940.png]
 *  SynchronizedMap：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051bWJlcl9vbmVFbmdpbmVlcg_size_16_color_FFFFFF_t_70]

### put()方法： ###

--------------------

*  ConcurrentHashMap：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051bWJlcl9vbmVFbmdpbmVlcg_size_16_color_FFFFFF_t_70 1]
 *  SynchronizedMap：  
    ![在这里插入图片描述][20210607132246874.png]

### get()方法： ###

--------------------

*  ConcurrentHashMap：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051bWJlcl9vbmVFbmdpbmVlcg_size_16_color_FFFFFF_t_70 2]
 *  SynchronizedMap：  
    ![在这里插入图片描述][20210607132311379.png]

## 3. ConcurrentHashMap详解 ##

### 1. 与HashTable容器对比： ###

HashTable容器在竞争激烈的并发环境下表现出效率底下的原因是所有访问HashTable的线程都必须竞争同一把锁（其实现是在对应的方法上添加了synchronized关键字进行修饰），那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

### 2. get()方法： ###

其高效之处在于整个get过程不需要加锁，除非读到的值是空的才会加锁重读。get方法里将要使用的共享变量都定义成volatile，如用于统计当前Segement大小的count字段和用于存储值的HashEntry的value。定义成volatile的变量，能够在线程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写（有一种情况可以被线程写，就是写入的值不依赖于原值），在get操作里只需要读不需要写共享变量count和value，所以可以不用加锁。

### 3. put()方法： ###

首先定位到Segment，然后在Segment里进行插入操作。插入操作需要经历两个步骤，第一步判断是否需要对Segment里的HashEntry数组进行扩容，第二步定位添加元素的位置然后放在HashEntry数组里。

### 4. 具体实现： ###

在ConcurrentHashMap的实现中使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16，其中第N个散列桶由第（N mod 16）个锁来保护。假设散列函数具有合理的分布性，并且关键字能够实现均匀分布，那么这大约能把对于锁的请求减少到原来的1/16。正是这项技术使得其能够支持多达16个并发的写入器。  
7.

### 5. 缺点： ###

当ConcurrentHashMap需要扩展映射范围，以及重新计算键值得散列值要分布到更大的桶集合中时，就需要获取分段锁集合中所有的锁（**要获取内置锁的一个集合，采用的唯一方式是递归**）。

## 4. ConcurrentHashMap底层实现 ##

*  底层采用分段的数组+链表实现
 *  通过把整个 Map 分为N个 Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于 HashEntry 的 value 变量是 volatile 的，也能保证读取到最新的值。)
 *  Hashtable 的 synchronized 是针对整张 Hash 表的，即每次锁住整张表让线程独占，ConcurrentHashMap 允许多个修改操作并发进行，其关键在于使用了锁分离技术。
 *  有些方法需要跨段，比如 size() 和 containsValue()，它们可能需要锁定整个表而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。
 *  扩容：段内扩容(段内元素超过该段对应 Entry 数组长度的75%触发扩容，不会对整个 Map 进行扩容)，插入前检测是否需要扩容，避免无效扩容。

ConcurrentHashMap 比 HashMap 多出了一个类 Segment，而 Segment 是一个可重入锁。ConcurrentHashMap 是使用了锁分段技术来保证线程安全的。

HashMap 在高并发下会出现链表环，从而导致程序出现死循环。高并发下避免 HashMap 出问题的方法有两种，一是使用 HashTable，二是使用 Collections.syncronizedMap。但是这两种方法的性能都很差。因为这两个在执行读写操作时都是将整个集合加锁，导致多个线程无法同时读写集合。高并发下的 HashMap 出现的问题就需要 ConcurrentHashMap 来解决了。

## 5. ConcurrentHashMap的读写过程 ##

### Get方法： ###

1.  为输入的 Key 做 Hash 运算，得到 hash 值。(为了实现Segment均匀分布，进行了两次Hash)
2.  通过 hash 值，定位到对应的 Segment 对象
3.  再次通过 hash 值，定位到 Segment 当中数组的具体位置。

### Put方法： ###

1.  为输入的 Key 做 Hash 运算，得到 hash 值。
2.  通过 hash 值，定位到对应的 Segment 对象
3.  获取可重入锁
4.  再次通过 hash 值，定位到 Segment 当中数组的具体位置。
5.  插入或覆盖 HashEntry 对象。
6.  释放锁。

从步骤可以看出，ConcurrentHashMap 在读写时均需要二次定位。首先定位到 Segment，之后定位到 Segment 内的具体数组下标。

### Size方法 ###

ConcurrentHashMap 的 Size() 是一个嵌套循环，大体逻辑如下：

1.  遍历所有的 Segment。
2.  把 Segment 的元素数量累加起来。
3.  把 Segment 的修改次数累加起来。
4.  判断所有 Segment 的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。
5.  如果尝试次数超过阈值，则对每一个 Segment 加锁，再重新统计。
6.  再次判断所有 Segment 的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。  
    释放锁，统计结束。

为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。为了尽量不锁住所有的 Segment，首先乐观地假设 Size 过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有 Segment 保证强一致性。

## 6. 锁分段技术： ##

*  首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据仍能被其他线程访问。
 *  ConcurrentHashMap 提供了与 Hashtable 和 SynchronizedMap 不同的锁机制。Hashtable 中采用的锁机制是一次锁住整个 hash 表，从而在同一时刻只能由一个线程对其进行操作；而 ConcurrentHashMap 中则是一次锁住一个桶。
 *  ConcurrentHashMap 默认将 hash 表分为16个桶，诸如 get、put、remove 等常用操作只锁住当前需要用到的桶。这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。

## 7. ConcurrentHashMap 1.7和1.8的区别 ##

### 1️⃣ 整体结构 ###

*  1.7：Segment + HashEntry + Unsafe
 *  1.8: 移除 Segment，使锁的粒度更小，Synchronized + CAS + Node + Unsafe

### 2️⃣ put() ###

*  1.7：先定位 Segment，再定位桶，put 全程加锁，没有获取锁的线程提前找桶的位置，并最多自旋 64 次获取锁，超过则挂起。
 *  1.8：由于移除了 Segment，类似 HashMap，可以直接定位到桶，拿到 first 节点后进行判断：①为空则 CAS 插入；②为 -1 则说明在扩容，则跟着一起扩容；③ else 则加锁 put(类似1.7)

### 3️⃣ get() ###

*  基本类似，由于 value 声明为 volatile，保证了修改的可见性，因此不需要加锁。

### 4️⃣ resize() ###

*  1.7：跟 HashMap 步骤一样，只不过是搬到单线程中执行，避免了 HashMap 在 1.7 中扩容时死循环的问题，保证线程安全。
 *  1.8：支持并发扩容，HashMap 扩容在1.8中由头插改为尾插(为了避免死循环问题)，ConcurrentHashmap 也是，迁移也是从尾部开始，扩容前在桶的头部放置一个 hash 值为 -1 的节点，这样别的线程访问时就能判断是否该桶已经被其他线程处理过了。

### 5️⃣ size() ###

*  1.7：很经典的思路：计算两次，如果不变则返回计算结果，若不一致，则锁住所有的 Segment 求和。
 *  1.8：用 baseCount 来存储当前的节点个数，这就设计到 baseCount 并发环境下修改的问题。

[20210607132610940.png]: /images/20221005/59022e86d25d42d8b20e2b7bb52bc7f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051bWJlcl9vbmVFbmdpbmVlcg_size_16_color_FFFFFF_t_70]: /images/20221005/1465e489d09c48f484277c4adcc93914.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051bWJlcl9vbmVFbmdpbmVlcg_size_16_color_FFFFFF_t_70 1]: /images/20221005/d641d36c479e46ca997c08ef830816fe.png
[20210607132246874.png]: /images/20221005/30d18a6bb21d4cf4aafdc69b63de02cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051bWJlcl9vbmVFbmdpbmVlcg_size_16_color_FFFFFF_t_70 2]: /images/20221005/cdb4de4fc934493bbf0e76c66a3c1fa6.png
[20210607132311379.png]: /images/20221005/270760c53265475f839dde19a48b3e2e.png