concurrenthashmap rehash

In ConcurrentHashMap table array is created for per-segment. And array of Segments created based on concurrencyLevel.

     * The per-segment table. Elements are accessed via
     * entryAt/setEntryAt providing volatile semantics.
    transient volatile HashEntry<K,V>[] table;

So REHASHING also will be done per segment’s table. So this wont affect the table of another segment.

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);

Question : Is this possible for 2 threads to update the ConcurrentHashMap at the same moment ?

Answer : Yes, its possible to have 2 parallel threads writing to the CHM at the same time, infact in the default implementation of CHM, atmost 16 threads can write & read in parallel. But in worst case if the two objects lie in the same segment, then parallel write would not be possible.

Question : Can multiple threads read from a given Hashtable concurrently ?

Answer : No, get() method of hash table is synchronized (even for synchronized HashMap). So only one thread can get value from it at any given point in time. Full concurrency for reads is possible only in ConcurrentHashMap via the use of volatile.

My other post about reentrant lock in Chinese

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s