HashMap、HashTable、CurrentHashMap对比

客官°小女子只卖身不卖艺 2024-04-23 15:58 5阅读 0赞

>  *  😜**作** **者**：[是江迪呀][Link 1]
>  *  ✒️**本文关键词**：`Java`、`集合`、`Map`、`CurrentHashMap`
>  *  ☀️**每日 一言**：`坚持自己的风格，面对未知的一切！`

![在这里插入图片描述][0e7db85f226c4b77928a52145cd2441b.png_pic_center]

## 一、`HashMap`、`HashTable`、`CurrentHashMap`对比 ##

### 1.1 `CurrentHashMap`和`HashMap`对比 ###

由于`HashMap`在多线程下不安全诞生了`HashTable`由于`HashTable`效率太低诞生了`CurrentHashMap`。`CurrentHashMap`它大量的使用了`volatile`，`final`，`CAS`等`lock-free`技术来减少锁竞争对于性能的影响。`ConcurrentHashMap`避免了对全局加锁改成了局部加锁操作。这样就极大的提高了 并发环境下的操作速度。

所以`CurrentHashMap`线程是安全的，`HashMap`线程不安全，在多线程下，使用`HashMap`进行`put`操作或造成**死循环**，导致`CPU`的利用率接近100%，使用并发情况下不能使用`HashMap`

### 1.2 `HashMap`和`HashTable`对比 ###

`HashMap`和`HashTable`的实现原理几乎一致，差别是：`HashTable`不允许`key`和`value`为`nul`l。`HashTable`是线程安全的。但是`Hastable`实现线程安全的代价很大，`get/put`的所有相关操作都是`synchronized`的，这相当于给`hash`表加上了一把大锁，多发生多线程操作`HashTable`时，只要有一个线程操作`HashTable`其它线程必须阻塞，相当于将所有**多线程操作串行化**，性能和效率很差。

## 二、JDK1.7`ConcurrentHashMap`实现原理 ##

在JDK1.7中`ConcurrentHashMap`使用的是**数组**\+`Segment`\+`分段锁`对的方式实现。`Segment（分段锁）`–减少锁的粒度，`ConcurrentHashMap`中的分段锁被称为`Segment`，它类似与 `HashMap`对的结构，及内部拥有一个`Entry`数组，数组中的每个元素又是一个**链表**。同时又是一个`ReentrantLock`（Segment继承了`ReentrantLock`）

### 2.1 `ConcurrentHashMap`的内部结构 ###

`ConcurrentHashMap`采用分段锁技术，将数据分为一段一段存储， 然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其它段的数据也能被其它线程访问。能够实现真正意义的并发访问，`ConcurrentHashMap`结构图：  
![在这里插入图片描述][d7d6114e9de843ee85855a86a0f4f94f.png]

从上面的结构我们可以看出，`ConcurrentHashMap`定位一个元素的过程需要进行两次操作。第一次定位到底`Segment`，第二次定位定位到元素所在的链表的头部。  
好处：写操作的时候可以只对元素所在的`Segment`进行加锁即可，不会影响到 其它的`Segment`，这样在理想状态下，`ConcurrentHashMap`可以最高同时支持和`Segment`数量一样多的写操作（刚好这些写操作都非常平均的分配到，所有的`Segment`上）并发能力可以大大的提高。  
坏处：这种结构带来的副作用就是，存值时的过程要比`HashMap`要长。`Segment`的数量是根据并发总量来决定的，比如来说，并发总量是8，那么segment的数量就是8

### 2.2 为啥JDK1.8版本的`ConcurrentHashMap`的并发能力可以大大的提高? ###

JDK8中`ConcurrentHashMap`采用了**数组**\+**链表**\+**红黑树**的实现方式来设计，内部采用大量的`CAS`操作。

> `CAS`是`compare and swap`的缩写，就是比较并交换。`CAS`是一种基于锁的操作，是**乐观锁**。  
> 锁分为**乐观锁**和**悲观锁**，悲观锁就是将资源锁住后，等当前获得锁的对象将锁释放后，下一个线程才能访问。而乐观锁采用了宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。  
> CAS操作包含三个操作数：  
> （1）内存位置（V）；  
> （2）预期值（A）；  
> （3）新值（B）；  
> 如果内存地址里面的值和`A`的值是一样的，那么就将内存中的值更新成`B`，`CAS`是通过无限循环来获取数据的，如果第一轮循环中，`a`线程获取地址里面的值被`b`线程修改了，那么`a`线程需要自旋，到下次循环才有可能被执行。

JDK8中彻底放弃了Segment转而采用的是Node。其设计思想不再是1.7中的分段锁机制。  
Node：保存key，value以及key的Hash值的数据结构，其中value和next都是用volatile修饰，保证并发内存的可见性。java8中的ConcurrentHashMap的结构基本和Java8中的HashMap一致，不过保证线程安全。在JDK8中的ConcurrentHashMap引入了红黑树，红黑树是一种性能非常好的二叉查找树，其查找性能是O。当ConcurrentHashMap中的链表的长度大于某个阈值（这个阈值是8）的时候将链表转化为红黑树，以提高查询效率。

## 三、总结 ##

### 3.1 JDK1.8的`ConcurrentHashMap`结构和`Hashmap`的结构比较 ###

JDK1.8的`ConcurrentHashMap`结构和`Hashmap`的结构很接近，只是增加了同步操作来控制并发：

*  **JDK1.7采用：** 数组+Segment+HashEntry
 *  **JDK1.8采用：** Synchronized+CAS+HashEntry+红黑树

### 3.2 JDK1.7和JDK1.8中的ConcurrentHashMap的比较： ###

*  **数据结构：放弃了`Segment`分段锁机制，采用了数组**\+**链表**\+**红黑树**
 *  **保证线程安全机制：** 1.7采用`Segment`分段锁机制，其中`Segment`继承`ReentrantLock`。1.8采用`CAS`\+`Synchronized`保证线程安全。
 *  **锁的粒度：** 1.7采用的对响应进行数据操作的`Segment`加锁，1.8调整为对每个数组元素进行加锁（node）减小了锁的粒度，提高的性能。
 *  链表转化为红黑树。
 *  **查询时间复杂度：** 从原来的遍历链表`O（n）`，变成遍历红黑树`O（LogN）`

[Link 1]: https://blog.csdn.net/qq_42785250?spm=1011.2124.3001.5343
[0e7db85f226c4b77928a52145cd2441b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/102684cb95624e239e2113f7d55359c3.png
[d7d6114e9de843ee85855a86a0f4f94f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/35d75bb39e814e788f31de571dfb5e8d.png