Straight to the right page
Hash Maps as Dictionaries
The analogy
To find "otter" in a dictionary you do not start at page 1 — the word itself tells you roughly where to go. A hash map does the same trick with maths: it turns the key into a page number, then looks only at that page.
Visualizer
Straight to the page
step 1 / 15[0]
[1]
[2]
[3]
[4]
[5]
[6]
7 empty pages. Nothing is sorted, and we will never scan looking for a key.0 entries in 7 pages — load factor 0.00
📖 In depth — the full reference
Hash map operations
| operation | average | worst | note |
|---|---|---|---|
| get(key) | O(1) | O(n) | worst = every key colliding; real hash functions make this astronomically unlikely |
| set(key, v) | O(1) | O(n) | occasional O(n) resize, amortized away |
| delete(key) | O(1) | O(n) | |
| contains key? | O(1) | O(n) | the duplicate-check superpower from m0l9 |
| iterate all | O(n) | O(n) | order: insertion order in Python 3.7+ and JS Map |
| min/max/range | O(n) | O(n) | hashing destroys order — a BST gives you this instead |
dict — the details that bite
- Keys must be hashable: str, int, float, bool, tuple-of-hashables. A list or dict as a key raises TypeError — freeze it into a tuple first.
- d[k] on a missing key raises KeyError; d.get(k) returns None; d.get(k, default) returns your fallback; d.setdefault(k, []).append(x) builds grouped lists in one line.
- Insertion order is GUARANTEED (Python 3.7+) — iterating a dict replays the story of how it was built.
- set is a dict without values: `x in s` is the same O(1) machinery. collections.Counter and defaultdict are dicts with superpowers.
- Since strings hash randomly per process (security), never rely on hash(x) being stable across runs.
See it yourself
ages = {"ada": 36, "bo": 7}
print(ages.get("cy")) # None — no crash
ages.setdefault("cy", 0) # insert-if-missing
print("ada" in ages) # True — O(1)
from collections import Counter
print(Counter("mississippi").most_common(2)) # [('i', 4), ('s', 4)]def my_hash(key, n_buckets):
total = 0
for ch in key:
total += ord(ch)
return total % n_buckets
d = {"cat": 1, "dog": 2}
d["dog"] # straight to the bucket — O(1)Check yourself
Average lookup cost in a well-sized hash map?
Practice — write it yourself
bucket_of(key, n) — the hash from the lesson: sum the character codes (ord(ch)), take % n. Pure arithmetic, no searching.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser