CODEWITHSUNDEEP
javamultithreading
WelcomeTo
WelcomeTo

Reputation: 20571

How to make thread-safe HashMap without locking `get()` method?

I asked on interview a question: how to implement getter and setter for exclusive writing to HashMap and non-exclusive reading. Suppose following code:

public class MyClass {

     private HashMap map = new HashMap();


      // HOW TO implement Getter and Setter for exclusive writing and non-exclusive reading
}

Upvotes: 6

Views: 7766

Answers (2)

assylias
assylias

Reputation: 328598

ConcurrentHashMap uses a lock striping strategy: it has (with default settings) 16 locks, each guarding 1/16th of the hashmap buckets.

Simply using volatile would not really help as some operations need to be atomic and volatile only gives visibility guarantees.

An alternative is to completely synchronize the map (like in Collections.synchronizedMap or Hashtable), but the performance of such a strategy under high contention is significantly worse - it might be good enough depending on your use case.

An alternative to Evgeniy's proposal is a sort of "copyonwritemap" - it will not be as efficient in most scenarios:

class MyClass<K, V> {
    //note: map needs to be volatile to completely remove synchronization
    //at the getter level
    private volatile Map<K, V> map = new HashMap<K, V>();
    private final Object lock = new Object();

    public V get(Object k) {
        return map.get(k);
    }

    public V put(K k, V v) {
        synchronized (lock) { //for exclusive writing
            Map<K, V> newMap = new HashMap<K, V> (map); //copy map
            V value = newMap.put(k, v);
            //volatile guarantees that this will be visible from the getter
            map = newMap;
            return value;
        }
    }
}

Upvotes: 8

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 135992

try this

class MyClass<K, V> {
    private HashMap<K, V> map = new HashMap<K, V>();
    private ReadWriteLock rwl = new ReentrantReadWriteLock();
    private Lock rl = rwl.readLock();
    private Lock wl = rwl.writeLock();

    public V get(Object k) {
        rl.lock();
        try {
            return map.get(k);
        } finally {
            rl.unlock();
        }
    }

    public V put(K k, V v) {
        wl.lock();
        try {
            return map.put(k, v);
        } finally {
            wl.unlock();
        }
    }
}

Upvotes: 14

Related Questions