CODEWITHSUNDEEP
javamultithreadingconcurrenthashmap
Popeye
Popeye

Reputation: 1558

Concurrent hashmap simultaneous insertion

I have read that in concurrent hashmap in Java, simultaneous insertions are possible because it is divided into segments and separate lock is taken for each segment. But if two insertions are going to happen on same segment, then these simultaneous will not happen. My question is what will happen in such a case? Will second insertion waits till first one gets completed or what?

Upvotes: 1

Views: 675

Answers (5)

Rahman
Rahman

Reputation: 3785

ConcurrentHashMap contains array of Segment which in turn holds array of HashEntry. Each HashEntry holds a key, a value, and a pointer to it's next adjacent entry.

But it acquires the lock in segment level. Hence you are correct. i.e second insertion waits till first one gets completed

Upvotes: 1

Xirema
Xirema

Reputation: 20396

ConcurrentHashMap does not block when performing retrieval operations, and there is no locking for the usual operations.

The heuristic with most Concurrent Data Structures is that there's a backing data structure that gets modified first, with a front-facing data structure that's visible to outside methods. Then, when the modification is complete, the backing data structure is made the public data structure and the public data structure is pushed to the back. There's way more to it than that, but that's the typical contract.

Upvotes: 3

Mifeet
Mifeet

Reputation: 13608

In general you don't need be too concerned how ConcurrentHashMap is implemented. It simply complies to the the contract of ConcurrentMap which ensures that concurrent modifications are possible.

But to answer your question: yes, one insertion may wait for completion of the other one. Internally, it uses locks which ensure that one thread is waiting until the other one releases the lock. Class Segment used internally actually inherits from ReentrantLock. Here is a shortened version of Segmenet.put():

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
       // modifications
    } finally {
        unlock();
    }
    return oldValue;
}

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    // ...
    int retries = -1; // negative while locating node
    while (!tryLock()) {
        if (retries < 0) {
            // ...
        }
        else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        }
        else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {
            e = first = f; // re-traverse if entry changed
            retries = -1;
        }
    }
    return node;
}

This could give you an idea.

Upvotes: 3

Andrew Aitken
Andrew Aitken

Reputation: 681

If 2 updates try to happen on the same segment they will go into contention with each other and one of them will have to wait. You can optimise this by choosing a concurrencyLevel value which takes into account the number of threads which will be concurrently updating the hashmap.

You can find all the details in the javadoc for the class

Upvotes: 1

lance-java
lance-java

Reputation: 27984

Take a look at the javadoc for ConcurrentMap. It describes the extra methods available to deal with concurrent map mutations.

Upvotes: 0

Related Questions