How HashMap Works Internally

HashMap is the most widely used implementation of the Map interface in Java, and it is also one of the most misunderstood. Most developers know that it stores key-value pairs and offers "average O(1)" performance for get() and put(), but far fewer can explain why that performance holds, or what happens the moment two unrelated keys collide. Understanding HashMap's internals is not academic trivia — it directly explains real production bugs like objects "disappearing" from a map, lookups silently returning null, or a HashMap that mysteriously becomes as slow as a linked list.

This lesson walks through the actual mechanics: the bucket array, the hashing and spreading function, collision resolution via chaining and treeification, the equals()/hashCode() contract, and the load factor and resizing process that keeps HashMap fast as it grows.

Why it matters

This is probably the single most asked Java interview question, and it is asked because it has practical consequences. A key class with a wrong hashCode() produces a map that silently fails to find entries, and a poor one turns a fast map into a slow one. Understanding buckets, collisions and resizing explains both problems.

The Bucket Array and Hash Spreading

Internally, a HashMap holds an array of "buckets" (technically an array of Node references, called the table). Each bucket can hold zero, one, or many entries. When you call put(key, value), HashMap does not search the whole array — it computes an index directly from the key's hash code so it can jump straight to the right bucket.

The index is computed in two steps. First, Java calls key.hashCode() to get a 32-bit integer. Second, HashMap applies an internal "spreading" function that XORs the higher 16 bits of the hash into the lower 16 bits (roughly hash ^ (hash >>> 16)). This spreading step matters because the bucket index is ultimately derived using only the lower bits of the hash (via a bitwise AND with table.length - 1, since the table size is always a power of two). Without spreading, two hash codes that differ only in their high bits would collide constantly, because those high bits would otherwise never influence which bucket is chosen.

• bucketIndex = (table.length - 1) & spreadHash(key.hashCode())
• Table length is always a power of two (default 16), which makes the bitwise AND behave like a fast modulus operation.
• Two keys with completely different hashCode() values can still land in the same bucket once reduced to an index — this is expected and normal, not a bug.

Collisions: Chaining and Treeification

A collision happens when two different keys are mapped to the same bucket index. HashMap handles this by chaining: each bucket effectively becomes a linked list of entries. When you call get(key), HashMap jumps to the bucket via the hash, then walks the (usually very short) chain, comparing each stored key with equals() until it finds a match.

As long as chains stay short, this is still effectively O(1) because chain length rarely grows past one or two entries in a well-distributed map. But since Java 8, if a single bucket's chain grows beyond a threshold (8 entries) and the table has at least 64 buckets, HashMap converts that bucket's linked list into a red-black tree instead. A red-black tree gives worst-case O(log n) lookup within that bucket instead of O(n), which protects the map against pathological cases — for example, an attacker deliberately supplying many keys that hash to the same bucket ("hash flooding") to degrade a naive HashMap into a slow linked list. If entries are later removed and the bucket shrinks back down (below 6 entries), Java converts it back into a plain linked list, since a tree has more overhead than it's worth for a short chain.

The equals() and hashCode() Contract

HashMap's correctness depends entirely on a contract between hashCode() and equals(): if two objects are equal according to equals(), they must return the same hashCode(). The reverse is not required — unequal objects may share a hash code (that's a normal collision) — but equal objects must never disagree on their hash code.

Breaking this contract causes silent corruption, not a loud exception. If you override equals() to compare two Point objects by their x and y fields but forget to override hashCode() to match, then two logically "equal" Point keys can compute different hash codes, land in different buckets, and the map will treat them as two separate keys. A get() call with a key that is equals() to one already stored can return null, because HashMap never even looks in the bucket where the original entry lives. This is one of the most common and hardest-to-diagnose bugs involving custom key objects — always override hashCode() and equals() together, typically using IDE generation or java.util.Objects.hash().

• Contract: a.equals(b) == true implies a.hashCode() == b.hashCode().
• Not required in reverse: unequal objects may share a hash code (a legitimate collision).
• A mutable field used in hashCode()/equals() is dangerous as a map key — mutating it after insertion can make the key "unfindable" because its bucket location no longer matches its current hash.

Load Factor and Resizing (Rehashing)

HashMap tracks how full it is using a load factor, which defaults to 0.75. The map maintains a threshold equal to capacity × loadFactor (for the default capacity of 16, that's 12). Once the number of stored entries exceeds this threshold, HashMap resizes: it doubles the internal array's capacity (e.g. 16 → 32) and then rehashes — recomputing the bucket index for every existing entry against the new, larger table, since the bucket index formula depends on table.length.

A lower load factor means more empty space and fewer collisions (faster lookups) at the cost of more memory; a higher load factor saves memory but increases the chance of collisions and longer chains. The default of 0.75 is a deliberate middle ground validated over years of real-world use. If you know a HashMap will hold a very large, predictable number of entries, you can avoid repeated resizing (each resize is an O(n) operation) by specifying an initial capacity upfront, e.g. new HashMap<>(256).

Finally, a poorly written hashCode() is a real performance hazard: if hashCode() always returns the same constant (say, 42) for every instance, then every single key lands in the exact same bucket regardless of the table size. get() and put() then degrade from O(1) to O(n), because HashMap must linearly scan (or tree-walk) every entry in that one overloaded bucket on every operation — effectively turning your HashMap into a linked list with extra overhead.

Time complexity

Examples

import java.util.HashMap;
import java.util.Objects;

public class BadHashDemo {

    static class BadKey {
        final int id;
        BadKey(int id) { this.id = id; }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof BadKey)) return false;
            return this.id == ((BadKey) o).id;
        }

        @Override
        public int hashCode() {
            return 42; // BAD: same bucket for every key, defeats hashing entirely
        }
    }

    static class GoodKey {
        final int id;
        GoodKey(int id) { this.id = id; }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof GoodKey)) return false;
            return this.id == ((GoodKey) o).id;
        }

        @Override
        public int hashCode() {
            return Objects.hash(id); // GOOD: spreads keys across buckets
        }
    }

    public static void main(String[] args) {
        HashMap<BadKey, String> badMap = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            badMap.put(new BadKey(i), "value" + i);
        }
        // All 5 entries live in the SAME bucket chain -> lookups degrade toward O(n)
        System.out.println("Bad map size: " + badMap.size());
        System.out.println("Lookup: " + badMap.get(new BadKey(3)));

        HashMap<GoodKey, String> goodMap = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            goodMap.put(new GoodKey(i), "value" + i);
        }
        System.out.println("Good map size: " + goodMap.size());
        System.out.println("Lookup: " + goodMap.get(new GoodKey(3)));
    }
}

Bad map size: 5
Lookup: value3
Good map size: 5
Lookup: value3

import java.util.HashMap;

public class BrokenContractDemo {

    static class Point {
        final int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Point)) return false;
            Point p = (Point) o;
            return x == p.x && y == p.y;
        }
        // hashCode() NOT overridden -> uses Object's identity-based hash
    }

    public static void main(String[] args) {
        HashMap<Point, String> map = new HashMap<>();
        map.put(new Point(1, 2), "origin-ish");

        // A logically equal key, but a different identity hash -> different bucket
        String result = map.get(new Point(1, 2));
        System.out.println(result);
    }
}

null

Exercise

Point overrides equals() but not hashCode(), so a second Point(1, 2) goes to a different bucket and the lookup returns null. Add a hashCode() that agrees with equals().

Expected output: found

import java.util.HashMap;
import java.util.Map;

class Point {
    final int x;
    final int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point other = (Point) o;
        return x == other.x && y == other.y;
    }

    // TODO: override hashCode() so equal points have equal hash codes
}

public class PointLookup {
    public static void main(String[] args) {
        Map<Point, String> labels = new HashMap<>();
        labels.put(new Point(1, 2), "found");

        System.out.println(labels.get(new Point(1, 2)));
    }
}

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

class Point {
    final int x;
    final int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point other = (Point) o;
        return x == other.x && y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y); // same fields as equals()
    }
}

public class PointLookup {
    public static void main(String[] args) {
        Map<Point, String> labels = new HashMap<>();
        labels.put(new Point(1, 2), "found");

        System.out.println(labels.get(new Point(1, 2))); // found
    }
}

Quick quiz

Interview questions