HashMap Internals

CS FundamentalsMiddata-structures

The Question

How does a hash map work internally?

What a Strong Answer Covers

• hash → bucket index
• collision resolution named
• O(1) average
• "load factor/resize

Senior-Level Answer

A HashMap is a data structure that stores key-value pairs and provides O(1) average-case lookup, insertion, and deletion. It achieves this by using a hash function to convert keys into array indices.

When you insert a key-value pair, the HashMap first computes the hash code of the key — an integer that represents the key. It then maps this hash code to a bucket index, typically using modular arithmetic: index = hash(key) % array_length. The value is then stored at that index in the underlying array.

The critical challenge is collision handling — what happens when two different keys hash to the same bucket index. There are two primary strategies.

Chaining stores a linked list (or another collection) at each bucket. When a collision occurs, the new entry is appended to the list. To look up a key, the HashMap hashes it to find the bucket, then traverses the list comparing keys using equals(). Java's HashMap uses chaining, and since Java 8, converts the linked list to a red-black tree when a single bucket exceeds 8 entries, improving worst-case from O(n) to O(log n).

Open addressing stores all entries directly in the array. When a collision occurs, the HashMap probes for the next available slot. Linear probing checks slots sequentially. Python's dict uses open addressing. The advantage is better cache locality; the disadvantage is more complex deletion (requires tombstone markers).

The load factor is the ratio of stored entries to total buckets (n / capacity). Most implementations define a threshold — commonly 0.75 — and when exceeded, the HashMap rehashes: allocating a new array (typically double the size) and reinserting every entry. This is O(n) but happens infrequently enough that insertions remain O(1) amortized.

For a HashMap to work correctly, keys must satisfy two contracts: the hash function must be deterministic, and if two keys are equal (via equals()), they must have the same hash code. Violating this contract causes the HashMap to lose entries or return incorrect values.

What Separates a 2/3 from a 3/3

Common Mistakes

• Saying HashMap is O(1) without qualifying it as average-case — worst case is O(n)
• Not explaining how collisions are resolved — just saying 'it handles collisions'
• Forgetting the equals/hashCode contract
• Confusing the hash code with the bucket index
• Not mentioning rehashing or load factor

Follow-Up Questions

• What happens if you use a mutable object as a HashMap key and then modify it? — The hash code changes but the object stays in the original bucket. Future lookups search the wrong bucket.
• Why does Java's HashMap use a power-of-two size for the internal array? — Allows bitwise AND instead of modulo, which is faster.
• How does a ConcurrentHashMap differ from a regular HashMap? — Fine-grained locking or lock-free CAS operations for thread-safe concurrent access.
• What is the time complexity of rehashing? — O(n) but amortized O(1) per insert over the sequence of insertions.
• Compare chaining and open addressing. — Chaining is simpler and handles high load factors. Open addressing has better cache performance but degrades faster.

Related Questions

• Process vs Thread
• Race Condition
• Deadlock — 4 Conditions, Prevention
• Thread Safety — Is dict Thread Safe?
• Hash Collision — Chaining vs Open Addressing