Deep Dive into Java HashMap: Source Code Analysis and Design Concepts

Following the previous overview of the Java Collections Framework, this article begins a detailed source‑code analysis of the HashMap class, using Oracle JDK 1.7.0_71 as the reference.

Signature

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

The class implements the marker interfaces Cloneable (enabling shallow copying via Object#clone()) and Serializable (allowing object serialization).

Cloneable Interface

Cloneable

does not declare a clone() method, which means a class can claim to be cloneable without actually overriding clone(); this design flaw is discussed in *Effective Java*.

Map Interface

The Map interface defines the three collection‑view methods keySet(), values(), and entrySet(), each returning a view of the keys, values, or key‑value pairs respectively.

AbstractMap Abstract Class

AbstractMap

provides default implementations for many Map methods, reducing the amount of code a concrete map implementation must write.

Design Concept – Hash Table

HashMap

is built on a hash table where a key is transformed by a hash function into an index within the bucket array [0, length). Collisions are handled by chaining (linked lists of Entry objects).

Two common strategies for computing the index are:

Using a prime‑sized table and hashCode(key) % length.

Using a power‑of‑two table and hashCode(key) & (length‑1), which is the approach taken by HashMap.

Hash Function Design

final int hash(Object k) {
    int h = hashSeed;
    if (h != 0 && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

The supplemental hash spreads high‑order bits to low‑order bits, reducing collisions when the table size is a power of two.

Core Operations

get()

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

private 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;
}

put()

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;
}

private void addEntry(int hash, K key, V value, int bucketIndex) {
    if (size >= threshold && table[bucketIndex] != null) {
        resize(2 * table.length);
        hash = (key != null) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

private void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

remove()

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null) ? null : e.value;
}

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) return null;
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;
    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++; size--;
            if (prev == e) table[i] = next; else prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
    return null;
}

Iterator – Fast‑Fail

The internal HashIterator checks the modification count on each access and throws ConcurrentModificationException if the map has been structurally modified.

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;
    int expectedModCount = modCount;
    int index;
    Entry<K,V> current;
    // constructor walks the table to find the first non‑null entry
    // hasNext(), nextEntry(), and remove() implement fast‑fail semantics
}

Serialization

Because the bucket array table is transient, HashMap provides custom writeObject and readObject methods that serialize the size, load factor, and each key/value pair, then rebuild the table on deserialization.

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    s.writeInt(table == EMPTY_TABLE ? roundUpToPowerOf2(threshold) : table.length);
    s.writeInt(size);
    for (Map.Entry<K,V> e : entrySet0()) {
        s.writeObject(e.getKey());
        s.writeObject(e.getValue());
    }
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    // read and ignore bucket count, then read mappings and re‑populate
    int mappings = s.readInt();
    if (mappings > 0) inflateTable(computeCapacity(mappings, loadFactor));
    for (int i = 0; i < mappings; i++) {
        K key = (K) s.readObject();
        V value = (V) s.readObject();
        putForCreate(key, value);
    }
}

Conclusion

The article summarizes the essential mechanisms of HashMap: a power‑of‑two bucket array, a supplemental hash function to disperse keys, chaining for collision resolution, O(1) average‑case performance for get/put/remove, fast‑fail iterators, and a custom serialization strategy that avoids persisting the transient table.