HashMap vs ConcurrentHashMap: Deep Dive into JDK 1.7 and 1.8 Implementations

HashMap (JDK 1.7)

Core structure: an array Entry<K,V>[] where each bucket is a linked list. Important fields include DEFAULT_INITIAL_CAPACITY (16), loadFactor (0.75), threshold, the table array that stores entries, and size. When size >= capacity * loadFactor the map resizes, rehashing all entries.

put method

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null) {
        return putForNullKey(value);
    }
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

The algorithm initializes the table if needed, handles a null key, computes the hash, finds the bucket, traverses the linked list to replace an existing value, and finally adds a new entry (which may trigger a resize).

get method

public V get(Object key) {
    if (key == null) {
        return getForNullKey();
    }
    Entry<K,V> entry = getEntry(key);
    return entry == null ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
            return e;
        }
    }
    return null;
}

It computes the hash, locates the bucket, and walks the chain until the matching key is found.

HashMap (JDK 1.8)

The overall design remains array‑plus‑chain, but two major changes improve performance: TREEIFY_THRESHOLD (default 8) triggers conversion of a bucket’s linked list into a red‑black tree, reducing lookup from O(N) to O(log N).

The internal node class is renamed to Node<K,V> but still stores key, value, hash, and next.

put method

public V put(K key, V value) {
    // 1. Initialize table if necessary
    // 2. Compute hash and locate bucket
    // 3. If bucket is empty, insert new Node
    // 4. If bucket contains a tree, delegate to tree insertion
    // 5. Otherwise traverse linked list, replace value if key matches
    // 6. If list size exceeds TREEIFY_THRESHOLD, convert to tree
    // 7. Resize if load factor exceeded
    // 8. Return previous value or null
}

The steps are similar to JDK 1.7 but include treeification and a more compact handling of empty buckets.

get method

public V get(Object key) {
    // Compute hash, locate bucket
    // If the first node is a tree node, use tree search
    // Otherwise traverse linked list
    // Returns value or null
}

ConcurrentHashMap (JDK 1.7)

Implements a segmented lock architecture. The map consists of an array of Segment<K,V> objects; each segment extends ReentrantLock and protects its own HashEntry<K,V>[] table. Key fields in a segment include a volatile table, count, threshold, and loadFactor. HashEntry mirrors HashMap ’s entry but its fields are volatile for visibility.

put method

public V put(K key, V value) {
    if (value == null) throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    Segment<K,V> s = (Segment<K,V>) UNSAFE.getObject(segments, (j << SSHIFT) + SBASE);
    if (s == null) s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    V oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    return oldValue;
                }
                e = e.next;
            } else {
                // insert new entry, possibly resize
                break;
            }
        }
    } finally {
        unlock();
    }
    return null;
}

The method locates the appropriate segment, acquires its lock (spinning if necessary), then performs bucket‑level insertion identical to HashMap. Volatile values guarantee visibility, but atomicity still requires locking.

get method

public V get(Object key) {
    int h = hash(key);
    long u = ((h >>> segmentShift) & segmentMask) << SSHIFT + SBASE;
    Segment<K,V> s = (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
    if (s != null && (tab = s.table) != null) {
        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;
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

Lookup is lock‑free: it computes the segment, reads the volatile table, and traverses the chain, relying on the volatile value for up‑to‑date reads.

ConcurrentHashMap (JDK 1.8)

Removes the segment array and uses a single Node<K,V>[] table. Concurrency is achieved with a combination of CAS (compare‑and‑set) for lock‑free bin insertion and synchronized blocks for updates that require coordination. Values and next pointers are volatile.

put method

public V put(K key, V value) {
    if (value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    for (;;) {
        Node<K,V>[] tab = table;
        int n = tab.length;
        int i = (n - 1) & hash;
        Node<K,V> f = tab[i];
        if (f == null) {
            if (CASBin(tab, i, null, new Node<>(hash, key, value, null)))
                break; // inserted
        } else if (f.hash == MOVED) {
            tab = helpTransfer(tab, f);
        } else {
            synchronized (f) {
                // handle linked‑list insertion, treeification, or resize
            }
        }
    }
    // possibly treeify if bin count exceeds TREEIFY_THRESHOLD
    return null;
}

The method first tries a lock‑free CAS insertion; if the bin is being moved during resize it assists the transfer; otherwise it falls back to a synchronized block to safely modify the bin. When a bin’s size exceeds TREEIFY_THRESHOLD, it is converted to a red‑black tree.

get method

public V get(Object key) {
    int h = spread(key.hashCode());
    Node<K,V>[] tab = table;
    int n = tab.length;
    Node<K,V> e = tab[(n - 1) & h];
    if (e != null) {
        if (e.hash == h && (e.key == key || key.equals(e.key)))
            return e.val;
        if (e instanceof TreeNode)
            return ((TreeNode<K,V>)e).find(h, key, null);
        while ((e = e.next) != null) {
            if (e.hash == h && (e.key == key || key.equals(e.key)))
                return e.val;
        }
    }
    return null;
}

Lookup is lock‑free: it computes the hash, reads the bin, checks for a direct match, then either traverses a tree or a linked list.

Key Differences and Performance Impact

JDK 1.8 HashMap replaces long linked lists with red‑black trees when a bucket exceeds TREEIFY_THRESHOLD, improving worst‑case lookup to O(log N).

ConcurrentHashMap 1.7 uses segment locks, allowing up to concurrencyLevel threads to modify different segments simultaneously.

ConcurrentHashMap 1.8 eliminates segments, using CAS + synchronized for bin updates, reducing contention and simplifying resizing.

Both 1.8 implementations rely on volatile fields for memory visibility and benefit from the JDK’s optimized synchronized implementation.