6.16 ConcurrentHashMap in JDK 1.7

1. Constructor

public ConcurrentHashMap() {
    // 16, 0.75f, 16
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

2. The put Method

public V put(K key, V value) {
    Segment<K,V> s;
    // value cannot be null
    if (value == null)
        throw new NullPointerException();
    // Calculate the hash value of the key
    int hash = hash(key);
    // Then use the hash value to calculate j
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         // Use j to calculate the address and obtain the Segment object with CAS
         (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
        // Initialize
        s = ensureSegment(j);
    // Call Segment.put
    return s.put(key, hash, value, false);
}

2.1. hash

private int hash(Object k) {
    int h = hashSeed;

    if ((0 != h) && (k instanceof String)) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

2.2. ensureSegment

private Segment<K,V> ensureSegment(int k) {
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // raw offset
    Segment<K,V> seg;
    // The Segment is null and needs to be initialized.
    // Why use CAS instead of directly using the array index???
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        // Prototype pattern: use the first Segment as the prototype
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        // Get the capacity, loadFactor, and threshold of the first Segment
        // (used later to create the entry table and Segment)
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);

        // Create the entry table (used later to create the Segment)
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        // Recheck that it is still null. If it is not null, another thread has already initialized it,
        // so exit directly to avoid wasting CPU in an infinite loop + CAS
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
            == null) { // recheck
            // Create the Segment
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // Infinite loop + CAS to set the Segment
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    return seg;
}

2.3. The Segment.put Method

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
        // First call sync.nonfairTryAcquire(1) to try to acquire the lock quickly
        HashEntry<K,V> node = tryLock() ? null :
            scanAndLockForPut(key, hash, value);
        V oldValue;
        try {
            // Calculate the index
            HashEntry<K,V>[] tab = table;
            int index = (tab.length - 1) & hash;
            // Head node
            HashEntry<K,V> first = entryAt(tab, index);
            // Traverse the linked list
            for (HashEntry<K,V> e = first;;) {
                // The linked list is not empty
                if (e != null) {
                    K k;
                    // Found an equal node
                    if ((k = e.key) == key ||
                        (e.hash == hash && key.equals(k))) {
                        oldValue = e.value;
                        // Replace value
                        if (!onlyIfAbsent) {
                            e.value = value;
                            ++modCount;
                        }
                        break;
                    }
                    e = e.next;
                }
                // The linked list is empty
                else
                {
                    // The node was already found above
                    if (node != null)
                        node.setNext(first);
                    else
                        node = new HashEntry<K,V>(hash, key, value, first);
                    // Increment the count
                    int c = count + 1;
                    // The count now exceeds threshold
                    if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                        // Resize
                        rehash(node);
                    else
                        // CAS-set the head node
                        setEntryAt(tab, index, node);
                    ++modCount;
                    count = c;
                    oldValue = null;
                    break;
                }
            }
        } finally {
            // Unlock
            unlock();
        }
        return oldValue;
    }

2.3.1. scanAndLockForPut

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
        HashEntry<K,V> first = entryForHash(this, hash);
        HashEntry<K,V> e = first;
        HashEntry<K,V> node = null;
        int retries = -1; // negative while locating node
        // Infinite loop until the lock is acquired
        while (!tryLock()) {
            HashEntry<K,V> f; // to recheck first below
            if (retries < 0) {
                // The linked-list head is null
                if (e == null) {
                    if (node == null) // speculatively create node
                        node = new HashEntry<K,V>(hash, key, value, null);
                    retries = 0;
                }
                // Found an equal node
                else if (key.equals(e.key))
                    retries = 0;
                // Next node in the linked list
                else
                    e = e.next;
            }
            // Too many loops: upgrade to blocking lock acquisition
            else if (++retries > MAX_SCAN_RETRIES) {
                lock();
                break;
            }
            else if ((retries & 1) == 0 &&
                     (f = entryForHash(this, hash)) != first) {
                e = first = f; // re-traverse if entry changed
                retries = -1;
            }
        }
        return node;
    }

2.3.2. rehash

private void rehash(HashEntry<K,V> node) {
        /*
         * Reclassify nodes in each list to new table.  Because we
         * are using power-of-two expansion, the elements from
         * each bin must either stay at same index, or move with a
         * power of two offset. We eliminate unnecessary node
         * creation by catching cases where old nodes can be
         * reused because their next fields won't change.
         * Statistically, at the default threshold, only about
         * one-sixth of them need cloning when a table
         * doubles. The nodes they replace will be garbage
         * collectable as soon as they are no longer referenced by
         * any reader thread that may be in the midst of
         * concurrently traversing table. Entry accesses use plain
         * array indexing because they are followed by volatile
         * table write.
         */
        HashEntry<K,V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        // New capacity = old capacity * 2
        int newCapacity = oldCapacity << 1;
        threshold = (int)(newCapacity * loadFactor);
        // Create a new entry array using the new capacity
        HashEntry<K,V>[] newTable =
            (HashEntry<K,V>[]) new HashEntry[newCapacity];
        int sizeMask = newCapacity - 1;
        // Traverse every element in the original array
        for (int i = 0; i < oldCapacity ; i++) {
            HashEntry<K,V> e = oldTable[i];
            if (e != null) {
                HashEntry<K,V> next = e.next;
                // Calculate its position in the new array
                int idx = e.hash & sizeMask;
                // Only one node
                if (next == null)   // Single node on list
                    newTable[idx] = e;
                else { // Reuse consecutive sequence at same slot
                    HashEntry<K,V> lastRun = e;
                    int lastIdx = idx;
                    // Traverse the linked list
                    for (HashEntry<K,V> last = next;
                         last != null;
                         last = last.next) {
                        int k = last.hash & sizeMask;
                        if (k != lastIdx) {
                            lastIdx = k;
                            lastRun = last;
                        }
                    }
                    newTable[lastIdx] = lastRun;
                    // Clone remaining nodes
                    for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                        V v = p.value;
                        int h = p.hash;
                        int k = h & sizeMask;
                        HashEntry<K,V> n = newTable[k];
                        newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                    }
                }
            }
        }
        int nodeIndex = node.hash & sizeMask; // add the new node
        node.setNext(newTable[nodeIndex]);
        newTable[nodeIndex] = node;
        table = newTable;
    }

3. get

public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    // Calculate the Segment address from the key
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // Obtain the Segment through CAS
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        // Obtain the entry through CAS
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            K k;
            // Traverse the linked list to find an equal node
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

4. The containsKey Method

public boolean containsKey(Object key) {
    Segment<K,V> s; // same as get() except no need for volatile value read
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // Obtain the corresponding Segment through CAS
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        // Obtain the corresponding entry through CAS and traverse the linked list
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            K k;
            // Found an equal node
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return true;
        }
    }
    return false;
}

5. remove

public V remove(Object key) {
    int hash = hash(key);
    // Find the Segment first
    Segment<K,V> s = segmentForHash(hash);
    return s == null ? null : s.remove(key, hash, null);
}

5.1. segmentForHash

private Segment<K,V> segmentForHash(int h) {
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // Obtain it through CAS
    return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
}

5.2. Segment.remove

final V remove(Object key, int hash, Object value) {
        // Try to acquire the lock; on failure, use an infinite loop + CAS to acquire it
        if (!tryLock())
            scanAndLock(key, hash);
        V oldValue = null;
        try {
            HashEntry<K,V>[] tab = table;
            int index = (tab.length - 1) & hash;
            HashEntry<K,V> e = enUNSAFE.putOrderedObject(this, nextOffset, n);tryAt(tab, index);
            HashEntry<K,V> pred = null;
            // Traverse the linked list
            while (e != null) {
                K k;
                HashEntry<K,V> next = e.next;
                // Found an equal node
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    V v = e.value;
                    if (value == null || value == v || value.equals(v)) {
                        if (pred == null)
                        // UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
                            setEntryAt(tab, index, next);
                        else
                        // UNSAFE.putOrderedObject(this, nextOffset, n);

                            pred.setNext(next);
                        ++modCount;
                        --count;
                        oldValue = v;
                    }
                    break;
                }
                pred = e;
                e = next;
            }
        } finally {
            // Unlock
            unlock();
        }
        return oldValue;
    }

Summary

In JDK 1.7, segmented locking is used to implement concurrent update operations. The underlying storage structure is array + linked list, with two core static inner classes: Segment and HashEntry.

• Segment extends ReentrantLock and acts as the lock. Each Segment object guards several buckets in the hash table.
• HashEntry encapsulates a key-value pair in the map.
• Each bucket is a linked list made up of multiple HashEntry objects.

6. References

Concurrency Talk (Part 4) — In-depth Analysis of ConcurrentHashMap - InfoQ