Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does ConcurrentHashMap handle rehashing?

I am wondering how does ConcurrentHashMap handle rehashing while another thread is still writing on another segment/partition. As far as I understand that ConcurrentHashMap locks the segment independently, so for example, Thread1 writes to the segment1 slightly before Thread2 writes to segment2, and what happen if it requires the table to resize and rehash after Thread1 insertion, but Thread2 is in the middle of the writing operation ? does it lock the whole map for rehashing ? and does it have something like tell Thread2 to stop and wait until the rehash is done ? because Thread2 may have a chance end up writing segment1 after the table resize, correct ?

like image 685
peter Avatar asked Dec 05 '12 16:12

peter


People also ask

How does ConcurrentHashMap works internally?

In ConcurrentHashMap, at a time any number of threads can perform retrieval operation but for updated in the object, the thread must lock the particular segment in which the thread wants to operate. This type of locking mechanism is known as Segment locking or bucket locking.

How does ConcurrentHashMap achieve its scalability?

Unlike Hashtable which achieves its thread-safety by compromising the scalability, ConcurrentHashMap uses advanced techniques e.g. dividing the map into segments to remain thread-safe and scalable at the same time.

How does ConcurrentHashMap ensure thread-safety?

Concurrent. ConcurrentHashMap class achieves thread-safety by dividing the map into segments, the lock is required not for the entire object but for one segment, i.e one thread requires a lock of one segment. In ConcurrentHashap the read operation doesn't require any lock.

Can ConcurrentHashMap throws ConcurrentModificationException?

ConcurrentHashMap does not throw ConcurrentModificationException if the underlying collection is modified during an iteration is in progress. Iterators may not reflect the exact state of the collection if it is being modified concurrently. It may reflect the state when it was created and at some moment later.


1 Answers

Every segment is separately rehashed so there is no collision.

ConcurrentHashMap is array of specialized hash tables which are called Segments

From the source code

final Segment<K,V>[] segments;

/**
 * Segments are specialized versions of hash tables.  This
 * subclasses from ReentrantLock opportunistically, just to
 * simplify some locking and avoid separate construction.
 */

And if you check the method which returns Segment

final Segment<K,V> segmentFor(int hash) {
    return segments[(hash >>> segmentShift) & segmentMask];
}

So if you call put it first determines the Segment using segmentFor and then call put on that Segment

put source code

public V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key.hashCode());
    return segmentFor(hash).put(key, hash, value, false);
}
like image 109
Amit Deshpande Avatar answered Oct 15 '22 05:10

Amit Deshpande