How HashMap Works Internally in Java

The structure

A HashMap holds an array of buckets. A key is converted to a number, that number selects a bucket, and the entry is stored there. Because the bucket is found by arithmetic rather than by searching, lookup is constant time on average.

table (an array of buckets)
  0 -> null
  1 -> [ "sql"=5 ]
  2 -> null
  3 -> [ "java"=15 ] -> [ "html"=7 ]     two keys collided in bucket 3
  ...

Step by step: put

1. Call hashCode() on the key.
2. Spread the bits, so that keys differing only in the high bits still land in different buckets.
3. Compute the index as hash & (capacity - 1), which works because the capacity is always a power of two.
4. If the bucket is empty, store the entry there.
5. If not, compare with each entry in the bucket using hashCode and then equals. A match replaces the value; otherwise the entry is appended.
6. If the table is too full, resize.

// A simplified view of the index calculation
int hash = key.hashCode();
hash = hash ^ (hash >>> 16);            // spread the high bits downwards
int index = hash & (table.length - 1);   // cheaper than a modulo

Step by step: get

1. Compute the same index from the key.
2. Look in that bucket.
3. Compare each entry: first the stored hash, which is a fast integer test, and only then equals.
4. Return the value, or null if nothing matches.

This is exactly why equals and hashCode must agree. If two equal keys produce different hashes, they are looked for in different buckets, and the entry is stored but unreachable.

Collisions

Two different keys can produce the same index. That is normal and unavoidable, and the map keeps both entries in the same bucket.

Since Java 8, a heavily collided bucket converts to a red black tree. This turned the worst case for a map under a deliberate hash collision attack from O(n) into O(log n). Tree conversion requires the keys to be Comparable, or it falls back to a stable ordering.

Capacity, load factor and resizing

Map<String, Integer> map = new HashMap<>();          // capacity 16, load factor 0.75
Map<String, Integer> sized = new HashMap<>(1000);    // fewer resizes later

• Capacity is the number of buckets, always a power of two.
• Load factor is how full the table may get before it grows. The default of 0.75 balances space against collisions.
• When size > capacity * loadFactor, the capacity doubles and every entry is rehashed into the new table.

With the default settings, a map grows at 12, 24, 48 entries and so on. Each resize is O(n), so giving the expected size up front matters when inserting many entries.

Why keys must be immutable

List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value");        // stored in the bucket for hash of ["a"]

key.add("b");                 // hash is now that of ["a","b"]
map.get(key);                 // looks in a different bucket -> null
map.containsKey(key);         // false, although the entry is present

The entry has not moved; the map simply looks in the wrong place. Nothing detects this, which is why it is such a persistent bug.

A poor hashCode destroys performance

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

    @Override public int hashCode() { return 1; }        // legal, and terrible
    @Override public boolean equals(Object o) {
        return o instanceof BadKey k && k.id == id;
    }
}

Every key lands in one bucket, and the map degenerates into a single list or tree. Lookup becomes O(n) or O(log n) instead of O(1). A hash code must be legal and spread values well; Objects.hash(...) over the identifying fields does both.

Null keys

HashMap allows one null key, stored in bucket zero by special case, since null.hashCode() is impossible. TreeMap and ConcurrentHashMap reject null keys entirely.

Iteration order

Map<String, Integer> map = new HashMap<>();
map.put("banana", 1);
map.put("apple", 2);
map.put("cherry", 3);
System.out.println(map);   // order follows bucket layout, not insertion

The order is a consequence of the hashes and the current capacity. It can change when the map resizes, and it is not part of the specification. Never depend on it; use LinkedHashMap or TreeMap when order matters.

HashMap and threads

Map<String, Integer> shared = new ConcurrentHashMap<>();   // correct
// Map<String, Integer> unsafe = new HashMap<>();          // corrupt under concurrent writes

Concurrent writes during a resize can leave the internal structure inconsistent. ConcurrentHashMap locks per bucket and is the right choice for shared access.

Common mistakes

• Overriding equals without hashCode.
• Returning a constant from hashCode.
• Mutating a key after insertion.
• Depending on iteration order.
• Sharing a HashMap across threads without synchronisation.
• Leaving the default capacity when inserting hundreds of thousands of entries.

Best practices

• Use immutable keys: String, wrappers, enums, records, LocalDate.
• Build hashCode with Objects.hash over the same fields as equals.
• Size the map when the entry count is known and large.
• Use ConcurrentHashMap for shared maps.
• Use EnumMap when the keys are enum constants.

Practice

1. Explain, bucket by bucket, why a lookup fails when hashCode is not overridden.
2. Why is the capacity always a power of two, and how does that make the index calculation cheap?
3. At which sizes does a default HashMap resize, and what is the cost each time?
4. What changes when a bucket exceeds eight entries, and why was that introduced?
5. Demonstrate the mutable key problem with a two element list, then fix it with a record.

Conclusion

A HashMap is an array of buckets indexed by a spread hash code, with collisions kept in a list or a tree and the table doubling as it fills. Every rule about keys, immutability, equals with hashCode, and unpredictable ordering follows directly from that design.