Hash Tables Explained

A hash table is a data structure that stores key-value pairs and gives you near-instant lookup, insertion, and deletion by converting each key into a numeric index using a hash function. Instead of scanning through every item to find what you’re looking for, as you would with a list, a hash table jumps almost directly to where the value lives. Python’s built-in dict and set types are hash tables under the hood, which is why they’re the default choice whenever you need fast membership checks or key-based lookups. Understanding how they work under the hood, not just how to call them, is essential for writing efficient code and for answering interview questions about time complexity.

Overview: How Hash Tables Work

Picture a phone book with a million entries, sorted alphabetically. Finding one specific name means either scanning linearly (slow) or binary searching, which is O(log n) but still not instant. A hash table takes a completely different approach: instead of searching, it computes exactly where an entry should live. A hash function takes a key, such as the string \"apple\", and converts it into a number, the hash code. That number is then reduced to a valid array index, typically with hash(key) % capacity, where capacity is the current size of the underlying array of buckets. To insert a value, you compute the index and place the key-value pair directly into that bucket. To look it up later, you compute the exact same index and go straight there, no searching required. That’s the core trick: trade computation (running the hash function) for search (scanning memory).

Two things make this work well in practice. First, a good hash function distributes keys uniformly across buckets, so no single bucket gets overloaded. Second, the table keeps its load factor, the ratio of stored items to bucket count, low, typically resizing (allocating a bigger array and re-hashing everything into it) once the load factor crosses a threshold such as 0.75. A bigger array means fewer keys land in each bucket on average, which keeps operations fast.

Two different keys can still hash to the same index. This is a collision, and it’s unavoidable in general because there are infinitely many possible keys but only a finite number of buckets. Hash tables handle collisions in one of two main ways.

Separate Chaining

Each bucket holds a small list of every key-value pair that hashed to that index. On a collision, the new pair is simply appended to that bucket’s list. Lookups scan the, usually very short, list in the target bucket for a matching key. This is the strategy we build by hand in Example 2 below.

Open Addressing

Instead of a list per bucket, every bucket holds at most one entry. On a collision, the table probes forward, checking the next bucket according to some rule such as linear probing, quadratic probing, or double hashing, until it finds an empty slot. CPython’s actual dict implementation uses a form of open addressing internally, alongside metadata that tracks insertion order, which is why iterating over a dict yields keys in the order they were first inserted (guaranteed since Python 3.7), though insertion order is not the same as sorted order.

Whichever strategy is used, the key insight is the same: with a well-chosen hash function and a load factor kept low by resizing, the average bucket holds close to one item, so insert, lookup, and delete all take roughly constant time regardless of how many items are stored.

Time and Space Complexity

Operation	Average Case	Worst Case	Why
Insert	O(1)	O(n)	Computing a hash and placing into a bucket is constant time; the worst case happens when many keys collide into one bucket.
Lookup (in, [])	O(1)	O(n)	Computing the index is constant time; scanning a bucket’s chain is O(1) on average since chains stay short, but O(n) if every key collided into one bucket.
Delete	O(1)	O(n)	Same reasoning as lookup: the entry must be found before it can be removed.
Space	O(n)	O(n)	The table stores all n key-value pairs, plus some reserved empty capacity to keep the load factor low.

The worst case of O(n) happens when many keys collide into the same bucket. For example, if a poorly chosen hash function sent every key to bucket 0, the hash table would degrade into a plain linked list, and every lookup would have to scan all n entries. In practice this is rare, because Python’s built-in hash functions are designed to spread keys out well, and the interpreter automatically grows the underlying array (and re-hashes existing entries into it) as more items are added, keeping the load factor, and therefore the expected chain length, small and roughly constant. That resize itself costs O(n) when it happens, but because resizes happen exponentially less often as the table grows, the amortized cost per insertion stays O(1). Space complexity is O(n) because the table must store all n key-value pairs, plus a constant-factor amount of unused capacity to keep the load factor low.

Examples

Example 1: Counting Word Frequencies

The most common real-world use of a hash table is counting things. Python’s collections.Counter, itself a dict subclass, hashes each word to tally occurrences in a single pass:

from collections import Counter


def word_frequencies(text: str) -> dict[str, int]:
    words = text.lower().split()
    return dict(Counter(words))


def main() -> None:
    text = \"the quick brown fox jumps over the lazy dog the fox runs\"
    frequencies = word_frequencies(text)
    for word, count in frequencies.items():
        print(f\"{word}: {count}\")


main()

Output:

the: 3
quick: 1
brown: 1
fox: 2
jumps: 1
over: 1
lazy: 1
dog: 1
runs: 1

text.split() breaks the sentence into 12 words. Counter walks through them once, incrementing a count for each word the first time it’s seen and every time after. Because a Counter is a dict under the hood, each lookup and increment is O(1) average, so the whole function runs in O(n) time for n words. The word \"the\" appears at positions 0, 6, and 9, so it ends with count 3; \"fox\" appears twice; every other word appears once. The iteration order matches first-appearance order because dictionaries preserve insertion order.

Example 2: Building a Hash Table From Scratch

To see what dict does internally, here is a minimal hash table implemented with separate chaining, built manually so you can see the hashing and collision-handling logic that a real dictionary hides from you:

class HashTable:
    def __init__(self, capacity: int = 8) -> None:
        self.capacity = capacity
        self.size = 0
        self.buckets: list[list[tuple[str, int]]] = [[] for _ in range(capacity)]

    def _hash(self, key: str) -> int:
        return hash(key) % self.capacity

    def put(self, key: str, value: int) -> None:
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1

    def get(self, key: str) -> int:
        index = self._hash(key)
        bucket = self.buckets[index]
        for existing_key, existing_value in bucket:
            if existing_key == key:
                return existing_value
        raise KeyError(key)

    def __contains__(self, key: str) -> bool:
        index = self._hash(key)
        return any(existing_key == key for existing_key, _ in self.buckets[index])


def main() -> None:
    table = HashTable(capacity=4)
    table.put(\"apple\", 3)
    table.put(\"banana\", 5)
    table.put(\"cherry\", 7)
    table.put(\"apple\", 10)

    print(table.get(\"apple\"))
    print(table.get(\"banana\"))
    print(\"cherry\" in table)
    print(\"date\" in table)
    print(table.size)


main()

Output:

10
5
True
False
3

Three keys are inserted, then \"apple\" is inserted again with a new value. Because put scans its target bucket for an existing matching key before appending, the second \"apple\" insert overwrites the value in place (3 becomes 10) rather than creating a duplicate entry, and size stays at 3 rather than growing to 4. get(\"apple\") then returns 10, get(\"banana\") returns 5, \"cherry\" in table is True, \"date\" in table is False since it was never inserted, and table.size is 3.

Example 3: Two Sum With a Hash Map

A hash map turns many O(n squared) brute-force problems into O(n) ones by trading a nested loop for a single pass plus O(1) average lookups. The classic example is finding two numbers in a list that add up to a target:

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for index, number in enumerate(nums):
        complement = target - number
        if complement in seen:
            return [seen[complement], index]
        seen[number] = index
    return []


def main() -> None:
    nums = [2, 7, 11, 15, 3]
    target = 9
    print(two_sum(nums, target))

    nums2 = [3, 3]
    target2 = 6
    print(two_sum(nums2, target2))


main()

Output:

[0, 1]
[0, 1]

For the first call, at index 0 the number is 2, its complement is 7, and seen is empty, so 2 is recorded as seen = {2: 0}. At index 1 the number is 7 and its complement, 2, is already in seen, so the function immediately returns [0, 1] without ever looking further into the list. The second call shows this also works with duplicate values: at index 0, number 3 has complement 3, not yet seen, so seen = {3: 0}; at index 1, number 3 again has complement 3, which is now in seen, so it returns [0, 1]. Without the hash map this would require checking every pair, which is O(n squared).

How It Works Step by Step

To see collisions and chaining play out concretely, trace inserting three keys into a tiny hash table with capacity 4, using a simplified hash function that sums character codes (deliberately weak compared to a real hash function, but easy to compute by hand): hash(key) = sum(ord(c) for c in key) % 4.

1. Insert \”ab\” with value 1. Sum of character codes: 97 + 98 = 195. Index = 195 % 4 = 3. Bucket 3 is empty, so (\"ab\", 1) is appended there.
2. Insert \”ba\” with value 2. Sum: 98 + 97 = 195, the same total, since \”ab\” and \”ba\” are anagrams, which is exactly why a naive character-sum hash is a poor choice in real systems. Index = 195 % 4 = 3, a collision with \”ab\”. The table scans bucket 3, finds no key equal to \”ba\”, and appends it, so bucket 3 becomes [(\"ab\", 1), (\"ba\", 2)].
3. Insert \”cat\” with value 3. Sum: 99 + 97 + 116 = 312. Index = 312 % 4 = 0. Bucket 0 is empty, so (\"cat\", 3) goes there directly with no collision.
4. Look up \”ba\”. Recompute the index: 195 % 4 = 3. Scan bucket 3’s chain in order: (\"ab\", 1) doesn’t match, (\"ba\", 2) does, so 2 is returned. The cost of this lookup was proportional to the length of that one bucket’s chain (2 entries), not the size of the whole table.

This is exactly what HashTable.put and HashTable.get in Example 2 do, except they use Python’s built-in hash() function, which distributes keys far more evenly, and which Python randomizes per process for strings by default as a defense against hash-flooding denial-of-service attacks.

Common Mistakes

Mistake 1: Using a Mutable Object as a Dictionary Key

Dictionary keys must be hashable, which in practice means immutable. Lists are mutable, so Python refuses to hash them:

def track_positions() -> dict:
    positions = {}
    coord = [1, 2]
    positions[coord] = \"start\"
    return positions


track_positions()

Running this raises TypeError: unhashable type: 'list'. If a list were allowed as a key and later mutated, its hash would change, and the entry could become unreachable at its original bucket, silently corrupting the table. The fix is to use an immutable equivalent, such as a tuple, wherever the key is naturally a fixed-size collection of values:

def track_positions() -> dict[tuple[int, int], str]:
    positions: dict[tuple[int, int], str] = {}
    coord = (1, 2)
    positions[coord] = \"start\"
    return positions


def main() -> None:
    result = track_positions()
    print(result)


main()

Output:

{(1, 2): 'start'}

Mistake 2: Mutating a Dictionary While Iterating Over It

Deleting or adding keys while a for loop is iterating directly over the dictionary invalidates the iterator:

def remove_short_words(word_counts: dict) -> None:
    for word in word_counts:
        if len(word) < 4:
            del word_counts[word]


counts = {\"cat\": 1, \"elephant\": 2, \"dog\": 1, \"giraffe\": 3}
remove_short_words(counts)

This raises RuntimeError: dictionary changed size during iteration as soon as the first del runs. The fix is to iterate over a snapshot of the keys, such as list(word_counts.keys()), so the loop walks a separate list while the original dictionary is freely modified underneath it:

def remove_short_words(word_counts: dict[str, int]) -> None:
    for word in list(word_counts.keys()):
        if len(word) < 4:
            del word_counts[word]


def main() -> None:
    counts = {\"cat\": 1, \"elephant\": 2, \"dog\": 1, \"giraffe\": 3}
    remove_short_words(counts)
    print(counts)


main()

Output:

{'elephant': 2, 'giraffe': 3}

Best Practices

• Reach for a dict or set whenever you need fast membership tests or key-based lookup; checking x in some_set is O(1) average versus O(n) for x in some_list.
• Only use hashable, immutable types as dictionary keys or set members: strings, numbers, and tuples of hashable values work, while lists, dicts, and sets do not.
• Don’t rely on hash table iteration order to encode meaning beyond \”insertion order.\” If you need sorted output, call sorted() explicitly rather than assuming the dict is already in the order you want.
• Use collections.defaultdict when grouping or counting, to avoid writing manual \”if key not in dict\” checks.
• Use collections.Counter specifically for frequency counting; it reads clearly and has useful extras like most_common().
• When writing a custom __hash__ for a class, keep it consistent with __eq__. Two objects that compare equal must have the same hash, or dict and set lookups involving them will silently fail to find matches.
• Never mutate a dictionary’s keys, or a set’s members, while iterating directly over it; collect the changes separately or iterate over a copy instead.

Practice Exercises

1. Contains Duplicate. Given a list of integers, return True if any value appears at least twice, and False if every element is distinct. Aim for O(n) time using a set. Hint: for [1, 2, 3, 1] the expected result is True.

2. Group Anagrams. Given a list of strings, group the words that are anagrams of each other. Hint: use each word’s sorted-character tuple as a hash map key, since anagrams share the same sorted form. For [\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"], one valid grouping is [[\"eat\", \"tea\", \"ate\"], [\"tan\", \"nat\"], [\"bat\"]], though the order of groups and of words within a group may vary.

3. First Unique Character. Given a string, return the index of the first character that does not repeat anywhere else in the string, or -1 if none exists. Hint: a first pass with a Counter to tally frequencies, then a second pass to find the first character with count 1, keeps this at O(n). For \"leetcode\", the expected output is 0, the index of the letter \"l\".

Summary

• A hash table stores key-value pairs and uses a hash function to compute an array index directly from a key, avoiding the need to search.
• Collisions, where two keys hash to the same index, are handled with separate chaining (a list per bucket) or open addressing (probing for the next free slot); CPython’s dict uses a form of open addressing internally.
• Average-case time complexity for insert, lookup, and delete is O(1); worst case is O(n) when many keys collide into the same bucket.
• Space complexity is O(n), plus a constant-factor overhead reserved to keep the load factor low.
• Python’s dict and set are hash tables under the hood, and preserve insertion order since Python 3.7, but insertion order is not the same as sorted order.
• Only hashable, immutable types can be dictionary keys or set members; mutating a dict while iterating directly over it raises a RuntimeError.