How Does HashMap Work Internally?

A HashMap is an array of buckets, each bucket holding a linked list of entries. The key steps are these.

Hashing. The key's hashCode is computed, and the JVM applies a spread function to it — an xor-and-shift that mixes the high bits down, so that keys whose hash codes differ only in their upper bits still land in different buckets.

Index. The spread hash is masked with the table length minus one to produce an index into the table array. Because the table length is always a power of two, that mask is equivalent to a modulo, and it is fast.

Bucket lookup. The map walks the entries in that bucket, comparing each entry's hash first and then calling equals on the key. If a match is found, the value is replaced; otherwise the new entry is appended to the bucket's list.

Resizing. When the number of entries exceeds the load factor — 0.75 by default — the table doubles and the entries are redistributed. Because the index is derived from the hash and the table length, each entry goes to either its old index or that index plus the old length, which makes the resize linear rather than requiring every entry to be rehashed from scratch.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("one", 11);          // replaces the value, does not add an entry

        System.out.println("size       : " + map.size());
        System.out.println("get one   : " + map.get("one"));
        System.out.println("get two   : " + map.get("two"));
        System.out.println("get three : " + map.get("three"));

        // The hash code decides the bucket.
        System.out.println("hash one  : " + "one".hashCode());
        System.out.println("containsKey: " + map.containsKey("two"));

        // Iteration order is not guaranteed and may change after a resize.
        System.out.println("entries    : " + map.entrySet());
    }
}

The output confirms the observable behaviour: the map holds two entries because putting the same key twice replaced the value, a missing key returns null, and iteration order is not sorted or insertion-ordered.

Two implementation details that come up in interviews. The map uses a lazy resize — the table is resized when the next write happens, not eagerly — and the tree is stored as an array of Node objects with an explicit hash field, which removed the need to recompute the hash when moving an entry during a resize.

Two different keys can produce the same bucket index — that is a collision, and it is completely normal. The map handles it by keeping the bucket as a linked list of entries and walking that list on lookup, comparing the stored hash first and then calling equals on the key.

As long as the buckets stay short, that is fine. The problem starts when many keys land in the same bucket, because lookups degrade to a linear scan of that list. The classic way to cause it is a key class with a poor hashCode that returns a constant, so every key hashes to the same index.

A bucket that grows beyond eight entries and whose table capacity is at least 64 is treeified: the linked list is converted into a red-black tree, keyed on the hash and then on the comparable key. That turns the lookup cost from O(n) into O(log n) for the pathological bucket. The tree is untreeified again if it shrinks below a threshold, which stops the memory cost of a tree structure hanging around for a bucket that no longer needs it.

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

public class Main {
    public static void main(String[] args) {
        // Every key lands in the same bucket: a deliberate collision.
        Map<BadKey, String> map = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            map.put(new BadKey(i), "value" + i);
        }

        System.out.println("size     : " + map.size());
        System.out.println("lookup   : " + map.get(new BadKey(3)));
        System.out.println("all in one bucket: true");

        // A well-behaved key spreads across the table.
        Map<GoodKey, String> good = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            good.put(new GoodKey(i), "value" + i);
        }
        System.out.println("good lookup : " + good.get(new GoodKey(3)));
    }
}

class BadKey {
    private final int id;

    BadKey(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return 1;                     // every instance lands in one bucket
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof BadKey && ((BadKey) o).id == id;
    }
}

class GoodKey {
    private final int id;

    GoodKey(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return id;                    // spreads across the table
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof GoodKey && ((GoodKey) o).id == id;
    }
}

The output shows both cases returning the correct value — a hash map is still correct with terrible hashes, just slower. The difference is invisible until the number of keys grows, at which point the badly hashed map degrades to linear scans while the good one stays logarithmic.

That is why the guidance about keys is really about performance rather than correctness. Any object with a correct equals and hashCode can be used as a key and the map will behave correctly. But a key whose hashCode returns a constant, or whose hashCode is based on a mutable field, turns every lookup into a scan or makes the entry unreachable.

The map uses the hash to decide which bucket to look in and equals to decide whether the key it found there is the one you asked for. Both must agree with each other, and both must be stable for the lifetime of the entry. Break either rule and the map still compiles and still returns answers — just wrong ones, or none at all.

If equals is overridden but hashCode is not. The default hashCode is identity-based, so two objects that equals says are equal have different hash codes. They land in different buckets, and a lookup with an equal-but-different instance never finds the entry. In a HashSet this shows up as a set that contains duplicates of what you believe is the same value.

If hashCode is overridden but equals is not. Then two equal keys can land in different buckets and the lookup misses. The hash contract also requires that equal objects have equal hash codes, so overriding one without the other is always wrong.

If the hash code is based on a mutable field. Changing that field after the key is in the map changes where the entry would now be found, and the old entry becomes unreachable — it is still counted in the size but can never be retrieved. The same applies to mutating a field that equals uses.

The rules to follow are short. Override both or neither. Make the hash code consistent with equals — derive both from the same fields. Use fields that do not change. And if you are writing a value class, a Java record gives you correct equals and hashCode for free, generated from the record components, which removes the whole class of bug.