DevPath
Tracks

Hash Tables

How a hash function turns keys into array slots, what collisions and load factor mean, and how to build a table with chaining.

beginner45 min#hash-table#hashing#collisions#load-factor#dictionary

Prerequisites: Arrays and Dynamic Arrays, Linked Lists

Why it matters

The hash table is the most useful structure in everyday programming: Python's dict and set, JavaScript's Map, Set and objects, database indexes, caches and symbol tables are all built on it. In interviews it is the standard tool for turning an O(n^2) "compare every pair" idea into O(n) by remembering what you have already seen.

Intuition

Imagine a wall of numbered mailboxes. You do not search for a person's mailbox; you apply a rule to their name that always yields a box number, then walk straight to it. That rule is the hash function. Because the rule is deterministic, the same key always lands in the same box, so lookup does not depend on how many people are registered.

The catch: there are far more possible names than boxes, so two names will sometimes map to the same box. That is a collision, and every hash table needs a plan for it.

How it works

  1. Hash function: converts a key to an integer. A good one is fast, deterministic, and spreads keys evenly. Equal keys must produce equal hashes.
  2. Index: hash(key) % number_of_buckets picks a slot in an underlying array.
  3. Collision handling:
    • Chaining: each slot holds a small list of key-value pairs. A lookup hashes, then scans that one short list.
    • Open addressing: every pair lives directly in the array. On a collision you probe other slots (next slot, or by a formula) until you find a free one. Deleting needs tombstone markers so probe sequences do not break.
  4. Load factor: items / buckets. As it grows, collisions multiply and chains get longer. When it crosses a threshold (commonly 0.75 for chaining, lower for open addressing), the table allocates about twice as many buckets and rehashes every item, because each index depends on the bucket count. Like a dynamic array, this makes insertion amortized O(1).

The path from a key to its slot is always the same three stages. Here it is for the key banana with the table from the code below, which starts with 4 buckets.

keybanana
hash functiondjb2-style: 4086421542
% 4 buckets4086421542 % 4 = 2
bucket 2scan its short chain
Lookup cost does not depend on how many keys are stored: hash, take the remainder, then scan one short chain.
buckets (4)         hash("fig") % 4 = 1  and  hash("date") % 4 = 1  -> collision
  0: []
  1: [fig:3] -> [date:4]          chaining: both live in bucket 1's list
  2: []
  3: [apple:5]

Now watch the lesson's table (4 buckets, chaining) receive its first four words, using the same hash as the code. The grid shows one row per bucket, with the chain reading left to right.

chain 1chain 2
0
1
2
3
An empty table with 4 buckets.
step 1 / 6

Collisions are handled by chaining, and growing the table (rehashing) spreads the chains out again.

The same thing happens later in the lesson's run. Before grape arrives, 8 buckets hold 6 words and date and fig share bucket 3.

0
elder
1
cherry
2
date, fig
3
4
5
banana
6
apple
7
8 buckets, 6 items: load factor 0.75, which does not exceed the limit. Bucket 3 holds the chain date, fig.
step 1 / 3

Load factor is items divided by buckets. Crossing the threshold triggers a one-time O(n) rehash that keeps chains short.

Keys must be hashable and stable. If a key's contents change after insertion, its hash changes and the table can no longer find it. That is why Python lists cannot be dict keys while tuples can, and why JavaScript objects used as Map keys are compared by reference, not by contents.

Worst case. If all keys collide, one chain holds everything and lookup degrades to O(n). Real libraries defend against that with good hash functions, resizing, randomized seeds (Python randomizes string hashes per process), and in some cases converting long chains into balanced trees. Note that hash iteration order is not sorted; if you need sorted keys, use a tree or sort afterwards.

OperationTimeNotes
Insert / updateO(1) averageAmortized, includes occasional rehash
Lookup / membershipO(1) averageHash, then scan a short chain
DeleteO(1) averageTombstone needed in open addressing
Any operation, worst caseO(n)All keys collide
Iterate all itemsO(n + buckets)Order is not sorted
SpaceO(n)Extra empty buckets for a low load factor

Code: a hash table with chaining

Python randomizes its built-in string hash on every run, so this example uses a small deterministic hash (a djb2-style multiply-and-add) to make the output reproducible.

def hash_str(s):
    h = 5381
    for ch in s:
        h = (h * 33 + ord(ch)) % 2**32  # deterministic djb2-style hash
    return h
 
 
class HashTable:
    def __init__(self):
        self._buckets = [[] for _ in range(4)]
        self._size = 0
 
    def __len__(self):
        return self._size
 
    def _bucket(self, key):
        return self._buckets[hash_str(key) % len(self._buckets)]
 
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value  # update existing key
                return
        bucket.append([key, value])
        self._size += 1
        if self._size / len(self._buckets) > 0.75:  # load factor limit
            self._grow()
 
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
 
    def delete(self, key):
        bucket = self._bucket(key)
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket.pop(i)
                self._size -= 1
                return True
        return False
 
    def _grow(self):
        old = self._buckets
        self._buckets = [[] for _ in range(len(old) * 2)]
        for bucket in old:
            for k, v in bucket:  # rehash: positions depend on table size
                self._buckets[hash_str(k) % len(self._buckets)].append([k, v])
 
    def stats(self):
        longest = max(len(b) for b in self._buckets)
        return len(self._buckets), longest
 
 
t = HashTable()
for word in ["apple", "banana", "cherry", "date", "elder", "fig", "grape"]:
    t.put(word, len(word))
t.put("fig", 30)
print(len(t), t.get("fig"), t.get("kiwi", "missing"))
print(t.delete("date"), t.delete("date"), len(t))
print(t.stats())
 
counts = {}
for w in "to be or not to be".split():
    counts[w] = counts.get(w, 0) + 1
print(counts)

Both versions print:

7 30 missing
True False 6
(16, 1)
{'to': 2, 'be': 2, 'or': 1, 'not': 1}

Reading the output: 7 distinct words were stored and fig was updated to 30 rather than duplicated. After a delete the size is 6. The table started with 4 buckets and doubled twice (4 to 8 to 16) as the load factor crossed 0.75, and the longest chain at the end has length 1. The final line is the classic word-count idiom using the built-in dictionary.

Common pitfalls

  • Assuming O(1) is guaranteed: it is an average. Adversarial or badly distributed keys can make it O(n).
  • Mutating a key after insertion: the item is stranded in the wrong bucket and can never be found.
  • Relying on order: Python dicts keep insertion order and JavaScript Maps do too, but that is a feature of those libraries, not of hashing in general.
  • Forgetting that equal keys need equal hashes: if you define your own equality, define a matching hash.
  • Floats and objects as keys: 0.1 + 0.2 is not equal to 0.3, and object keys in JavaScript plain objects are turned into strings, so 1 and "1" collide. Prefer Map when key types matter.
  • Hashing inside a loop of n^2: building a set once outside the loop is usually the whole optimization.

Practice

Two Sum (unsorted) easy

Hint

For each number, what other number would complete the target? Have you seen it already?

Show solution

Keep a map from value to index. For each x at index i, check whether target - x is in the map; if so return that index and i. Otherwise store x. One pass, O(n) time, O(n) space.

Group anagrams medium

Hint

You need a key that is identical for all anagrams of a word.

Show solution

Use the sorted letters of each word (or a tuple of 26 letter counts) as the key and append the word to that key's list. Sorting costs O(k log k) per word of length k; counting costs O(k). Overall O(n * k) with the counting key.

Longest consecutive sequence medium

Hint

Put everything in a set. Which numbers are the start of a run?

Show solution

Add all numbers to a set. For each number x with x - 1 not in the set, count upward while x + 1, x + 2, ... are present. Each run is walked only from its start, so total work is O(n) even though there is a nested loop.

Open addressing with deletion hard

Hint

If you simply empty a slot on delete, what happens to a key that was placed after it in a probe sequence?

Show solution

With linear probing, a lookup stops at the first empty slot. Emptying a deleted slot would cut the probe path and hide later keys. Mark the slot as a tombstone instead: lookups continue past it, inserts may reuse it. Count tombstones toward the load factor and rebuild the table when they pile up.

Interview questions

  1. How does a hash table achieve O(1) lookup? It converts the key into an array index, so it does not search; collisions are kept short by a good hash and by resizing at a load factor limit.
  2. What is a collision and how can you handle it? Two keys map to the same bucket. Chaining stores a list per bucket; open addressing probes for another free slot.
  3. Why does the table resize, and what does it cost? To keep chains short. Rehashing all items is O(n), but it is rare, so insertion is amortized O(1).
  4. Hash table vs balanced tree? Hash tables are faster on average for exact lookup; trees keep keys sorted and give O(log n) worst case, plus range queries.

Interviewers look for: reaching for a map or set to trade space for time, stating average versus worst case, and knowing why keys must be immutable.

Quick check

A chaining hash table has 8 buckets and 6 items. Its load factor is 0.75 and the resize threshold is 0.75 (resize when above it). You insert one more item. What happens?

Finished this lesson?

Further resources

Related lessons