Beyond Buckets: Unveiling the Segment-Based Architecture of ConcurrentHashMap

ConcurrentHashMap in Java offers a thread-safe alternative to the traditional HashMap. It excels in scenarios where multiple threads need to access and modify the map simultaneously. Here’s a breakdown of its internal workings:

Key Components:

• Segments: The ConcurrentHashMap is divided into an array of segments (default: 16). Each segment acts as a mini-HashMap and is responsible for managing its own key-value pairs.
• Synchronized Locking: Each segment has its own lock. This allows concurrent access to different segments by multiple threads without causing data corruption. Threads only need to acquire the lock for the specific segment they’re modifying.

class ConcurrentHashMap<K, V> {

    private Segment<K, V>[] segments; // Array of segments

    // ... other methods and constructors

    public V put(K key, V value) {
        int hash = key.hashCode();
        int segmentIndex = hash & (segments.length - 1); // Get segment index

        Segment<K, V> segment = segments[segmentIndex];
        synchronized (segment) { // Acquire segment lock
            // ... (logic similar to HashMap's put, but within the segment)
        }
        return value;
    }

    public V get(K key) {
        int hash = key.hashCode();
        int segmentIndex = hash & (segments.length - 1);

        Segment<K, V> segment = segments[segmentIndex];
        // No locking needed for reads (might change in Java 8+ with striped locking)
        // ... (logic similar to HashMap's get, but within the segment)
    }

    private static class Segment<K, V> {
        // ... (data structures for storing key-value pairs within the segment)
    }
}

private static class Segment<K, V> {

    private volatile Node<K, V>[] table; // Hash table within the segment
    private final int capacity; // Capacity of the segment's hash table
    private volatile int size; // Number of key-value pairs in the segment

    // ... other fields and methods

    public V put(K key, V value) {
        int hash = key.hashCode();
        int index = hash & (table.length - 1); // Get bucket index within the segment

        Node<K, V> newNode = new Node<>(key, value);
        synchronized (this) { // Acquire segment lock
            // ... (collision handling and insertion logic similar to HashMap)
        }
        return value;
    }

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash & (table.length - 1);

        // No locking needed for reads (might change in Java 8+ with striped locking)
        Node<K, V> current = table[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    private static class Node<K, V> {
        final K key;
        V value;
        volatile Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

ConcurrentHashMap’s Segment and Data Structures:

• Segment as Primary Unit: In ConcurrentHashMap, the Segment acts as the primary data structure for storing key-value pairs. This is a key difference from HashMap, where buckets are the primary level of organization within a single hash table.
• table Array: The private volatile Node<K, V>[] table; within Segment serves a similar purpose to a bucket array, but with some crucial distinctions. It’s essentially an internal hash table specific to that segment. Unlike a single bucket array in HashMap, each segment has its own independent table array for storing key-value pairs.
• Collision Handling: When multiple keys hash to the same index within the segment’s table (collision), ConcurrentHashMap employs techniques like linked lists or resizing the table itself to manage these collisions efficiently. This collision handling happens within the segment, not across separate buckets like in HashMap.