The Hash Map Idea: Turn a Key Into an Address

"Arrays give you instant access — but only if you know the integer index. Hashing asks: what if ANY key — a name, a word, a tuple — could be its own index? That question is the whole structure."

The Dream

An array's arr[i] is O(1) because i tells you the address directly. But your keys are rarely tidy integers — they're usernames, words, IDs, coordinates. Searching a list for "is this username taken?" is O(n). What if you could turn the username itself into an array index and jump straight to its slot, just like arr[i]? That's the dream a hash map delivers.

The Trick: a Hash Function

A hash function takes any key and deterministically produces a number — its hash. Take that number modulo the table size and you get an array index. Now: to store a key, hash it to an index and drop it in that slot. To look it up, hash it again to the same index and read that slot. No searching — you computed exactly where it lives. Both operations are O(1) average: one hash computation plus one array access.

Underneath, a hash map is just an array. Hashing is the adapter that lets arbitrary keys behave like integer indices into that array. You already know why array access is instant (the address math from the Arrays track); hashing simply extends that gift from integers to everything hashable.

A hash map turns a key into an array index via a hash function, then uses the array's O(1) access. It's an array wearing an adapter that accepts any hashable key instead of only integers. Insert, look up, delete: all O(1) average.

You Use This Constantly

Python's dict and set are hash maps, and they are probably the most-used non-trivial data structure in all of programming. "Have I seen this before?" → a set. "What's the value for this key?" → a dict. "Count how many times each word appears?" → a dict. Every time you replaced an O(n) in list with an O(1) in set earlier in this quest, this is the machinery that made it instant. It's not an exotic structure to learn for interviews — it's the workhorse you'll reach for daily.

Pippa's Confession

Hash maps felt like cheating to me at first — how can finding something be free? Then Dad reframed it: "It's not finding. It's computing where you already put it." The map never searches; it recomputes the address. That one sentence turned the magic into mechanism. Now dict and set are the first tools I reach for, and 'can I make this lookup an O(1) hash instead of an O(n) scan?' is a reflex I run on almost every loop I write.

Code

A hash map from scratch (then just use dict)·python

# A tiny hash map from scratch, to demystify dict. (Use dict in real code!)
class TinyHashMap:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]   # each slot is a small list

    def _index(self, key):
        return hash(key) % self.size     # key -> number -> array index

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]      # jump straight to the slot
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value); return       # update existing
        bucket.append((key, value))                    # or insert new

    def get(self, key):
        bucket = self.buckets[self._index(key)]      # same key -> same slot
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

m = TinyHashMap()
m.put("pippa", 2024)
m.put("dad", 1)
print(m.get("pippa"))    # 2024 — no scan of all keys, we computed the slot
print(m.get("dad"))      # 1
# Real Python: just use {} — d = {"pippa": 2024}; d["pippa"].

Exercise

With a table of size 8 and the rule index = hash % 8, suppose hash('a')=17, hash('b')=8, hash('c')=25. Which slot does each land in? Do any collide? Then explain, in your own words, why looking up 'a' later doesn't require checking 'b' or 'c' at all.

Hint

17%8=1, 8%8=0, 25%8=1 — so 'a' and 'c' collide in slot 1. Lookup of 'a' recomputes 17%8=1 and only examines slot 1's little bucket; the other slots are never touched, which is the O(1).

The Dream

The Trick: a Hash Function

You Use This Constantly

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0