Java - Concurrent HashMap

Internal Structure

final Segment<K,V> [] segments;

class HashEntry<K,V> {
    final K key;
    volatile V
    final int hashCode;
    final HashEntry<K,V> next;
}

class Segment<K,V> extends ReentrantLock<K> implements Serializable {

    transient volatile int count;// no of elements in this segment
    transient int modCount;
    transient int threshold; = loadFactor * table.length
    final float loadFactor;
    transient volatile ConcurrentHashMap.HashEntry<K, V>[] table; 

}

• Following operations lock - put(), replace(), 
• Following operations lock if fails first time - containsValue() | get()
• The lock is on the Segment (which extends ReentrantLock)
• concurrencyLevel decides the number of segments the CHM will create.

Constructor - Default

initialCapacity = 16
loadFactor = 0.75
concurrencyLevel = 16

1. decide size of Segment[] by left shifting 1 (<<) till its greater than concurrencyLevel. So for ccy level of 16 we have Segment[32] .
2. if initialCapacity > MAX_CAPACITY then initialCapacity = MAX_CAPACITY
3. Find size of HashEntry[] in each Segment, c = initialCapacity / segmentSize
4. Calculate capacity by left shifting 1 (<<) till its greater than c.
5. Create all Segment[] elements using the above capacity and loadFactor.

public V put( K,V )

1. calculate index using K.hashCode()
2. Find Segment index using the hashCode
3. obtain the Segment lock() [ Segment extends ReentrantLock ]
4. rehash() if required ( count++ > threshold )
5. Traverse the list at Segment[i] till we find matching key or reach the end.
6. if we reach end - add the new HashEntry to the front of List
7. else replace the existing Value.
8. Return existing Value OR null if the Mapping was not present before. 
9. unlock() the Segment's lock

public get( K ) - not synchronised

1. Find the Segment index using hashCode. 
2. Check count > 0 // volatile read
3. Traverse the list at Segment[i] by comparing hashCode && key.equals( searchKey ).
4. If key not found do a synchronised lookup lock() and then unlock() in finally
5. return the associated value or null if not found.

containsValue( V )

1. Tries non-locking search ( 2 times ) first otherwise locks all segments and search again (same algorithm as below )
2. Iterates each Segment and calls Segment.containsValue( V )
3. Iterates each element in table[] and its contained list in-turn to check for Value
4. If Value is null for an entry (could be under addition). lock() the segment (synchronise) and retry to get the value and unlock().

replace( K, V )

1. Find the Segment
2. lock() the segment
3. Find the HashEntry using the Key & its hashCode
4. Replace with new Value and return oldValue
5. return null of Key not found.

replace( K, V old, V new)

1. Replaces only if current mapping has value=old
2. Find the Segment using hashCode of key.
3. lock() the segment
4. Find the HashEntry from the table array using the Key & its hashCode()
5. Traverse the HashEntry list till we find HashEntry with a key that satisfies equals() method.
6. Compare existing Value in the HashEntry with new Value
7. if equal - replace HashEntry.value = new
8. return null of Key not found.

keySet() - Returns Set backed by the Map

iteration() - While iterating following state is maintained

1. nextTableIndex, nextSegmentIndex are maintained
2. nextEntry is kept in Current State
3. hasNext() -> if nextEntry = null

public V putIfAbsent( K, V )

1. If value == null throw NPE.
2. Calculate/Get hashCode and get the corresponding segment.
3. Call Segment.put() ( which executes lock() ) with putIfAbsent = true.
4. Return the value returned by put()

ConcurrentSkipListMap 

1. A scalable concurrent ConcurrentNavigableMap implementation. 
2. Cross between ConcurrentMap & Treemap
3. Sorted in natural order
4. log(n) time cost for the containsKey, get, put and remove 
5. it provides more scalable concurrency even over ConcurrentHashMap
6. Uses CAS on Key & Value to achieve higher concurrency.
7. this concurrency is paid for with non-constant access times.

ConcurrentLinkedQueue