Understanding Java ConcurrentHashMap: Segmented Locks, Immutability, and Performance

Background

Thread‑unsafe HashMap

In a multithreaded environment, using HashMap for put operations can cause an infinite loop and CPU usage near 100%, so HashMap must not be used concurrently.

Inefficient Hashtable

Hashtable achieves thread safety with synchronized methods, but under heavy contention the lock becomes a bottleneck; only one thread can access put or get at a time, drastically reducing throughput.

Segmented‑Lock Technique

ConcurrentHashMap solves the bottleneck by partitioning the map into multiple segments, each protected by its own lock. Threads accessing different segments do not contend for the same lock, improving concurrency. Some operations that span segments (e.g., size() and containsValue()) acquire all segment locks in a fixed order to avoid deadlock.

ConcurrentHashMap consists of a Segment array and a HashEntry array. Each Segment is a ReentrantLock that guards its own hash table; each HashEntry stores a key‑value pair.

Application Scenarios

When a large array must be shared among many threads, partitioning it into multiple nodes (segments) avoids a single global lock. The same principle applies to database tables: large tables can be split horizontally (sharding) to reduce contention.

Source Code Analysis

The main classes in JDK 1.7 ConcurrentHashMap are ConcurrentHashMap, Segment, and HashEntry:

/**
 * The segments, each of which is a specialized hash table
 */
final Segment<K,V>[] segments;

Immutable and Volatile

ConcurrentHashMap allows multiple readers without locking. To keep reads consistent, HashEntry objects are almost immutable; only the value field is volatile. The class definition is:

static final class HashEntry<K,V> {
    final K key;
    final int hash;
    volatile V value;
    final HashEntry<K,V> next;
}

Because all fields except value are final, nodes cannot be inserted or removed in the middle of a chain; new nodes are always added at the head, and removal requires cloning preceding nodes.

Positioning Operation

Elements are placed into a segment using a re‑hashed value. The segment is selected by:

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

The re‑hash spreads bits across the hash value, reducing collisions. With the default 16 segments, the high 4 bits of the hash determine the segment.

Data Structure

All fields in Segment are final except the volatile counters. Important members include:

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile int count;          // number of elements
    transient int modCount;               // structural modifications
    transient int threshold;              // rehash threshold
    transient volatile HashEntry<K,V>[] table; // bucket array
    final float loadFactor;
}

remove(key)

public V remove(Object key) {
    int hash = hash(key.hashCode());
    return segmentFor(hash).remove(key, hash, null);
}

The method first locates the appropriate segment, then removes the entry while holding the segment lock. If the entry exists, preceding nodes are cloned because their next reference is final.

get(key)

V get(Object key, int hash) {
    if (count != 0) {
        HashEntry<K,V> e = getFirst(hash);
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) {
                V v = e.value;
                if (v != null) return v;
                return readValueUnderLock(e);
            }
            e = e.next;
        }
    }
    return null;
}

Reads are lock‑free because count and value are volatile. If a read sees a null value, the method re‑checks under lock to handle possible reordering.

put(key, value)

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
        int c = count;
        if (c++ > threshold) rehash();
        HashEntry<K,V>[] tab = table;
        int index = hash & (tab.length - 1);
        HashEntry<K,V> first = tab[index];
        HashEntry<K,V> e = first;
        while (e != null && (e.hash != hash || !key.equals(e.key)))
            e = e.next;
        V oldValue;
        if (e != null) {
            oldValue = e.value;
            if (!onlyIfAbsent) e.value = value;
        } else {
            oldValue = null;
            ++modCount;
            tab[index] = new HashEntry<K,V>(key, hash, first, value);
            count = c;
        }
        return oldValue;
    } finally {
        unlock();
    }
}

The method acquires the segment lock, checks capacity, and either updates an existing entry or inserts a new one at the head of the bucket chain.

containsKey(key)

boolean containsKey(Object key, int hash) {
    if (count != 0) {
        HashEntry<K,V> e = getFirst(hash);
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) return true;
            e = e.next;
        }
    }
    return false;
}

size()

To compute the total size, ConcurrentHashMap first attempts an unsynchronized sum of all segment count values. If the modCount changes during the scan, it retries with all segments locked to guarantee a consistent result.

Source: Blog园 https://www.cnblogs.com/ITtangtang/p/3948786.html