How to Test & Prove my custom Map is thread safe

Question

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.

Answer 1

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.