如何证明java中的HashMap不是线程安全的

Question

我正在开发应用程序,它将HashMap作为共享状态.我需要通过单元测试证明它在多线程环境中会有问题.

我尝试通过检查这两个HashMap的大小和元素来检查sinlge线程环境和多线程环境中的应用程序状态.但似乎这没有帮助,状态总是一样的.

有没有其他方法来证明它或证明在地图上执行操作的应用程序适用于并发请求？

Answer 1

这很容易证明。

从思想上

哈希映射基于数组，其中每个项目代表一个存储桶。随着添加更多密钥，存储桶将增长，并在某个阈值处以更大的大小重新创建阵列，其存储桶将重新排列，以便它们更均匀地分布（出于性能考虑）。

技术上

这意味着有时HashMap#put()会在内部调用HashMap#resize()以使基础数组变大。

HashMap#resize()为该table字段分配一个具有更大容量的新空数组，并用旧项目填充它。发生这种填充时，基础数组不会包含所有旧项，并且HashMap#get()可能会返回带有现有键的调用null。

以下代码演示了这一点。您很可能会得到异常，这意味着HashMap线程不是安全的。我选择了目标键65 535-这种方式将是在数组中的最后一个元素，因此被重新人群增加获得的可能性期间的最后一个元素null上HashMap#get()（知道为什么，看到HashMap#put()实现）。

final Map<Integer, String> map = new HashMap<>();

final Integer targetKey = 0b1111_1111_1111_1111; // 65 535
final String targetValue = "v";
map.put(targetKey, targetValue);

new Thread(() -> {
    IntStream.range(0, targetKey).forEach(key -> map.put(key, "someValue"));
}).start();


while (true) {
    if (!targetValue.equals(map.get(targetKey))) {
        throw new RuntimeException("HashMap is not thread safe.");
    }
}

一个线程将新键添加到地图。另一个线程不断检查targetKey是否存在。

如果算上这些例外，我避开200 000。

Answer 2

很难模拟Race但是查看OpenJDK源代码put()的HashMap方法:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);

    //Operation 1       
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    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;
        }
    } 

    //Operation 2
    modCount++;

    //Operation 3
    addEntry(hash, key, value, i);
    return null;
}

如您所见,put()涉及3个未同步的操作.复合操作是非线程安全的.因此理论上证明它HashMap不是线程安全的.

Answer 3

阅读 API 文档就足够了吗？里面有一句话：

请注意，此实现不是同步的。如果多个线程同时访问哈希图，并且至少有一个线程在结构上修改了该图，则必须进行外部同步。（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）这通常是通过在自然封装映射的某个对象上进行同步来完成的。如果不存在这样的对象，则应使用 Collections.synchronizedMap 方法“包装”映射。最好在创建时完成此操作，以防止意外地不同步访问地图：

线程安全的问题在于很难通过测试来证明。大多数时候都可以。你最好的选择是只运行一堆正在获取/放入的线程，你可能会遇到一些并发错误。

我建议使用 aConcurrentHashMap并相信 Java 团队所说的HashMap不同步就足够了。

Answer 4

还有其他方法可以证明吗？

阅读文档怎么样（并注意强调的“必须”）：

如果多个线程同时访问一个哈希图，并且至少有一个线程在结构上修改了该图，则必须进行外部同步

如果您打算尝试编写一个演示不正确行为的单元测试，我建议您执行以下操作：

• 创建一堆具有相同哈希码的键（例如 30 或 40）
• 为每个键向映射添加值
• 为该键生成一个单独的线程，该线程有一个无限循环，(1) 断言该键存在于映射中，(2) 删除该键的映射，(3) 将映射添加回来。

如果幸运的话，断言将在某个时刻失败，因为哈希桶后面的链表将被损坏。HashMap如果你不幸的话，尽管有文档，它看起来确实是线程安全的。

Answer 5

我需要通过单元测试证明它在多线程环境中会有问题.

这将是非常困难的.种族条件很难证明.您当然可以编写一个程序,它可以在大量线程中放入并进入HashMap,但是应用程序的日志记录,volatile字段,其他锁定和其他时间详细信息可能会使您的特定代码失败变得非常困难.

这是一个愚蠢的小HashMap失败测试案例.它失败是因为当线程由于内存损坏而进入无限循环时超时HashMap.但是,根据内核数量和其他体系结构详细信息,它可能不会失败.

@Test(timeout = 10000)
public void runTest() throws Exception {
    final Map<Integer, String> map = new HashMap<Integer, String>();
    ExecutorService pool = Executors.newFixedThreadPool(10);
    for (int i = 0; i < 10; i++) {
        pool.submit(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    map.put(i, "wow");
                }
            }
        });
    }
    pool.shutdown();
    pool.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);
}

Answer 6

它是一个旧线程。但是只需粘贴我的示例代码即可证明hashmap的问题。

看一下下面的代码，我们尝试使用10个线程（每个线程3000个项目）将30000个项目插入到哈希图中。

因此，在所有线程完成之后，理想情况下，您应该看到hashmap的大小应为30000。但是，实际的输出将是重建树时的异常，或者最终计数小于30000。

class TempValue {
    int value = 3;

    @Override
    public int hashCode() {
        return 1; // All objects of this class will have same hashcode.
    }
}

public class TestClass {
    public static void main(String args[]) {
        Map<TempValue, TempValue> myMap = new HashMap<>();
        List<Thread> listOfThreads = new ArrayList<>();

        // Create 10 Threads
        for (int i = 0; i < 10; i++) {
            Thread thread = new Thread(() -> {

                // Let Each thread insert 3000 Items
                for (int j = 0; j < 3000; j++) {
                    TempValue key = new TempValue();
                    myMap.put(key, key);
                }

            });
            thread.start();
            listOfThreads.add(thread);
        }

        for (Thread thread : listOfThreads) {
            thread.join();
        }
        System.out.println("Count should be 30000, actual is : " + myMap.size());
    }
}

输出1：

Count should be 30000, actual is : 29486

输出2 ：（异常）

java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNodejava.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
    at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1819)
    at java.util.HashMap$TreeNode.treeify(HashMap.java:1936)
    at java.util.HashMap.treeifyBin(HashMap.java:771)
    at java.util.HashMap.putVal(HashMap.java:643)
    at java.util.HashMap.put(HashMap.java:611)
    at TestClass.lambda$0(TestClass.java:340)
    at java.lang.Thread.run(Thread.java:745)

但是，如果将行修改Map<TempValue, TempValue> myMap = new HashMap<>();为ConcurrentHashMap，则输出始终为30000。

另一个观察结果：在上面的示例中，所有TempValue类对象的哈希码都相同（**，即1 **）。因此，您可能想知道，仅当发生冲突时（由于哈希码），才会发生HashMap的此问题。我尝试了另一个例子。

修改TempValue类为

class TempValue {
    int value = 3;
}

现在重新执行相同的代码。
在每5次运行中，我看到2-3次运行仍提供与30000不同的输出。
因此，即使通常不会发生太多碰撞，您也可能最终会遇到问题。（可能是由于重建了HashMap等）

总体而言，这些示例说明了ConcurrentHashMap处理的HashMap问题。