Stage 3: Core APIs, lesson 5 of 12

How HashMap works inside

Advanced3 min read@since 9Code runs on your Java 25
Explain it forThe essentials plus production detail and pitfalls.

HashMap stores entries in an array of buckets.

  1. put(k, v) computes k.hashCode(), mixes the high bits into the low bits, then picks a bucket with hash & (n - 1).
  2. If the bucket is empty, the entry goes in. Otherwise Java walks the bucket comparing keys with equals(): the same key means the value is replaced, a new key is appended.
  3. Since Java 8, a bucket holding 8 or more entries (in a table of at least 64 buckets) becomes a red-black tree, so worst-case lookup is O(log n) instead of O(n).
  4. When the size passes capacity × load factor (16 × 0.75 = 12 by default), the table doubles and the entries are redistributed.

One null key is allowed. HashMap is not thread-safe.

Example

Java
Map<String, Integer> stock = new HashMap<>(64);    // presize if you know roughly how many

stock.put("java-book", 10);
stock.put("java-book", 12);                        // same key: value replaced
stock.computeIfAbsent("spring-book", k -> 5);
stock.computeIfPresent("java-book", (k, v) -> v - 1);

// Why keys must not change after insertion:
List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> m = new HashMap<>();
m.put(key, "value");
key.add("b");                                      // hashCode changes
System.out.println(m.get(key));                    // null: the entry is stranded

Common mistake

Using a mutable object as a key and changing it after insertion. The entry becomes unreachable.

Under the hood

A power-of-two capacity makes & (n - 1) a fast modulo, and the hash spreading step (h ^ (h >>> 16)) compensates for weak hashCodes. During a resize in Java 8+, each entry either stays at index i or moves to i + oldCapacity, so nothing is rehashed. In Java 7, concurrent resizing could create a cycle in a bucket and hang a thread forever, one reason to use ConcurrentHashMap, which locks per bucket (CAS plus synchronized on the first node) and forbids null keys and values.

Check yourself

In Java 8+, what does a crowded bucket turn into?

How this connects

Where this leads

Part of Job-ready backend developer, Crack the Java interview.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.