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
  1. Hash the key: hash("apple") → a large integer.
  2. Reduce to an index: integer % capacity → e.g. bucket 5.
  3. 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
  1. Allocate a new bucket array with double the capacity.
  2. Re-hash every existing key into it.
  3. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Data Structures — University-Style Teaching Notes