Hash Tables

At a theatre coat check, you hand over your coat and get ticket 37. When you come back, the attendant does not search every hook in the room. They read your ticket and walk straight to hook 37.

An array works like that, but only when the "ticket" is a small whole number. Most of the time you want to look things up by something else: a username, a word, a product code. A hash table is a way to give any key its own ticket number, so you can find it just as fast.

#From key to bucket

A hash table is an array of buckets. To decide where a key goes, you run it through a hash function: a recipe that turns the key into a whole number. The same key always gives the same number. Then you take that number modulo the bucket count, so it fits the array.

Here is a simple, deliberately weak hash function for strings: add up the character codes. For "owl": o is 111, w is 119, l is 108, total 338. With 5 buckets, 338 % 5 = 3. So "owl" lives in bucket 3, and every later lookup of "owl" goes straight there.

#Collisions, and why they are fine

There are endless possible keys and only 5 buckets, so two keys will sometimes land in the same bucket. That is a collision. "ant" sums to 323, and 323 % 5 is also 3.

The common fix is called chaining: each bucket holds a short list of [key, value] pairs. To look up a key, hash it, go to its bucket, and compare keys along that short list until you find a match or reach the end. Step through a small table that stores how many of each animal a zoo has.

b = (sum of char codes of key) % 5set: if key is in buckets[b]: update it     else: add [key, value] to buckets[b]get: for each [k, v] in buckets[b]:       if k == key: return v     return not found

Here is that table as code. Real languages use a far better hash function, but the structure is the same.

class TinyMap {
  constructor(size = 5) {
    this.buckets = Array.from({ length: size }, () => []);
  }
  bucketFor(key) {
    let sum = 0;
    for (const ch of key) sum += ch.charCodeAt(0); // weak hash, for teaching
    return this.buckets[sum % this.buckets.length];
  }
  set(key, value) {
    const bucket = this.bucketFor(key);
    for (const pair of bucket) {
      if (pair[0] === key) { pair[1] = value; return; } // update
    }
    bucket.push([key, value]); // new key: add to the chain
  }
  get(key) {
    for (const [k, v] of this.bucketFor(key)) {
      if (k === key) return v;
    }
    return undefined; // not found
  }
}

class TinyMap:
    def __init__(self, size=5):
        self.buckets = [[] for _ in range(size)]
 
    def bucket_for(self, key):
        total = sum(ord(ch) for ch in key)  # weak hash, for teaching
        return self.buckets[total % len(self.buckets)]
 
    def set(self, key, value):
        bucket = self.bucket_for(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value  # update
                return
        bucket.append([key, value])  # new key: add to the chain
 
    def get(self, key):
        for k, v in self.bucket_for(key):
            if k == key:
                return v
        return None  # not found

#Keeping the chains short

Lookups are fast only while chains stay short. Two things make sure they do.

A good hash function spreads keys evenly. Adding character codes is weak: "cat" and "act" have the same letters, so they always collide. Real hash functions mix every bit of the key, so similar keys land in unrelated buckets.

The table grows. The load factor is entries divided by buckets. When it passes a limit, such as 0.75, the table makes about twice as many buckets and re-inserts every entry, because % bucketCount now gives different answers. That costs O(n) once, but like a growing array it happens rarely enough that inserts stay O(1) on average.

With both in place, a chain holds about one entry on average, whatever the size of the table. So get, set and delete are O(1) on average. In the worst case, if every key lands in one bucket, a lookup walks all n entries: O(n).

#Turning O(n²) into O(n)

You do not usually write your own hash table. JavaScript has Map and Set; Python has dict and set. The skill is noticing when to reach for one.

Say you want to count how often each word appears in a list. The direct approach takes each word and scans the whole list to count it. That is a loop inside a loop, O(n²). With a map, you walk the list once and bump a counter for each word.

function countWords(words) {
  const counts = new Map();
  for (const word of words) {
    counts.set(word, (counts.get(word) ?? 0) + 1); // O(1) on average
  }
  return counts;
}
 
countWords(["red", "blue", "red", "green", "blue", "red"]);
// Map { "red" => 3, "blue" => 2, "green" => 1 }

def count_words(words):
    counts = {}
    for word in words:
        counts[word] = counts.get(word, 0) + 1  # O(1) on average
    return counts
 
count_words(["red", "blue", "red", "green", "blue", "red"])
# {'red': 3, 'blue': 2, 'green': 1}

The pattern is general. Whenever an inner loop exists only to search for something, such as "have I seen this?", "how many of these so far?" or "where is the partner for this value?", a map can remember the answer instead. One pass, and each question costs O(1). You pay for it with O(n) extra memory.

#Common mistakes

#Check yourself

#What to practise next

Solve Matching Receipts: the obvious answer checks every pair, and a map finds each partner in one step. When the data is sorted, you can often skip the map and its memory with Two Pointers.