What are you studying?
Ask a CS concept or interview question. Get an explanation you can actually use.
Hash maps
A hash map stores key–value pairs in an array of buckets. A hash function turns each key into a bucket index, giving average constant-time lookup, insertion, and deletion when collisions are managed well.
Under the hood
01How it works
The map hashes a key and uses the result to locate a bucket. Different keys can land in the same bucket; implementations resolve this with chaining or open addressing. Equality checks distinguish keys within a collision.
02Why it matters
Hash maps trade extra memory for fast access by key. They are a common choice when you need to count, group, deduplicate, or index data without scanning every element.
03Common use cases
Frequency counters, caches, symbol tables, and two-sum lookups benefit from fast key-based access. Ordered traversal usually needs a different structure or an additional sorting step.
Code example
Pythoncounts = {}
for word in ["tree", "graph", "tree"]:
counts[word] = counts.get(word, 0) + 1
print(counts["tree"]) # 2Each word is the key; its count is the value. get supplies zero when the key has not appeared yet.
Complexity at a glance
| Operation | Time | Space | Notes |
|---|---|---|---|
| Lookup | O(1) avg · O(n) worst | O(n) | Worst case with many collisions |
| Insert / delete | O(1) avg · O(n) worst | O(n) | A resize can take O(n) |