Micro-questions over the hash maps module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The object itself
1. What is a hash map?
Answer
A structure that stores pairs of things so you can look one up by the other almost instantly.
2. What is it called in Python, C++, Java and JavaScript?
Answer
dict in Python, map in C++ and Java, object (and Map) in JavaScript. Also called a hash table or a dictionary generally.
3. Why do hash maps exist?
Answer
Arrays let you look up by position. Hash maps let you look up by any key you choose — a username, a product code, a word — at the same speed.
4. What is a key?
Answer
The thing you look something up by. Keys are unique within the map; storing a pair with an existing key overwrites the old value.
5. What is a value?
Answer
The thing stored against a key. Values have no restrictions at all and can repeat freely.
6. What is a hash set, and how does it relate to a hash map?
Answer
A hash map that stores keys with no values. It answers exactly one question instantly: have I seen this before?
B. The vocabulary
7. What is a hash function?
Answer
A function taking a key and returning a large integer. The same key always gives the same integer; different keys usually give different ones. It turns “look up this word” into “go to this array position”.
8. What is a bucket?
Answer
One slot in the underlying array where entries are kept. The hash function decides which bucket a key belongs in.
9. How is a hash value turned into a bucket index?
Answer
Modulo the number of buckets: index = hash(key) % capacity.
10. What is a collision?
Answer
Two different keys landing in the same bucket.
11. Are collisions a bug?
Answer
No, and they cannot be avoided — there are more possible keys than buckets, so some must share. The design question is never how to prevent them, only how to handle them.
12. What is chaining?
Answer
Each bucket holds a small list of all entries that landed there; a lookup walks that short list.
13. What is open addressing?
Answer
Every entry lives directly in the flat array. When a bucket is taken, the entry goes into another bucket found by a fixed rule.
14. What is linear probing?
Answer
The simplest open-addressing rule: if slot is taken, try , then , and so on.
15. What is the load factor, and what is its symbol?
Answer
How full the map is — entries divided by buckets, written .
16. What is rehashing?
Answer
Allocating a larger bucket array and recomputing the bucket for every existing entry — necessary because the bucket depends on the array size. It is .
C. The pipeline
17. Walk through the three steps of map["apple"] = 100.
Answer
- Hash the key:
hash("apple")→ a large integer. - Reduce to an index:
integer % capacity→ e.g. bucket 5. - Store the pair in bucket 5.
18. Why must the hash be deterministic?
Answer
Because lookup repeats the same computation. If hash("apple") returned something different the second time, you would probe the wrong bucket and the entry would be unreachable.
19. What property makes a hash function good?
Answer
It spreads keys uniformly across buckets, so no bucket gets disproportionately many. Uniform spread is what keeps chains short and lookups .
D. Collision strategies compared
20. Chaining vs open addressing — where does each store the entries?
Answer
Chaining: the bucket holds a pointer to a list node, so entries live scattered on the heap. Open addressing: everything lives in one flat array.
21. Which has better cache behaviour, and why?
Answer
Open addressing. Probing walks sequential array slots, so the probe sequence is usually already in the cache line you fetched. Chained list nodes are scattered, so each hop is a potential cache miss.
22. What load factor can each tolerate?
Answer
Chaining can exceed — the lists just grow. Open addressing must stay below , because it fails outright when the array is full.
23. Why is deletion harder under open addressing?
Answer
Emptying a slot breaks the probe chain: a later key that probed past that slot becomes unfindable. The fix is a tombstone — a marker meaning “empty, but keep probing past me”.
24. Which strategy do modern languages use?
Answer
Open addressing — Python’s dict, Rust’s HashMap, C++ flat maps. Chaining is the textbook classic and what Java’s HashMap uses.
E. Load factor and resizing
25. What happens if the load factor is left to climb?
Answer
Collisions become frequent, chains and probe sequences get long, and lookups degrade toward scans.
26. What is the typical load factor threshold?
Answer
Around .
27. What are the three steps when the threshold is crossed?
Answer
- Allocate a new bucket array with double the capacity.
- Re-hash every existing key into it.
- Free the old array.
28. Why can’t the old bucket assignments simply be copied across?
Answer
The bucket index is hash % capacity, and the capacity just changed. Every key’s index must be recomputed.
29. Why does this make hash map operations amortised ?
Answer
Same argument as dynamic arrays: capacity doubles, so rehashes get exponentially rarer and their cost spreads over an ever-larger number of cheap operations.
F. Costs
30. Average and worst-case cost of lookup?
Answer
average, worst case.
31. Average cost of insert and delete?
Answer
amortised for insert (rehashing), average for delete. Both worst case.
32. Space complexity?
Answer
— plus the deliberately unused buckets that keep the load factor low.
33. When does the worst case actually happen?
Answer
When every key lands in one bucket — from a bad hash function, or from an attacker choosing colliding keys on purpose.
34. What is hash collision denial-of-service?
Answer
An attacker submits keys chosen to collide (e.g. as form fields or JSON keys), forcing every lookup to and collapsing the server under work. It is why languages now randomise their hash seed at startup.
G. The ADT and what is absent
35. List the hash map ADT.
Answer
put(key, value), get(key), contains(key), delete(key) — all average; size() — ; keys()/values()/items() — , in no guaranteed order.
36. Why can a hash map not tell you the smallest key?
Answer
The smallest key sits in an arbitrary bucket, so you would have to check all of them. A heap does this in ; a balanced tree in .
37. Why can a hash map not answer range queries?
Answer
Nearby keys are nowhere near each other in memory — the hash deliberately scattered them. This is exactly why databases index with B-trees rather than hash tables.
38. What single cause explains all three missing operations?
Answer
Hashing deliberately destroys order. Scattering similar keys to unrelated buckets is what avoids collisions, and in scattering it throws away every relationship between keys.
39. Python dict preserves order since 3.7. Does that contradict the above?
Answer
No. It preserves insertion order, not sorted order, using an extra list kept alongside the buckets. It gives you none of min-key, range query, or successor.
40. Why must keys be immutable?
Answer
If a key’s internal data changes after insertion, its hash changes, so it now belongs in a different bucket than the one it sits in — and becomes permanently unreachable. In Python, lists cannot be keys; tuples can.
H. Using them
41. What is “the single most common speedup in software engineering”?
Answer
Replacing a list with a set for membership testing — turning an scan inside an loop ( total) into an check inside it ( total).
42. Why is if item in some_list a trap?
Answer
in on a list is a full linear scan. It looks identical to in on a set, which is a single hash lookup — same syntax, completely different cost.
43. When should you not reach for a hash map?
Answer
When you need ordering, ranges, nearest-neighbour or min/max — use a balanced tree, a B-tree or a heap. Also when keys are few and small, where a plain array indexed directly is simpler and faster.
44. State the hash map’s trade in one sentence.
Answer
It buys lookup by any key, and pays with the entire notion of order — plus an average-case asterisk that an adversary can exploit.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Hash Maps & Hash Sets — the module
- Dynamic Arrays — Question Bank — where the same doubling/amortised argument appears
- Binary Search Trees — the ordered alternative
Software engineering
Infrastructure & security
Computer science
Hardware & engineering