`

HashMap在java并发中如何发生死循环

 
阅读更多

        在多线程环境中,使用HashMap进行put操作时会引起死循环,导致CPU使用接近100%,下面通过代码分析一下为什么会发生死循环。

      首先先分析一下HashMap的数据结构:HashMap底层数据结构是有一个链表数据构成的,HashMap中定义了一个静态内部类作为链表,代码如下(与本文无关的代码省略):

 

 

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
、
    }

 

 

   

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

    之所以会导致HashMap出现死循环是因为多线程会导致HashMap的Entry节点形成环链,这样当遍历集合时Entry的next节点用于不为空,从而形成死循环

  

 

    单添加元素时会通过key的hash值确认链表数组下标

   

    

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        
        //确认链表数组位置
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        
        //如果key相同则覆盖value部分
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //添加链表节点
        addEntry(hash, key, value, i);
        return null;
    }

 

 

 

   下面看一下HashMap添加节点的实现

 

  

void addEntry(int hash, K key, V value, int bucketIndex) {
 //bucketIndex 通过key的hash值与链表数组的长度计算得出
	Entry<K,V> e = table[bucketIndex];
	//创建链表节点      
  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  
  //判断是否需要扩容
  if (size++ >= threshold)
            resize(2 * table.length);
}

 

 

    以上部分的实现不会导致链路出现环链,环链一般会出现HashMap扩容是,下面看看扩容的实现:

  

  

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

 

 

  下面transfer的实现

 

 

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

   这个方法的目的是将原链表数据的数组拷到新的链表数组中,拷贝过程中如果形成环链的呢?下面用一个简单的例子来说明一下:

 

 

  

public class InfiniteLoop {

    static final Map<Integer, Integer> map = new HashMap<Integer, Integer>(2, 0.75f);

    public static void main(String[] args) throws InterruptedException {

        map.put(5, 55);

        new Thread("Thread1") {
            public void run() {
                map.put(7, 77);
                System.out.println(map);
            };
        }.start();

        new Thread("Thread2") {
            public void run() {
                map.put(3, 33);
                System.out.println(map);
            };
        }.start();

    }

}

 

 

   下面通过debug跟踪调试来看看如果导致HashMap形成环链,断点位置:

  1. 线程1的put操作
  2. 线程2的put操作
  3. 线程2的输出操作
  4. HashMap源码transfer方法中的第一行、第六行、第九行

    测试开始

  

  1.  使线程1进入transfer方法第一行,此时map的结构如下

   

 

    2.  使线程2进入transfer方法第一行,此时map的结构如下:

   



 
 3.接着切换回线程1,执行到transfer的第六行,此时map的结构如下:

 




 
 

4.然后切换回线程2使其执行到transfer方法的第六行,此时map的结够如上

5.接着切换回线程1使其执行到transfer方法的第九行,然后切换回线程2使其执行完,此时map的结构如下:

 



 6.切换回线程1执行循环,因为线程1之前是停在HashMap的transfer方法的第九行处,所以此时transfer方法的节点e的key=3,e.next的key=7

 

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);//线程1等线程2执行结束后
                                                          //从此处开始执行
                                                          //此时e的key=3,e.next.key=7
                                                          //但是此时的e.next.next的key=3了
                                                          //(被线程2修改了)
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
}

  

  下面线程1开始执行第一次循环,循环后的map结构如下:

 

  

 

接着执行第二次循环:e.key=7,e.next.key=3,e.next.next=null

 



 

接着执行第三次循环,从而导致环链形成,map结构如下

 



 并且此时的map中还丢失了key=5的节点

  • 大小: 5.7 KB
  • 大小: 7.1 KB
  • 大小: 8.3 KB
  • 大小: 4.9 KB
  • 大小: 6.5 KB
  • 大小: 7.4 KB
分享到:
评论
1 楼 颜若儒 2017-03-16  
最后一步图是不是画错了,3应该在前面吧

相关推荐

    深入了解JAVA HASHMAP的死循环

    首先,死循环问题通常发生在并发环境中,当多个线程同时修改HashMap时。HashMap的核心数据结构是一个数组(table[]),数组中的每个元素都是一个链表(Entry)。键值对通过哈希函数计算出其在数组中的位置,若存在...

    java7-8中的 HashMap和ConcurrentHashMap全解析

    `HashMap`是非线程安全的,意味着在多线程环境下,多个线程同时操作`HashMap`可能会导致数据不一致或者死循环。因此,如果需要在并发环境中使用,必须使用同步机制,如`synchronized`关键字或`Collections....

    关于如何解决HashMap线程安全问题的介绍

    在多线程环境下,两个线程同时触发扩容可能导致循环链表的形成,从而引发死循环,这是一种严重的性能问题。 为了解决HashMap的线程不安全问题,我们可以采取以下几种策略: 1. 使用Collections.synchronizedMap()...

    马士兵老师HashMap学习笔记

    本文将结合马士兵老师的讲解,详细阐述HashMap在不同JDK版本中的put操作流程,以及可能遇到的死循环问题。 首先,我们来看JDK 8中HashMap的put操作。在JDK 8中,HashMap进行了重大的优化,引入了红黑树(Red-Black ...

    Java并发程序设计+并发

    Java并发程序设计是Java开发中的重要领域,它涉及到如何在多线程环境下高效、安全地执行代码。在Java中,并发编程主要通过类库、工具和技术来实现,这些包括线程、锁、同步机制以及并发容器等。下面将详细介绍Java...

    高级程序员必会的HashMap的线程安全问题,适用于0~2年的.7z

    3. **死循环(死锁)**:在极端情况下,由于HashMap的迭代器依赖于table的状态,如果在迭代过程中table结构发生变化(比如resize),可能会造成迭代器陷入死循环。 为了解决这些问题,有以下几种策略: 1. **使用...

    基于Java HashMap的死循环的启示详解

    Java HashMap的死循环是一个在多线程环境下容易出现的问题,主要由于其内部的迭代器实现方式和并发操作不当引起。本文将深入分析这个问题,并探讨如何避免这类错误。 首先,Java HashMap在非线程安全的环境下,如果...

    java并发编程学习思维导图

    Java并发编程是Java开发中的重要领域,涉及到多线程、同步机制、线程池等多个核心概念,对于提高程序性能和系统资源利用率具有关键作用。在Java中,并发编程的实现主要依赖于Java语言的内置机制,如Thread类、...

    java面试多线程高并发相关回家技巧(超经典)

    1. **ExecutorService**:Java并发框架的核心,用于管理和控制线程池,提供灵活的线程管理。 2. **Future和Callable**:Callable接口允许线程返回结果,Future接口则用来获取线程执行的结果。 3. **CountDownLatch...

    java7hashmap源码-backend-study:后端学习之路

    java7 hashmap源码 随着Java学习的不断深入,发现...多线程下,hashmap的resize()方法为什么容易出现死循环? 答: 其他面试题? 答: 并发 概述 :star::star: :star::star: 线程池 :star: AQS :star: 锁 ListenalbeFut

    hashmap-thread-test:测试 Java HashMap 是否是线程安全的

    在Java编程语言中,`HashMap`是一个非常常用的数据结构,它提供了一种高效的方式来存储和检索键值对。然而,`HashMap`并非线程安全,这意味着在多线程环境中直接使用`HashMap`可能会导致数据不一致、并发问题,甚至...

    jdk1.7 HashMap中的致命错误:循环链表

    然而,在JDK1.7版本中,HashMap存在一个严重的问题,即“循环链表”(Looping List),这可能导致在多线程环境下性能急剧下降,甚至引发死循环。本文将深入探讨这个问题及其解决方案。 首先,我们来看看JDK1.7 ...

    通过面试题带你了解java的Map

    - 当lastRun节点位于全0或全1的链表上,可能导致在扩容时形成死循环,但Java 8的尾插法解决了这个问题。 6. **红黑树的引入**: - 当链表长度达到8时,HashMap会将链表转换为红黑树,以保持O(logN)的查找效率,而...

    并发编程之一 日常学习笔记

    在并发编程中,不合适的并发操作HashMap可能导致数据不一致或者死循环。了解HashMap的内部实现有助于开发者理解为什么需要使用ConcurrentHashMap这样的线程安全数据结构,以及如何在多线程环境中正确使用HashMap。 ...

    Hashmap实现了Map接口的底层实现.docx

    HashMap在多线程环境中并不安全,因为其非线程安全的设计可能导致死循环。例如,在并发扩容时,可能产生环形链表。在这种情况下,尝试获取不存在的键时,可能会导致无限循环。因此,多线程场景推荐使用...

    求职宝典-Java 基础面试题

    在多线程环境下,HashMap的并发操作可能导致死循环问题。在JDK1.7中,rehash过程中的并发修改可能导致链表循环,而在JDK1.8中,虽然采用了红黑树,但仍然存在类似问题。为了解决这个问题,应使用ConcurrentHashMap,...

    HashMap源码分析系列-第四弹:HashMap多线程解决方案.docx

    1. **链表死循环问题**:在JDK 1.7中,当多个线程同时进行`put`操作时,可能会出现链表死循环的情况,这是一个严重的BUG。这个问题在JDK 1.8中通过使用尾插法得到了解决。 2. **数据覆盖问题**:如前所述的例子所示...

Global site tag (gtag.js) - Google Analytics