如何测试和证明我的自定义地图是线程安全的

Question

我最近在一次采访中被要求在 java 中实现 Map class 的线程安全实现，并假设不存在线程安全库。

interface Map{
        void put(String key, String value);
        String get(String key);
        String delete(string key);
 }

我包装了 HashMap 并使函数同步。这是我的实现：

class MyMap{

     Map<String, String> map;

     public MyMap(){
           map = new HashMap<>();
     }

     public synchronized void put(String key, String value){
           map.put(key, value);
     }

     public String get(String key){
           return map.get(key);
     }

    public synchronized String delete(String key){
           return map.remove(key);
     }

}

虽然添加synchronized允许线程安全，但我真的不知道如何证明这是否正确。

我尝试编写以下单元测试，但无法真正确信我的映射是线程安全的，因为我不知道是先获取还是先放置。

Thread t1 = new Thread(()->{ map.put("testKey1", "testValue1") });
Thread t2 = new Thread(()->{ map.put("testKey2", "testValue2") });

t1.start();
t2.start();

Thread t3 = new Thread(()->{ System.out.println(map.get("testKey1")) });
Thread t4 = new Thread(()->{ System.out.println(map.get("testKey2")) });

t3.start();
t4.start();

我看到了 ConcurrentHashMap class' 的实现，看起来他们使用的 Segments 太复杂了，无法在面试中讲述。

有人可以建议我的实现是否是线程安全的，如果是，如何进行测试来证明它。

Answer 1

Can someone suggest if my implementation is thread safe ...

您的实施不是 thread-safe:

map 变量未声明为 private final。这意味着一些其他代码可以进入并修改甚至替换包装的 Map。这（至少！）不是 thread-safe。可以说它被打破了 irrespective of thread-safety.
get 方法在不同步的情况下访问 map 变量。这意味着在（比如说）写入 map（通过 put 或 delete）的一个线程与第二个线程之间没有 发生在 之前的关系线程从中读取。在之前缺少 意味着写入不能保证（总是）对读取线程可见。这是一个 thread-safety 错误。

后一个 thread-safety 错误可能表现为 get() 请求：

获取过时值，或

没有得到应该存在的键的值，或者

获取已删除键的值，或

意外异常，或

无限循环(!)。

使用您的 MyMap class 的应用程序可能在某些平台上运行，但在其他平台上无法运行。它可能会反复失败，或者很少以在测试环境中几乎不可能重现的方式失败。

.... and if yes how to have a test to prove it.

您无法通过测试来证明代码是 thread-safe。您只能通过分析代码来证明某些东西是 thread-safe。根据您需要的证据的严格程度，即使那样也可能很困难。

适当编写的测试可以证明代码不是 thread-safe。基本上，您需要一些东西来表明可见性问题（见上文）实际上表现为不正确的行为。但要注意的是，第二个缺陷涉及由于缺乏保证而产生的行为。读取操作不保证看到之前的写入，但无论如何它都可能看到。这意味着您可以运行在损坏的实现上进行测试，并观察到该测试在某些平台上永远不会失败。简而言之，没有失败的测试并没有证明任何东西。

如何为上述行为编写测试？

好吧，一个线程需要更新 MyMap，另一个线程需要执行读取。并且您需要以这样的方式设计测试，如果 reader 看到不正确的 get 结果，测试将失败。但是设计这样的测试很困难，因为测试本身会触发（例如）内存缓存刷新，从而掩盖您正在寻找的潜在效果。（例如，痕迹打印可以做到这一点。）

Answer 2

您的测试应该确保您不能两次添加相同的元素，并且您不能两次删除相同的元素。在每种情况下，第二个线程都应该抛出一个异常。我看不出有任何理由让 get 同步。

如何测试和证明我的自定义地图是线程安全的

How to Test & Prove my custom Map is thread safe

java

multithreading

hashmap

thread-safety

concurrenthashmap