Deep Dive into Java HashMap: Implementation Details, Internals, and Interview Questions

HashMap is a frequently asked interview topic that reflects a candidate's grasp of core Java collections, data structures (arrays, linked lists, red‑black trees), and the importance of correctly implementing equals and hashCode methods.

The default initial capacity is 16, the default load factor is 0.75, and the threshold is calculated as capacity * loadFactor. When the number of entries exceeds the threshold, the map expands.

In JDK 1.8, HashMap is built from an array + linked list + red‑black tree. Each bucket stores a Node object that holds hash, key, value, and a reference to the next node. The source code for the constants and the Node class is shown below:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Node<K,V>[] table;
transient int size;
int threshold;

static final class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // constructors and getters omitted for brevity
}

The bucket array length is always a power of two, which enables fast index calculation using hash & (length‑1) instead of the slower modulo operation. The method tableSizeFor(int cap) finds the smallest power‑of‑two greater than or equal to the requested capacity.

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

During resizing, a new array twice the size of the old one is allocated, and existing entries are re‑hashed. Because the length is a power of two, each entry either stays in its original index or moves to oldIndex + oldCap, which avoids recomputing the full hash.

final Node<K,V>[] resize() {
    // simplified logic: double capacity, rehash entries, handle tree nodes, etc.
}

If a bucket's linked list grows beyond a threshold (default 8) and the table size is at least 64, the list is transformed into a red‑black tree (treeification) to keep lookup time logarithmic.

Lookup uses a custom hash(Object key) method that mixes the high and low 16 bits of the original hashCode to improve distribution:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The get(Object key) method first computes the hash, then locates the bucket and traverses the linked list or tree to find the matching entry.

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

Insertion follows these steps: initialize the table if necessary, compute the bucket index, insert a new node if the bucket is empty, otherwise handle collisions by chaining, possibly converting the chain to a tree, and finally trigger a resize when the size exceeds the threshold.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Deletion locates the bucket, searches for the matching node, removes it, and updates the linked list or tree structure accordingly.

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

Iterating a HashMap uses a fail‑fast iterator that checks a modification count ( modCount) on each access; if the map is structurally modified during iteration, a ConcurrentModificationException is thrown. The iterator walks the bucket array and each chain in turn.

final class HashIterator {
    Node<K,V> next;
    Node<K,V> current;
    int expectedModCount = modCount;
    int index;
    // hasNext, nextNode, remove implementations omitted for brevity
}

Because keys are stored based on their hash, custom objects used as keys must correctly override equals and hashCode. The article demonstrates this with a Person class where failing to override hashCode prevents retrieval of a value inserted with an equivalent key.

class Person {
    Integer id;
    String name;
    @Override public boolean equals(Object obj) { /* compare id */ }
    // hashCode should also be overridden
}

In summary, the article covers HashMap's core implementation, including default parameters, internal node structure, resizing logic, treeification, lookup, insertion, deletion, iteration, and the necessity of proper equals / hashCode implementations, providing a solid foundation for interview preparation and deeper understanding of Java collections.