再三提醒，使用HashMap的时候小心点

川长思鸟来 2023-10-14 22:28 3阅读 0赞

## Map家族介绍 ##

我们都知道HashMap是线程不安全的，但是HashMap的使用频率在所有Map中确实属于比较高的。因为它可以满足我们大多数的场景了。

看一眼Map家族的关系图：

![ad1b58a34bb44a26b7fdb0d79601f44e.png][]![31b755e0f5464417915bc759202a2151_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_Lb5Gwi5UuvCTrOJlMORU61S6GYc_3D][]

Map是一个接口，我们常用的实现类有HashMap、LinkedHashMap、TreeMap，HashTable。

## HashMap ##

HashMap根据key的·值来保存value，需要注意的是，HashMap不保证遍历的顺序和插入的顺序是一致的。HashMap允许有一条记录的key为null，但是对值是否为null不做要求。

## HashTable ##

HashTable类是线程安全的，它使用synchronize来做线程安全，全局只有一把锁，在线程竞争比较激烈的情况下hashtable的效率是比较低下的。因为当一个线程访问hashtable的同步方法时，其他线程再次尝试访问的时候，会进入阻塞或者轮询状态，比如当线程1使用put进行元素添加的时候，线程2不但不能使用put来添加元素，而且不能使用get获取元素。所以，竞争会越来越激烈。相比之下，ConcurrentHashMap使用了分段锁技术来提高了并发度，不在同一段的数据互相不影响，多个线程对多个不同的段的操作是不会相互影响的。每个段使用一把锁。所以在需要线程安全的业务场景下，推荐使用ConcurrentHashMap，而HashTable不建议在新的代码中使用，如果需要线程安全，则使用ConcurrentHashMap，否则使用HashMap就足够了。

## LinkedHashMap ##

LinkedHashMap属于HashMap的子类，与HashMap的区别在于LinkedHashMap保存了记录插入的顺序。

## TreeMap ##

TreeMap实现了SortedMap接口，TreeMap有能力对插入的记录根据key排序，默认按照升序排序，也可以自定义比较强，在使用TreeMap的时候，key应当实现Comparable。

## HashMap的实现 ##

Java7和Java7在实现HashMap上有所区别，当然Java7的效率要更好一些，主要是Java7的HashMap在Java7的基础上增加了红黑树这种数据结构，使得在桶里面查找数据的复杂度从O(n)降到O(logn)，当然还有一些其他的优化，比如resize的优化等。 介于Java7的HashMap较为复杂，本文将基于Java7的HashMap实现来说明，主要的实现部分还是一致的，Java7的实现上主要是做了一些优化，内容还是没有变化的，依然是线程不安全的。 HashMap的实现使用了一个数组，每个数组项里面有一个链表的方式来实现，因为HashMap使用key的hashCode来寻找存储位置，不同的key可能具有相同的hashCode，这时候就出现哈希冲突了，也叫做哈希碰撞，为了解决哈希冲突，有开放地址方法，以及链地址方法。HashMap的实现上选取了链地址方法，也就是将哈希值一样的entry保存在同一个数组项里面，可以把一个数组项当做一个桶，桶里面装的entry的key的hashCode是一样的。

![a16009857d53426185e980c0c6a7b9cd.png][]![dfea8d173845402ca23bd99b2762992b_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_5F7S07eyFREXb1pAdeP0Ch2Tafw_3D][]

上面的图片展示了我们的描述，其中有一个非常重要的数据结构Node<K,V>，这就是实际保存我们的key-value对的数据结构，下面是这个数据结构的主要内容：

final int hash;    
    final K key;
    V value;
    Node<K,V> next;

一个Node就是一个链表节点，也就是我们插入的一条记录，明白了HashMap使用链地址方法来解决哈希冲突之后，我们就不难理解上面的数据结构，hash字段用来定位桶的索引位置，key和value就是我们的数据内容，需要注意的是，我们的key是final的，也就是不允许更改，这也好理解，因为HashMap使用key的hashCode来寻找桶的索引位置，一旦key被改变了，那么key的hashCode很可能就会改变了，所以随意改变key会使得我们丢失记录（无法找到记录）。next字段指向链表的下一个节点。

HashMap的初始桶的数量为16，loadFact为0.75,当桶里面的数据记录超过阈值的时候，HashMap将会进行扩容则操作，每次都会变为原来大小的2倍，直到设定的最大值之后就无法再resize了。

下面对HashMap的实现做简单的介绍，具体实现还得看代码，对于Java7中的HashMap实现，还需要能理解红黑树这种数据结构。

1、根据key的hashCode来决定应该将该记录放在哪个桶里面，无论是插入、查找还是删除，这都是第一步，计算桶的位置。因为HashMap的length总是2的n次幂，所以可以使用下面的方法来做模运算：

h & (length-1)

h是key的hashCode值，计算好hashCode之后，使用上面的方法来对桶的数量取模，将这个数据记录落到某一个桶里面。当然取模是Java7中的做法，Java7进行了优化，做得更加巧妙，因为我们的length总是2的n次幂，所以在一次resize之后，当前位置的记录要么保持当前位置不变，要么就向前移动length就可以了。所以Java7中的HashMap的resize不需要重新计算hashCode。我们可以通过观察java7中的计算方法来抽象出算法，然后进行优化，具体的细节看代码就可以了。

2、HashMap的put方法

![e2619afd41d1485eb99a095644646610.png][]![2b7f9747e4dd426da325fce9de95d38b_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_PsVnPRZcI3TpLJ8cScWdFpgGeQE_3D][]

上图展示了Java7中put方法的处理逻辑，比Java7多了红黑树部分，以及在一些细节上的优化，put逻辑和Java7中是一致的。

3、resize机制

HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组，然后将原先的记录逐个重新映射到新的桶里面，然后将原先的桶逐个置为null使得引用失效。后面会讲到，HashMap之所以线程不安全，就是resize这里出的问题。

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

上面说到，HashMap会进行resize操作，在resize操作的时候会造成线程不安全。下面将举两个可能出现线程不安全的地方。

**1、put的时候导致的多线程数据不一致。** 这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

**2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%），具体分析如下：**

下面的代码是resize的核心内容：

void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {  
            while(null != e) {  
                Entry<K,V> next = e.next;           
                if (rehash) {  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } 
        }  
    }

这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去。

![860d59f1fdc44270bec56df6814fa50e.png][]![3512cccd5e9c4067a2caa8e5133a840e_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_jnfp2oxWgPEZl_2FHMuY_2BI7DUysyM_3D][]

**多线程HashMap的resize**：我们假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：\[3,A\]，\[7,B\]，\[5,C\]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。 假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = \[3,A\], next = \[7,B\]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的\[7,B\]的next为\[3,A\]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将\[3,A\]迁移到新的数组上，然后再处理\[7,B\]，而\[7,B\]被链接到了\[3,A\]的后面，处理完\[7,B\]之后，就需要处理\[7,B\]的next了啊，而通过thread2的resize之后，\[7,B\]的next变为了\[3,A\]，此时，\[3,A\]和\[7,B\]形成了环形链表，在get的时候，如果get的key的桶索引和\[3,A\]和\[7,B\]一样，那么就会陷入死循环。

如果在取链表的时候从头开始取（现在是从尾部开始取）的话，则可以保证节点之间的顺序，那样就不存在这样的问题了。

综合上面两点，可以说明HashMap是线程不安全的。

[ad1b58a34bb44a26b7fdb0d79601f44e.png]: https://img-blog.csdnimg.cn/ad1b58a34bb44a26b7fdb0d79601f44e.png
[31b755e0f5464417915bc759202a2151_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_Lb5Gwi5UuvCTrOJlMORU61S6GYc_3D]: https://p26-sign.toutiaoimg.com/pgc-image/31b755e0f5464417915bc759202a2151~tplv-tt-origin-asy1:5aS05p2hQOS7o-eggeWwj-W9k-Wutg==.image?_iz=58558&from=article.pc_detail&x-expires=1692934927&x-signature=Lb5Gwi5UuvCTrOJlMORU61S6GYc%3D
[a16009857d53426185e980c0c6a7b9cd.png]: https://img-blog.csdnimg.cn/a16009857d53426185e980c0c6a7b9cd.png
[dfea8d173845402ca23bd99b2762992b_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_5F7S07eyFREXb1pAdeP0Ch2Tafw_3D]: https://p3-sign.toutiaoimg.com/pgc-image/dfea8d173845402ca23bd99b2762992b~tplv-tt-origin-asy1:5aS05p2hQOS7o-eggeWwj-W9k-Wutg==.image?_iz=58558&from=article.pc_detail&x-expires=1692934927&x-signature=5F7S07eyFREXb1pAdeP0Ch2Tafw%3D
[e2619afd41d1485eb99a095644646610.png]: https://img-blog.csdnimg.cn/e2619afd41d1485eb99a095644646610.png
[2b7f9747e4dd426da325fce9de95d38b_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_PsVnPRZcI3TpLJ8cScWdFpgGeQE_3D]: https://p26-sign.toutiaoimg.com/pgc-image/2b7f9747e4dd426da325fce9de95d38b~tplv-tt-origin-asy1:5aS05p2hQOS7o-eggeWwj-W9k-Wutg==.image?_iz=58558&from=article.pc_detail&x-expires=1692934927&x-signature=PsVnPRZcI3TpLJ8cScWdFpgGeQE%3D
[860d59f1fdc44270bec56df6814fa50e.png]: https://img-blog.csdnimg.cn/860d59f1fdc44270bec56df6814fa50e.png
[3512cccd5e9c4067a2caa8e5133a840e_tplv-tt-origin-asy1_5aS05p2hQOS7o-eggeWwj-W9k-Wutg_.image_iz_58558_from_article.pc_detail_x-expires_1692934927_x-signature_jnfp2oxWgPEZl_2FHMuY_2BI7DUysyM_3D]: https://p3-sign.toutiaoimg.com/pgc-image/3512cccd5e9c4067a2caa8e5133a840e~tplv-tt-origin-asy1:5aS05p2hQOS7o-eggeWwj-W9k-Wutg==.image?_iz=58558&from=article.pc_detail&x-expires=1692934927&x-signature=jnfp2oxWgPEZl%2FHMuY%2BI7DUysyM%3D

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关 Hashmap知识点

目录 1.未被重写的hashCode() 和equal()方法 2.在HashMap中，判断两个对象(key)是否相等的规则: 3.为什么要重写equal方法？ 4.为

骑猪看日落/ 2024年03月29日 14:47/ 0 赞/ 103 阅读

相关面试题：为什么HashMap 使用的时候指定容量？

文章目录前言正文为什么要指定容量？ -------------------- 前言其实可以看到我写了这么久的博客，很少去写has

青旅半醒/ 2024年02月20日 09:25/ 0 赞/ 82 阅读

相关再三提醒，使用HashMap的时候小心点

Map家族介绍我们都知道HashMap是线程不安全的，但是HashMap的使用频率在所有Map中确实属于比较高的。因为它可以满足我们大多数的场景了。看一眼Map家族

川长思鸟来/ 2023年10月14日 22:28/ 0 赞/ 4 阅读

相关为什么hashmap扩容的时候是2倍

避免Hash冲突在存入元素时，放入元素位置有一个(n-1)&hash的一个算法，和hash&(newCap -1)的一个算法。 ![在这里插入图片描述][713e2

ゞ浴缸里的玫瑰/ 2023年10月13日 23:18/ 0 赞/ 178 阅读

相关 HashMap 什么时候进行扩容呢

HashMap扩容: 　　当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对HashMap的数组进行

Dear 丶/ 2023年10月06日 16:37/ 0 赞/ 88 阅读

相关面试官：为什么HashMap 使用的时候指定容量？

前言其实可以看到我写了这么久的博客，很少去写hashMap的东西。为什么？因为这个东西感觉是java面试必备的，我感觉大家都看到腻了，所以一直没怎么去写hash

拼搏现实的明天。/ 2023年09月23日 16:35/ 0 赞/ 92 阅读

相关 HashMap的一些面试点

数据结构数组+链表 ·tip：当某一个key长度超过8，则链表转化成红黑树存储。 Hash算法优化 static final int hash(Obj

喜欢ヅ旅行/ 2022年12月09日 04:55/ 0 赞/ 107 阅读

相关小心小心再小心－缓冲区溢出

include <stdio.h> include <string.h> int checkpass( void){ int x;

野性酷女/ 2022年08月10日 11:51/ 0 赞/ 309 阅读

相关 java中split的坑，用的时候一定要小心

1.一些特殊业务场景，对自己拼接出来的字符串使用split分割，假设我们已经知道了这个长度，也许我们会这么写。 String ids = "1,2,3,";

雨点打透心脏的1/2处/ 2022年07月14日 04:58/ 0 赞/ 314 阅读

相关 Mybatis #和$使用的安全性提醒

使用$符号一般情况下是在 LIKE 模糊查询的时候，例如 SELECT \ FROM User WHERE name LIKE '%$\{name\}%' 但是这个情况很

亦凉/ 2022年06月01日 08:44/ 0 赞/ 216 阅读