JAVA并发下HashMap死循环与数据丢失问题的真实复现与修复策略

各位朋友，大家好！今天我们来聊聊Java并发编程中一个令人头疼的问题：HashMap在并发环境下的死循环和数据丢失。HashMap作为Java Collections框架中一个常用的数据结构，在单线程环境下表现出色，但在多线程环境下，由于其内部实现的特殊性，极易出现并发问题。本次讲座，我们将深入剖析这些问题的产生原因，并通过实际的代码案例来复现这些问题，并最终给出可行的修复策略。

一、 HashMap的内部实现简述

要理解HashMap的并发问题，首先需要对其内部实现有一个基本的了解。HashMap的核心数据结构是一个数组，数组中的每个元素被称为一个桶（bucket）。每个桶存储一个链表（或红黑树，在JDK 1.8之后）。当向HashMap中插入键值对时，首先会根据Key的hashCode计算出一个hash值，然后将hash值映射到数组的某个索引位置，也就是确定这个键值对应该放入哪个桶中。如果该桶中已经存在其他键值对，那么新的键值对就会以链表（或红黑树）的形式添加到该桶中。

核心属性：

table: Node<K,V>[]类型的数组，用于存储键值对。
size: HashMap中键值对的数量。
threshold: HashMap的扩容阈值，当size超过threshold时，HashMap会进行扩容。
loadFactor: 负载因子，用于计算threshold，threshold = capacity * loadFactor。

二、 HashMap并发问题的根源：非线程安全

HashMap本身不是线程安全的。这意味着多个线程同时对HashMap进行修改操作（例如put、remove）时，可能会导致数据不一致或死循环。这些问题的根源在于HashMap的resize操作以及put操作中的链表操作。

三、死循环问题的复现与分析

死循环问题主要出现在HashMap的resize操作中。当HashMap中的元素数量达到threshold时，会触发resize操作。resize操作会创建一个新的数组，并将原数组中的所有元素重新计算hash值并放入新数组中。在多线程环境下，如果多个线程同时进行resize操作，就可能导致链表成环，从而导致死循环。

3.1 代码复现

以下代码模拟了多线程环境下HashMap的死循环：

import java.util.HashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class HashMapDeadLoop {

    private static final int THREAD_COUNT = 2;
    private static final int MAP_SIZE = 10; // 初始容量小，更容易触发resize
    private static final float LOAD_FACTOR = 0.75f;

    public static void main(String[] args) throws InterruptedException {
        final HashMap<Integer, String> map = new HashMap<>(MAP_SIZE, LOAD_FACTOR);

        // 初始化HashMap，使其接近threshold
        for (int i = 0; i < MAP_SIZE * LOAD_FACTOR; i++) {
            map.put(i, "value" + i);
        }

        ExecutorService executor = Executors.newFixedThreadPool(THREAD_COUNT);

        for (int i = 0; i < THREAD_COUNT; i++) {
            final int threadId = i;
            executor.execute(() -> {
                for (int j = 0; j < 10000; j++) {
                    map.put(threadId * 10000 + j, "value" + (threadId * 10000 + j));
                }
            });
        }

        executor.shutdown();
        while (!executor.isTerminated()) {
            Thread.sleep(10);
        }

        System.out.println("Finished."); // 可能无法输出，因为死循环
    }
}

运行这段代码，很有可能导致程序卡死，CPU占用率飙升，因为HashMap进入了死循环。

3.2 原因分析

死循环的产生主要源于HashMap的transfer方法，该方法负责将旧数组中的元素迁移到新数组中。在多线程环境下，假设有两个线程A和B同时进行transfer操作，并且都处理同一个链表。

假设原始链表如下：

A -> B -> C

线程A和线程B同时获取到该链表，并开始进行transfer操作。

线程A首先处理A节点，将其放入新数组。
线程B也处理A节点，也将其放入新数组。
线程A处理B节点，将其插入到A节点之前，此时新链表为：B -> A
线程B处理B节点，也将其插入到A节点之前，此时新链表为：B -> A
线程A处理C节点，将其插入到B节点之前，此时新链表为：C -> B -> A
线程B处理C节点，也将其插入到B节点之前，此时新链表为：C -> B -> A

如果在某个时刻，线程A和线程B都完成了部分操作，并且各自的链表结构发生了变化，例如：

线程A的新链表：A -> B
线程B的新链表：B -> A

此时，如果线程A继续处理B节点，将其指向A节点，那么线程A的链表就变成了环状链表：A -> B -> A。当get操作访问到这个环状链表时，就会陷入死循环。

可以用表格来简化一下：

步骤	线程A 操作	线程B 操作	线程A 链表	线程B 链表
1	获取链表 A->B	获取链表 A->B	A->B	A->B
2	处理 A，放入新桶	处理 A，放入新桶	A	A
3	处理 B，B->A		B->A	A
4		处理 B，B->A	B->A	B->A
5	…	…	…	…

这个过程是高度并发的，并且依赖于线程的执行顺序，因此很难预测何时会发生死循环。

四、数据丢失问题的复现与分析

除了死循环，HashMap在并发环境下还可能出现数据丢失问题。数据丢失通常发生在put操作和resize操作并发执行时。

4.1 代码复现

以下代码模拟了多线程环境下HashMap的数据丢失：

import java.util.HashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class HashMapDataLoss {

    private static final int THREAD_COUNT = 10;
    private static final int MAP_SIZE = 10; // 初始容量小，更容易触发resize
    private static final float LOAD_FACTOR = 0.75f;

    public static void main(String[] args) throws InterruptedException {
        final HashMap<Integer, String> map = new HashMap<>(MAP_SIZE, LOAD_FACTOR);

        ExecutorService executor = Executors.newFixedThreadPool(THREAD_COUNT);

        for (int i = 0; i < THREAD_COUNT; i++) {
            final int threadId = i;
            executor.execute(() -> {
                for (int j = 0; j < 10000; j++) {
                    map.put(threadId * 10000 + j, "value" + (threadId * 10000 + j));
                }
            });
        }

        executor.shutdown();
        while (!executor.isTerminated()) {
            Thread.sleep(10);
        }

        System.out.println("Map size: " + map.size()); // 预期大小是 THREAD_COUNT * 10000，但实际可能小于这个值
    }
}

运行这段代码，最终HashMap的size很可能小于THREAD_COUNT * 10000，这意味着发生了数据丢失。

4.2 原因分析

数据丢失的原因在于put操作的非原子性。put操作包括以下几个步骤：

计算key的hash值。
根据hash值找到对应的桶。
遍历桶中的链表（或红黑树），查找key是否已经存在。
如果key存在，则更新value；如果key不存在，则将新的键值对添加到桶中。
如果添加后，HashMap的size超过了threshold，则进行resize操作。

在高并发环境下，多个线程可能同时执行put操作，并且都试图将新的键值对添加到同一个桶中。如果没有适当的同步措施，就可能导致一个线程的put操作被另一个线程覆盖，从而导致数据丢失。

假设线程A和线程B同时执行put操作，并且都将键值对添加到同一个桶中。

线程A计算出key的hash值，并找到对应的桶。
线程B也计算出key的hash值，并找到对应的桶（与线程A相同）。
线程A遍历桶中的链表，发现key不存在。
线程B遍历桶中的链表，发现key不存在。
线程A将新的键值对添加到桶中。
线程B也将新的键值对添加到桶中。

如果线程B在线程A完成put操作之前，就已经完成了步骤4，那么线程B就会覆盖线程A的put操作，导致线程A的数据丢失。

五、修复策略：线程安全的HashMap替代方案

解决HashMap的并发问题，最直接的方法是使用线程安全的HashMap替代方案。Java提供了以下几种线程安全的HashMap替代方案：

Collections.synchronizedMap(new HashMap<>()): 使用Collections工具类的synchronizedMap方法可以创建一个线程安全的HashMap。这种方法通过对HashMap的所有方法进行同步来实现线程安全。但是，这种方法的并发性能较低，因为所有操作都需要获取锁。
ConcurrentHashMap: ConcurrentHashMap是Java并发包java.util.concurrent中提供的一个线程安全的HashMap实现。它采用了分段锁（Segment Locking）的技术，将HashMap分成多个段（Segment），每个段拥有独立的锁。这样，多个线程可以同时访问不同的段，从而提高并发性能。ConcurrentHashMap是高并发场景下的首选方案。
Hashtable: Hashtable是Java早期版本中提供的一个线程安全的HashMap实现。与Collections.synchronizedMap类似，Hashtable也通过对所有方法进行同步来实现线程安全。但是，Hashtable的并发性能更低，因为它使用的是全局锁，这意味着同一时刻只能有一个线程访问Hashtable。因此，Hashtable在现代Java开发中已经很少使用。

5.1 Collections.synchronizedMap

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class SynchronizedMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = Collections.synchronizedMap(new HashMap<>());

        // 使用方式与HashMap相同，但所有操作都是线程安全的
        map.put("key1", 1);
        map.get("key1");
    }
}

优点：简单易用，只需要一行代码即可将HashMap转换为线程安全的Map。

缺点：并发性能较低，所有操作都需要获取锁，在高并发场景下容易成为性能瓶颈。

5.2 ConcurrentHashMap

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

        // 使用方式与HashMap类似，但所有操作都是线程安全的，并且并发性能更高
        map.put("key1", 1);
        map.get("key1");
    }
}

优点：并发性能高，采用分段锁技术，允许多个线程同时访问不同的段。

缺点：实现相对复杂，需要理解分段锁的原理。

5.3 使用ConcurrentHashMap修复数据丢失问题

将之前复现数据丢失问题的代码中的HashMap替换为ConcurrentHashMap，即可解决数据丢失问题。

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentHashMapDataLossFixed {

    private static final int THREAD_COUNT = 10;
    private static final int MAP_SIZE = 10;
    private static final float LOAD_FACTOR = 0.75f;

    public static void main(String[] args) throws InterruptedException {
        final ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>(MAP_SIZE, LOAD_FACTOR);

        ExecutorService executor = Executors.newFixedThreadPool(THREAD_COUNT);

        for (int i = 0; i < THREAD_COUNT; i++) {
            final int threadId = i;
            executor.execute(() -> {
                for (int j = 0; j < 10000; j++) {
                    map.put(threadId * 10000 + j, "value" + (threadId * 10000 + j));
                }
            });
        }

        executor.shutdown();
        while (!executor.isTerminated()) {
            Thread.sleep(10);
        }

        System.out.println("Map size: " + map.size()); // 预期大小是 THREAD_COUNT * 10000
    }
}

运行修改后的代码，最终ConcurrentHashMap的size将等于THREAD_COUNT * 10000，数据丢失问题得到解决。

六、总结：选择合适的并发容器，避免HashMap的坑

HashMap在并发环境下存在死循环和数据丢失的问题，这是由于其内部实现导致的非线程安全。解决这些问题的关键是使用线程安全的HashMap替代方案，例如Collections.synchronizedMap和ConcurrentHashMap。在选择替代方案时，需要根据具体的应用场景和并发量来权衡性能和复杂性。对于高并发场景，ConcurrentHashMap是首选方案。理解HashMap的并发问题以及选择合适的并发容器，可以避免在多线程环境下踩坑，保证程序的正确性和性能。

JAVA并发下HashMap死循环与数据丢失问题的真实复现与修复策略

发表回复 取消回复

发表回复取消回复