源码分析之五种Map容器的区别

ゞ浴缸里的玫瑰 2022-11-17 13:36 102阅读 0赞

### 源码分析之五种Map容器的区别 ###

*   *  1、Java中的Map容器概述
     *  2、HashMap容器
     *  3、Hashtable容器
     *  4、ConcurrentHashMap容器
     *  5、LinkedHashMap容器
     *  6、TreeMap容器
     *  7、往期佳文
     *   *  7.1、面试系列
         *  7.2、技术系列
         *  7.3、源码系列
         *  7.4、数据结构和算法系列
         *  7.5、多线程系列

## 1、Java中的Map容器概述 ##

Map是一种存储key-value（键值对）的容器，在Java中，常见的Map接口的实现类有五种，分别是HashMap、Hashtable、ConcurrentHashMap、LinkedHashMap、TreeMap。五种容器的关系如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]  
      注意不能把：hash与map两个概念混为一谈，然而map是用于存储key-value的虚拟容器，按照key的hash值将节点散列到一个table数组（也称hash表）的table\[i\]（也称hash桶）中。

## 2、HashMap容器 ##

Java中的HashMap底层使用一个table数组存放节点，使用链表（JDK 1.8新增红黑树）解决hash冲突（多个元素的hash值散列到同一个table\[i\]中）的问题。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 1]  
特点：

1.  存取高效，不支持并发读写操作（没有引入锁任何机制）
2.  table数组的长默认是16，并且每次扩容为原来的2倍（长度总是保持为2的次幂，方便hash值求余）
3.  支持key、value为null的键值对插入

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

## 3、Hashtable容器 ##

Java中的Hashtable底层同样是使用一个table数组存放节点，使用链表解决hash冲突（多个元素的hash值散列到同一个table\[i\]中）的问题。不过引入了锁机制（通过synchronized关键字，锁为this，每次锁住整个容器），支持并发操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 2]  
特点：

1.  写入、删除效率相对较低。引入锁机制，通过synchronized关键字修饰方法（同步方法），锁对象为this，每次锁住整个容器，锁的粒度太大。
2.  table数组的长默认是11，并且每次扩容为原来的2倍 + 1
3.  不支持key、value为null的键值对插入

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

## 4、ConcurrentHashMap容器 ##

Java中的ConcurrentHashMap底层同样是使用一个table数组存放节点，使用链表解决hash冲突（多个元素的hash值散列到同一个table\[i\]中）的问题。在JDK 1.8前的版本中引入段的概念，使用RententLock锁，并且分段锁（对每个段分别设置一个锁），相比于Hashtable锁整个容器，并发操作时，效率提高了不少。  
      在JDK 1.8的时候，又取消了段的概念，重新使用synchronized关键字（同步代码块）。不过每次锁住的对象的是需要修改的table\[i\]（hash桶），并且在各大方法中尽量减少了同步代码块中的代码量，从而减少了锁的粒度，并发操作时，效率提高了不少。在扩容时，支持多个线程同时进行扩容（并发扩容）。  
JDK1.7:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 3]  
JDK1.8:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 4]  
特点：

1.  写入、删除效率相比与Hashtable容器较高。引入锁机制，通过synchronized关键字（同步代码块），锁对象为即将修改的table\[i\]（hash桶），锁的粒度小。
2.  table数组的长默认是16，并且每次扩容为原来的2倍（长度总是保持为2的次幂，方便hash值求余）
3.  不支持key、value为null的键值对插入

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

## 5、LinkedHashMap容器 ##

Java中的LinkedHashMap是HashMap的子类，也可以说是对HashMap的封装。对外展示的是一个双向链表，链表中的元素顺序，就是插入节点的顺序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 5]  
特点：

1.  LinkedHashMap是对HashMap的进一步封装，所以实现细节基本一致
2.  对外展示为双向链表，链表节点中的顺序为插入时的顺序（其实也可以修改为访问顺序）

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

## 6、TreeMap容器 ##

Java中的TreeMap容器底层是通过维护一棵红黑树来存储key-value节点，与hash没有任何关系。树中的节点按照key的大小排序，可以手动指定key的比较器comparator。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 6]  
特点：

1.  读写高效，查找的复杂度在O(log2n)级别。（不支持并发读写，为引入锁）
2.  节点按照key升序排列，可指定key的比较器comparator
3.  不支持key为null的key-value插入

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

## 7、往期佳文 ##

### 7.1、面试系列 ###

1、[吊打面试官之一面自我介绍][Link 1]  
2、[吊打面试官之一面项目介绍][Link 2]  
3、[吊打面试官之一面系统架构设计][Link 3]  
4、[吊打面试官之一面你负责哪一块][Link 4]  
5、[吊打面试官之一面试官提问][Link 5]  
6、[吊打面试官之一面你有什么问题吗][Link 6]

······持续更新中······

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

### 7.2、技术系列 ###

1、[吊打面试官之分布式会话][Link 7]  
2、[吊打面试官之分布式锁][Link 8]  
3、[吊打面试官之乐观锁][Link 9]  
4、[吊打面试官之幂等性问题][Link 10]  
5、[吊打面试关之分布式事务][Link 11]  
6、[吊打面试官之项目线上问题排查][Link 12]

······持续更新中······

### 7.3、源码系列 ###

1、[源码分析之SpringBoot启动流程原理][SpringBoot]  
2、[源码分析之SpringBoot自动装配原理][SpringBoot 1]  
3、[源码分析之ArrayList容器][ArrayList]  
4、[源码分析之LinkedList容器][LinkedList]  
5、[源码分析之HashMap容器][HashMap]  
6、[源码分析之ConcurrentHashMap容器][ConcurrentHashMap]

### 7.4、数据结构和算法系列 ###

1、[数据结构之八大数据结构][Link 13]  
2、[数据结构之动态查找树（二叉查找树，平衡二叉树，红黑树）][Link 14]

······持续更新中······

### 7.5、多线程系列 ###

1、[并发系列之初识多线程][Link 15]  
2、[并发系列之JMM内存模型][JMM]  
3、[并发系列之synchronized解析][synchronized]  
4、[并发系列之volatile解析][volatile]  
5、[并发系列之synchronized与volatile的区别][synchronized_volatile]  
6、[并发系列之Lock解析][Lock]  
7、[并发系列之synchronized与lock的区别][synchronized_lock]

······持续更新中······

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]: /images/20221022/4efe5d397c974f93abbe5a7b4c34c7b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/12a6e27c8de04ba4a9c79925e62837d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/99a74545194d45f8b43f8406b1c60b48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/484830b8144546abb87afc3aeeff918c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 4]: /images/20221022/e794d2945613435a9f9972ab0f939c6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 5]: /images/20221022/2d5d2fddc59042ed82df5fe7b0330604.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 6]: /images/20221022/009a3cfbd0a4498b9929633846bf513c.png
[Link 1]: https://blog.csdn.net/wtyicy/article/details/114933478
[Link 2]: https://blog.csdn.net/wtyicy/article/details/114983053
[Link 3]: https://blog.csdn.net/wtyicy/article/details/115005012
[Link 4]: https://blog.csdn.net/wtyicy/article/details/115064661
[Link 5]: https://blog.csdn.net/wtyicy/article/details/115296365
[Link 6]: https://blog.csdn.net/wtyicy/article/details/115402511
[Link 7]: https://blog.csdn.net/wtyicy/article/details/114685293
[Link 8]: https://blog.csdn.net/wtyicy/article/details/114915987
[Link 9]: https://blog.csdn.net/wtyicy/article/details/114915177
[Link 10]: https://blog.csdn.net/wtyicy/article/details/114888754
[Link 11]: https://blog.csdn.net/wtyicy/article/details/115081790
[Link 12]: https://blog.csdn.net/wtyicy/article/details/115292969
[SpringBoot]: https://blog.csdn.net/wtyicy/article/details/115181539
[SpringBoot 1]: https://blog.csdn.net/wtyicy/article/details/115233701
[ArrayList]: https://blog.csdn.net/wtyicy/article/details/115244565
[LinkedList]: https://blog.csdn.net/wtyicy/article/details/115314536
[HashMap]: https://blog.csdn.net/wtyicy/article/details/115365586
[ConcurrentHashMap]: https://blog.csdn.net/wtyicy/article/details/115549277
[Link 13]: https://blog.csdn.net/wtyicy/article/details/115342236
[Link 14]: https://blog.csdn.net/wtyicy/article/details/115353145
[Link 15]: https://blog.csdn.net/wtyicy/article/details/115386707
[JMM]: https://blog.csdn.net/wtyicy/article/details/115455467
[synchronized]: https://blog.csdn.net/wtyicy/article/details/115454573
[volatile]: https://blog.csdn.net/wtyicy/article/details/115502376
[synchronized_volatile]: https://blog.csdn.net/wtyicy/article/details/115512541
[Lock]: https://blog.csdn.net/wtyicy/article/details/115524613
[synchronized_lock]: https://blog.csdn.net/wtyicy/article/details/115536187