专栏首页Java后端技术栈cwnaitHashMap为什么存在线程不安全呢?

HashMap为什么存在线程不安全呢?

本文主要探讨下HashMap 在多线程环境下容易出现哪些问题,深层次理解其中的HashMap

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

上面展示了java中Map的继承图,Map是一个接口,我们常用的实现类有

HashMap LinkedHashMap TreeMap HashTable

数据覆盖问题

两个线程执行put()操作时,可能导致数据覆盖。JDK1.7版本和JDK1.8版本的都存在此问题,这里以 JDK1.7为例。

假设 A、B 两个线程同时执行put()操作,且两个 key 都指向同一个 buekct,那么此时两个结点,都会做头插法。先看这里的代码实现:

public V put(K key, V value) {
    //...
    addEntry(hash, key, value, i);
}


void addEntry(int hash, K key, V value, int bucketIndex) {
    //...
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

看下最后的createEntry()方法,首先获取到了 bucket 上的头结点,然后再将新结点作为 bucket 的头部,并指向旧的头结点,完成一次头插法的操作。当线程 A 和线程 B 都获取到了 bucket 的头结点后,若此时线程 A 的时间片用完,线程 B 将其新数据完成了头插法操作,此时轮到线程 A 操作,但这时线程 A 所据有的旧头结点已经过时了(并未包含线程 B 刚插入的新结点),线程 A 再做头插法操作,就会抹掉 B 刚刚新增的结点,导致数据丢失。

其实不光是put()操作,删除操作、修改操作,同样都会有覆盖问题。

扩容时导致死循环

这是最常遇到的情况,也是面试经常被问及的考题。但说实话,这个多线程环境下导致的死循环问题,并不是那么容易解释清楚,因为这里已经深入到了扩容的细节。这里尽可能简单的描述死循环的产生过程。

另外,只有 JDK1.7 及以前的版本会存在死循环现象,在JDK1.8 中,resize()方式已经做了调整,使用两队链表,且都是使用的尾插法,及时多线程下,也顶多是从头结点再做一次尾插法,不会造成死循环。而JDK1.7能造成死循环,就是因为 resize()时使用了头插法,将原本的顺序做了反转,才留下了死循环的机会。

在进一步说明死循环的过程前,我们先看下JDK1.7中的扩容代码片段:

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;
        }
    }
}

这段代码是HashMap的扩容操作,重新定位每个桶的下标,并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转,这也是形成死循环的关键点。

其实就是简单的链表反转,再进一步简化的话,分为当前结点e,以及下一个结点e.next。我们以链表a->b->c->null为例,两个线程 A 和 B,分别做扩容操作。

原表:

线程 A 和 B 各自新增了一个新的哈希 table,在线程 A 已做完扩容操作后,线程 B 才开始扩容。此时对于线程 B 来说,当前结点e指向 a 结点,下一个结点e.next仍然指向 b 结点(此时在线程 A 的链表中,已经是c->b->a的顺序)。按照头插法,哈希表的 bucket 指向 a 结点,此时 a 结点成为线程 B 中链表的头结点,如下图所示:

a 结点成为线程 B 中链表的头结点后,下一个结点e.next为 b 结点。既然下一个结点e.next不为 null,那么当前结点e就变成了 b 结点,下一个结点e.next变为 a 结点。继续执行头插法,将 b 变为链表的头结点,同时 next 指针指向旧的头节点 a,如下图:

此时,下一个结点e.next为 a 节点,不为 null,继续头插法。指针后移,那么当前结点e就成为了 a 结点,下一个结点为 null。将 a 结点作为线程 B 链表中的头结点,并将 next 指针指向原来的旧头结点 b,如下图所示:

此时,已形成环链表。同时下一个结点e.next为 null,流程结束。

总结

如果想在多线程环境下使用 HashMap,很容易引起各类问题,上面仅为不安全问题的两个典型示例,具体问题无法一一列举,但大体会分为以下三类:

死循环 数据重复 数据丢失(覆盖)

注意:在JDK1.5之前,多线程环境往往使用 HashTable,但在JDK1.5及以后的版本中,在并发包中引入了专门用于多线程环境的ConcurrentHashMap类,采用分段锁实现了线程安全,相比 HashTable 有更高的性能,推荐使用。

推荐阅读

据说程序员才能看懂的趣图 一次蚂蚁金服的辛酸面试历程 5 个刁钻的 String 面试题!

本文分享自微信公众号 - Java后端技术栈(t-j20120622),作者:田老师

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 重构:改善既有代码的设计.pfd

    因为经历过一段时间的紧张迭代,软件中必然会出现各种因为赶进度或者不规范操作遗留下来的问题文件和代码,若不及时清理,后续一定会造成更多的开销。例如:

    田维常
  • 一个简单的案例带你入门Dubbo分布式框架

    相信有很多小伙伴都知道,dubbo是一个分布式、高性能、透明化的RPC服务框架,提供服务自动注册、自动发现等高效服务治理方案,dubbo的中文文档也是非常全的,...

    田维常
  • 面试官:什么是内部类?|这么回答就妥妥的

    内部类可以用多个实例,每个实例都有自己的状态信息,并且与其他外围对象的信息相互独立。

    田维常
  • 傻瓜都能看懂,30张图彻底理解红黑树!

    当在 10 亿数据中只需要进行十几次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀!

    Rocky0429
  • BTree,B-Tree,B+Tree,B*Tree都是什么

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

    阳光岛主
  • 这 30 张图带你读懂红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    帅地
  • 数据结构与算法 -树

    树型结构是一类重要的非线性结构,树型结构是结点之间有分支, 并且具有层次关系的结构,它非常类似于自然界中的树。

    越陌度阡
  • java源码之树与二叉树

    树(Tree)是n(n≥0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中:

    Java阿呆
  • 30 张图带你彻底理解红黑树

    小吴正在写红黑树的相关系列文章,不过内容太多,动画做起来比较慢,大家可以先看一下这篇红黑树的介绍,内容很不错。

    五分钟学算法
  • 树型结构--树的定义和基本术语(十六)

    树是n(n>=0)个结点的有限集合T,当n=0时,称为空树,当n>0时,该集合满足如下条件: 1.其中必有一个称为根的特定结点,它没有直接前驱,但是有零个或多...

    花狗Fdog

扫码关注云+社区

领取腾讯云代金券