Understanding Java HashMap: Implementation Principles, JDK7 Source Walkthrough, and Interview Insights

Hash tables are a crucial data structure used in many caching systems, and Java's HashMap is a classic example that frequently appears in technical interviews.

What is a hash table? It stores key‑value pairs in an array where a hash function maps a key to an index, achieving O(1) average time for insert, delete, and lookup when collisions are minimal.

HashMap implementation basics – The core of HashMap is an Entry[] array. Each Entry holds a key, value, hash, and a reference to the next entry, forming a linked list to resolve collisions (chain addressing).

transient Entry<K,V>[] table = (Entry<K,V>) EMPTY_TABLE;

The Entry class is defined as:

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next; // linked list
    int hash; // cached hash value
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

Key operations

put first ensures the table is allocated, handles a null key specially, computes the hash, finds the bucket index with indexFor(hash, table.length) , then either updates an existing entry or adds a new one. If the size exceeds the threshold and a collision would occur, the map is resized.

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) {
        if (e.hash == hash && (e.key == key || key.equals(e.key))) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

get mirrors the lookup process: compute the hash, locate the bucket, then traverse the chain comparing both hash and equals to find the matching entry.

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

Why the array length is always a power of two? Using a power‑of‑two size allows the index calculation hash & (length‑1) to be a fast bitwise operation, ensures uniform distribution of low‑order bits, and makes resizing cheap because only one additional high bit changes.

The inflateTable method rounds the requested capacity up to the nearest power of two, and resize creates a new array of double the size, re‑hashing entries via the transfer method.

private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

Overriding equals without hashCode leads to lookup failures because HashMap first compares the stored hash value; if two logically equal objects produce different hash codes, the map cannot locate the entry, resulting in a null return.

In the provided example, a Person class overrides equals but not hashCode , causing map.get(new Person(1234, "萧峰")) to return null even though the objects are equal by equals .

Conclusion – The article walks through the inner workings of Java's HashMap , explains design choices such as power‑of‑two sizing and chain addressing, and highlights the practical importance of correctly implementing equals and hashCode for reliable usage in real‑world code and interview scenarios.