Data structures and patterns · Question 35 of 50

How does a HashMap work inside?

What they're checking

Hashing, collisions, resizing and complexity.

The answer

A hash map is an array of buckets. To store a key, it computes the key's hash, turns it into a bucket index (the hash modulo the array size) and stores the key and value there. Two keys can land in the same bucket, a collision: they are kept in a small list (Java turns long ones into a balanced tree), or the map probes for the next free slot (open addressing).

Lookups are O(1) on average and O(n) in the worst case, when everything collides. When the map gets too full (Java's default load factor is 0.75), it grows, usually doubling, and re-hashes every entry into the new array. Keys need a stable hash and consistent equality.

The picture

put("apple", 5):  hash("apple") = 9183  →  9183 % 8 = 7
[0] [1] [2] [3] [4] [5] [6] [7]
                             └─▶ ("apple", 5) ─▶ ("grape", 2)   a collision
75% full → grow to 16 buckets and re-hash everything
The follow-up they'll ask

What happens if you change a key after putting it in the map?

Show the answer

Its hash changes, so the map looks in the wrong bucket and cannot find it. Use keys that never change.

Your progress stays on this device.