CODEWITHSUNDEEP
javamultithreadinghashmapsynchronized
user3105690
user3105690

Reputation: 11

HashMap synchronization

I have a task to synchronize method put(K key, V value) of HashMap. But It should work faster then synchronized(this) or synchronized(table). I wrote this code:

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

    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))) {
            synchronized(e) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

The problem is that when I call this method by different Threads using the same key, there can be situation, that map.entrySet().size() > 1. So my synchronization is wrong, but I don't understand why. How can I do this properly?

Upvotes: 1

Views: 970

Answers (3)

Diversity
Diversity

Reputation: 1900

Because your e can change before it enters the synchroniezed block, The complete table can change before and during the iteration of the synchronized block.

The problem is to lock the table entries. So maybe its better to declare the complete method as synchronized.

Work with semaphores (See Java concurrency API) to ensure atomic access to your table.

Update due to comment:

Provide a cache mechanism for your application. Introduce an additional list(queue, cache) which gathers all incoming changes to your tables or map while they are blocked. So your application can still proceed. Until the table is not blocked any more you add the cache entries to you table.

An answer but just a suggestion.

Upvotes: 1

Gray
Gray

Reputation: 116918

The problem is that when I call this method by different Threads using the same key, there can be situation, that map.entrySet().size() > 1. So my synchronization is wrong, but I don't understand why.

I'm not 100% sure I understand the error case, but I see a number of problems with your attempt at synchronization that will cause race conditions.

For example, if two threads try to add the same key to the HashMap at the same time, they are going to loop through the bucket and not find the entry. Then both of them are going to try to add the entry to the table. This could result in two entries with the same key or even corruption of the table.

I'm also assuming that addEntry(...) could change the bucket array which could cause rehashing of all of the elements. So one thread could cause the buckets to change while another thread is working with an out-of-date array. This could cause entries to be lost or again table corruption.

How can I do this properly?

This is a non-trivial exercise. One thing you could do is use a ReadWriteLock so at least you can have lookups not block the writing. But if you are writing a new entry into the map, you may have to have an exclusive lock on it because of the changes to the bucket array mentioned above.

Upvotes: 3

Paul Draper
Paul Draper

Reputation: 83393

One problem that your for loop is iterating over a potentially changing collection.

I would really recommend ConcurrentHashMap, or making the entire method (or most of it) synchronized.

Upvotes: 0

Related Questions