文档章节

【HashMap】HashMap死循环与元素丢失(一)

大白来袭
 大白来袭
发布于 2017/06/24 23:23
字数 1768
阅读 38
收藏 1

前一篇文章讲解了HashMap的实现原理,讲到了HashMap不是线程安全的。那么HashMap在多线程环境下又会有什么问题呢?

公司项目的一个模块在线上运行的时候出现了死循环,死循环的代码就卡在HashMap的get方法上。尽管最终发现不是因为HashMap导致的,但却让我重视了HashMap在多线程环境下会引发死循环的这个问题,下面先用一段代码简单模拟出HashMap的死循环:

    public class HashMapThread extends Thread
    {
        private static AtomicInteger ai = new AtomicInteger(0);
        private static Map<Integer, Integer> map = new HashMap<Integer, Integer>(1);
        public void run()
        {
            while (ai.get() < 100000)
            {
                map.put(ai.get(), ai.get());
                ai.incrementAndGet();
            }
        }
    }

这个线程的作用很简单,给AtomicInteger不断自增并写入HashMap中,其中AtomicInteger和HashMap都是全局共享的, 也就是说所有线程操作的都是同一个AtomicInteger和HashMap。开5个线程操作一下run方法中的代码:

    public static void main(String[] args)
    {
        HashMapThread hmt0 = new HashMapThread();
        HashMapThread hmt1 = new HashMapThread();
        HashMapThread hmt2 = new HashMapThread();
        HashMapThread hmt3 = new HashMapThread();
        HashMapThread hmt4 = new HashMapThread();

        hmt0.start();
        hmt1.start();
        hmt2.start();
        hmt3.start();
        hmt4.start();
    }

多运行几次之后死循环就出来了,我大概运行了7次、8次的样子,其中有几次是数组下标越界异常 ArrayIndexOutOfBoundsException。这里面要提一点,多线程环境下代码会出现问题并不意味着多线程环境下一定会出现问题,但 是只要出现了问题,或者是死锁、或者是死循环,那么你的项目除了重启就没有什么别的办法了,所以代码的线程安全性在开发、评审的时候必须要重点考虑到。 死循环问题的定位一般都是通过jps+jstack查看堆栈信息来定位的:

看到Thread-0处于RUNNABLE,而从堆栈信息上应该可以看出,这次的死循环是由于Thread-0对HashMap进行扩容而引起的。 

正常的扩容过程

先来看一下HashMap一次正常的扩容过程。简单一点看吧,假设我有三个经过了最终rehash得到的数字,分别是5 7 3,HashMap的table也只有2,那么HashMap把这三个数字put进数据结构了之后应该是这么一个样子的:

这应该很好理解。然后看一下resize的代码,上面的堆栈里面就有:

    void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }


    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }


    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

我总结一下这三段代码,HashMap一次扩容的过程应该是:

1、取当前table的2倍作为新table的大小

2、根据算出的新table的大小new出一个新的Entry数组来,名为newTable

3、轮询原table的每一个位置,将每个位置上连接的Entry,算出在新table上的位置,并以链表形式连接

4、原table上的所有Entry全部轮询完毕之后,意味着原table上面的所有Entry已经移到了新的table上,HashMap中的table指向newTable

这样就完成了一次扩容,用图表示是这样的:

扩容导致的死循环

既然是扩容导致的死循环,那么继续看扩容的代码:

    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

两个线程,线程A和线程B。假设第9行执行完毕,线程A切换,那么对于线程A而言,是这样的:

CPU切换到线程B运行,线程B将整个扩容过程全部执行完毕,于是就形成了:

此时CPU切换到线程A上,执行第8行~第14行的do…while…循环,首先放置3这个Entry:

我们必须要知道,由于线程B已经执行完毕,因此根据Java内存模型(JMM),现在table里面所有的Entry都是最新的,也就是7的next是3,3的next是null。3放置到table[3]的位置上了,下面的步骤是:

1、e=next,即e=7

2、判断e不等于null,循环继续

3、next=e.next,即next=7的next,也就是3

4、放置7这个Entry

所以,用图表示就是:

放置完7之后,继续运行代码:

1、e=next,也就是说e=3

2、判断e不等于null,循环继续

3、next=e.next,即3的next,也就是null

4、放置3这个Entry

把3移到table[3]上去,死循环就出来了:

3移到table[3]上去了,3的next指向7,由于原先7的next指向3,这样就成了一个死循环。

此时执行13行的e=next,那么e=null,循环终止。尽管此次循环确实结束了,但是后面的操作,只要涉及轮询HashMap数据结构的,无论是迭代还是扩容,都将在table[3]这个链表处出现死循环。这也就是前面的死循环堆栈出现的原因,transfer的484行,因为这是一次扩容操作,需要遍历HashMap数据结构,transfer方法是扩容的最后一个方法。

OK,前面讲了5 7 3导致了死循环,现在看一下正常的顺序3 5 7,会发生什么问题。简单看一下,就不像上面讲得这么详细了:

这是扩容前数据结构中的内容,扩容之后正常的应该是:

现在在多线程下遇到问题了,某个线程先放7:

再接着放5:

由于5的next此时为null,因此扩容操作结束,3 5 7造成的结果就是元素丢失。

解决

把一个线程非安全的集合作为全局共享的,本身就是一种错误的做法,并发下一定会产生错误。所以,解决这个问题的办法很简单,有两种:

1、使用Collections.synchronizedMap(Mao<K,V> m)方法把HashMap变成一个线程安全的Map

2、使用Hashtable、ConcurrentHashMap这两个线程安全的Map

不过,既然选择了线程安全的办法,那么必然要在性能上付出一定的代价—-毕竟这个世界上没有十全十美的事情,既要运行效率高、又要线程安全。

本文转载自:https://blog.csdn.net/menggudaoke/article/details/52699801

上一篇: LinkdedList
下一篇: Maven使用
大白来袭
粉丝 4
博文 41
码字总数 13667
作品 0
海淀
程序员
私信 提问
如何线程安全的使用HashMap

为什么HashMap是线程不安全的 总说HashMap是线程不安全的,不安全的,不安全的,那么到底为什么它是线程不安全的呢?要回答这个问题就要先来简单了解一下HashMap源码中的使用的存储结构(这里...

Edwyn王
2016/09/02
111
0
HashMap多线程并发问题分析(rehash分析)

HashMap多线程并发问题分析 发表于1年前(2015-03-31 11:40) 阅读(2664) | 评论(1) 12人收藏此文章, 我要收藏 赞1 目录[-] 并发问题的症状 多线程put后可能导致get死循环 多线程put的时候...

tantexian
2016/04/07
359
0
JDK1.8 不一样的HashMap

前言 HashMap想必大家都很熟悉,JDK1.8 的 HashMap 随便一搜都是一大片一大片的,那为什么还要写呢,我会把它精简一下,一方面有利于自己的学习,另一方面希望让大家更好理解核心内容。本篇主...

小坏怎么被用了
2018/01/05
0
0
HashMap在并发场景下踩过的坑

本文来自网易云社区 作者:张伟 关于HashMap在并发场景下的问题有很多人,很多公司遇到过!也很多人总结过,我们很多时候都认为这样都坑距离自己很远,自己一定不会掉入这样都坑。可是我们随...

网易云
2018/09/06
0
0
HashMap在并发下可能出现的问题分析

我们都知道,HashMap在并发环境下使用可能出现问题,但是具体表现,以及为什么出现并发问题, 可能并不是所有人都了解,这篇文章记录一下HashMap在多线程环境下可能出现的问题以及如何避免。...

Elivense
2016/12/26
30
0

没有更多内容

加载失败,请刷新页面

加载更多

作为一个(IT)程序员!聊天没有话题?试试这十二种技巧

首先呢?我是一名程序员,经常性和同事没话题。 因为每天都会有自己的任务要做,程序员对于其他行业来说;是相对来说比较忙的。你会经常看到程序员在发呆、调试密密麻麻代码、红色报错发呆;...

小英子wep
59分钟前
12
0
【SpringBoot】产生背景及简介

一、SpringBoot介绍 Spring Boot 是由 Pivotal 团队提供的全新框架,其设计目的是用来简化新 Spring 应用的初始搭建以及开发过程,该框架使用了特定的方式来进行配置,从而使开发人员不再需要...

zw965
今天
4
0
简述并发编程分为三个核心问题:分工、同步、互斥。

总的来说,并发编程可以总结为三个核心问题:分工、同步、互斥。 所谓分工指的是如何高效地拆解任务并分配给线程,而同步指的是线程之间如何协作,互斥则是保证同一时刻只允许一个线程访问共...

dust8080
今天
6
0
OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌 :#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌,请使劲儿戳(这里) @hxg2016 :刚在...

小小编辑
今天
3.2K
22
靠写代码赚钱的一些门路

作者 @mezod 译者 @josephchang10 如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。 今天给大家分享一个精彩的 GitHub 库,这个库整理...

高级农民工
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部