I was recently asked in an interview to implement a thread safe implementation of Map class in java and assume that no thread safe library exists.

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

I wrapped the HashMap and just made the functions synchronized. Here is my implementation:

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

}

While adding synchronized allows thread safety, I really don't know how to prove if this is correct or not.

I tried writing the following unit test but couldn't really convince that my map is thread safe as I don't know if the get will happen first or put will happen first.

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

I saw the ConcurrentHashMap class' implementation and looks like they use Segments which are too complicated to tell in an interview.

Can someone suggest if my implementation is thread safe, and if yes how to have a test to prove it.

CodePudding user response：

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

Your implementation is NOT thread-safe:

1. The map variable is not declared as private final. That means that some other code could reach in and modify or even replace the wrapped Map. This is (at least!) not thread-safe. Arguably it is broken irrespective of thread-safety.

2. The get method accessed the map variable without synchronizing. That means that there is no happens before relationship between (say) one thread writing to the map (via put or delete) and a second thread reading from it. The lack of the happens before means that the writes are NOT guaranteed to (always) be visible to the reading thread. That is a thread-safety bug.

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

You cannot prove that code is thread-safe by testing it. You can only prove something is thread-safe by analyzing the code. Depending on how rigorous a proof you require, even that can be difficult.

A suitably written test could demonstrate that code is NOT thread-safe. Basically, you need something that shows that the visibility problem (see above) actually manifests as incorrect behavior. But the catch is that the 2nd flaw involves a behavior that arises from an absence of a guarantee. The read operation is not guaranteed to see the previous write, but it might see it anyway. This means that you could run the test on a broken implementation and observe that the test never fails on some platform. In short, the test not failing doesn't prove anything.

How do you write a test for the above behavior?

Well one thread needs to updates on the MyMap and a second thread needs to perform reads. And you need to design the test in such a way that the test will fail if the reader sees an incorrect get result. But designing such a test is difficult because the test itself can trigger (for example) memory cache flushes that obscure the underlying effect you are looking for. (For example, trace prints can do that.)

CodePudding user response：

Your test should make sure you are not able to add the same element twice, and you are not able to delete the same element twice. In each of the cases there should be an exception thrown in the second thread whichever it is. I don't see any reason to make get synchonous.