How does a hash map work internally?
Answer
- An array of buckets.
hash(key) % capacity chooses the bucket. - Collisions (two keys, same bucket): chaining (a small list per bucket) or open addressing (try the next slots; Python dicts do this).
- When it gets too full (load factor), it resizes: a bigger array and every key re-placed. Amortized O(1) inserts.
- Keys must be hashable and must not change; equal keys must have equal hashes.
- Average O(1) get/put/delete; worst case O(n) with many collisions.
Practice this question in Repaso
