HashMap 中唯一键的线程安全

Question

关于这个话题有很多讨论，例如这里：

What's the difference between ConcurrentHashMap and Collections.synchronizedMap(Map)?

但我还没有找到我的具体用例的答案。

通常，您不能假设 HashMap 是线程安全的。如果同时从不同的线程写入同一个键，一切都会崩溃。但是，如果我知道我的所有线程都将具有唯一键怎么办？

这段代码是线程安全的还是需要添加阻塞机制（或者使用concurrent map）？

Map<int, String> myMap = new HashMap<>();
for (int i = 1 ; i > 6 ; i++) {
    new Thread(() -> {
        myMap.put(i, Integer.toString(i));
    }).start();
}

Answer 1

答案很简单：HashMap 完全没有线程安全保证。

事实上it's explicitly documented它不是线程安全的：

If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

因此在没有任何同步的情况下从多个线程访问一个是灾难的根源。

我已经看到每个线程使用不同的关键原因问题的情况（比如同时发生的迭代导致无限循环）。

想想重新散列：当达到阈值时，内部桶数组需要调整大小。这是一个有点冗长的操作（与单个 put 相比）。在那段时间里，如果另一个线程也尝试 put（甚至可能触发第二次重新散列！），就会发生各种奇怪的事情。

此外，您没有可靠的方法证明您的特定用例是安全的，因为您可以运行进行的所有测试都可能只是“意外地”起作用。换句话说：你永远不能依赖这个工作，即使你认为你已经用单元测试覆盖了它。

并且由于不是每个人都相信，您可以使用以下代码轻松地自行测试：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class HashMapDemonstration {

  public static void main(String[] args) throws InterruptedException {
    int threadCount = 10;
    int valuesPerThread = 1000;
    Map<Integer, Integer> map = new HashMap<>();
    List<Thread> threads = new ArrayList<>(threadCount);
    for (int i = 0; i < threadCount; i++) {
      Thread thread = new Thread(new MyUpdater(map, i*valuesPerThread, (i+1)*valuesPerThread - 1));
      thread.start();
      threads.add(thread);
    }
    for (Thread thread : threads) {
      thread.join();
    }
    System.out.printf("%d threads with %d values per thread with a %s produced %d entries, should be %d%n",
        threadCount, valuesPerThread, map.getClass().getName(), map.size(), threadCount * valuesPerThread);
  }
}

class MyUpdater implements Runnable {
  private final Map<Integer, Integer> map;
  private final int startValue;
  private final int endValue;

  MyUpdater(Map<Integer, Integer> map, int startValue, int endValue) {
    this.map = map;
    this.startValue = startValue;
    this.endValue = endValue;
    System.out.printf("Creating updater for values %d to %d%n", startValue, endValue);
  }

  @Override
  public void run() {
    for (int i = startValue; i<= endValue; i++) {
      map.put(i, i);
    }
  }
}

这正是 OP 提到的程序类型：每个线程只会写入其他线程从未接触过的键。而且，生成的 Map 不会包含所有条目：

Creating updater for values 0 to 999
Creating updater for values 1000 to 1999
Creating updater for values 2000 to 2999
Creating updater for values 3000 to 3999
Creating updater for values 4000 to 4999
Creating updater for values 5000 to 5999
Creating updater for values 6000 to 6999
Creating updater for values 7000 to 7999
Creating updater for values 8000 to 8999
Creating updater for values 9000 to 9999
10 threads with 1000 values per thread with a java.util.HashMap produced 9968 entries, should be 10000

请注意，每个运行最终 Map 中的实际条目数会有所不同。它甚至有时会打印 10000（因为它不是线程安全的！）。

请注意，这种故障模式（丢失条目）绝对不是唯一可能的模式：基本上 任何事情 都可能发生。

Answer 2

我想专门回复一下这句话。

But what if I know that all my threads will have unique keys?

您正在对地图的实现做出假设。实施可能会发生变化。如果实现是 documented not to be thread-safe, you must take into account the Java Memory Model (JMM)，那么几乎不能保证线程之间内存的可见性。

这是在做很多假设而很少保证。你不应该依赖这些假设，即使它恰好在你的机器上，在特定的用例中，在特定的时间工作。

简而言之：如果在多线程中使用非线程安全的实现，则必须用确保线程安全的结构包围它。总是。

但是，为了好玩，让我们描述一下在您的特定情况下可能出现的问题，其中每个线程只使用一个唯一的键。

添加或删除键时，即使是唯一键，也有哈希映射需要在内部重组的情况。第一个是在哈希冲突的情况下，¹，其中必须更新键值条目的链接列表。第二个是地图决定调整其内部条目 table 大小的地方。这彻底检查了内部结构，包括提到的链表。

由于 JMM，在很大程度上不能保证另一个线程看到重组的内容。这意味着如果在重组发生时另一个线程恰好位于 get(key) 的中间，则行为是未定义的。如果另一个线程同时执行 put(key,value)，您最终可能会遇到两个线程同时尝试调整地图大小的情况。坦率地说，我什至不想去想会造成什么混乱！

¹ 多个键可以有相同的散列码。因为映射没有无限存储，哈希码通常也用内部条目的大小 table 包裹，比如 (hashCode % sizeOfTable)，这可能导致不同哈希码利用的情况相同的“条目”。

HashMap 中唯一键的线程安全

Thread-safety of unique keys in a HashMap

java

multithreading

concurrency

hashmap

thread-safety