Hash Tables Explained: How Dictionaries and Sets Work

A hash table stores key-value pairs and finds a key in O(1) time on average, whatever the size. Python's dict and set are hash tables, and they are the most useful tool in DSA for turning slow solutions into fast ones.

The idea: turn a key into an index#

Arrays give O(1) access by index. A hash table makes any key behave like an index:

1. A hash function turns the key into a big integer.
2. That integer modulo the number of buckets picks a slot.
3. The value is stored in that slot.

buckets = 8
for key in ["apple", "banana", "cherry"]:
    h = sum(ord(c) for c in key)          # a very simple hash function
    print(f"{key:>7}: hash {h}, bucket {h % buckets}")

  apple: hash 530, bucket 2
 banana: hash 609, bucket 1
 cherry: hash 653, bucket 5

Real hash functions mix the bits much better than adding character codes, so similar keys spread out evenly. Python's hash() for strings is also randomised each time Python starts, for security, so its exact values change from run to run.

Collisions#

Two different keys can land in the same bucket: a collision. The simplest fix is chaining: each bucket holds a small list of pairs.

class HashMap:
    def __init__(self, buckets=4):
        self.buckets = [[] for _ in range(buckets)]
        self.count = 0

    def _bucket(self, key):
        return self.buckets[sum(ord(c) for c in key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:          # existing key: update it
                pair[1] = value
                return
        bucket.append([key, value])
        self.count += 1
        if self.count / len(self.buckets) > 0.75:
            self._resize()

    def get(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        raise KeyError(key)

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        self.count = 0
        for k, v in old:
            self.put(k, v)

m = HashMap()
for word, n in [("cat", 3), ("dog", 5), ("act", 7), ("bird", 2)]:
    m.put(word, n)
print(m.get("cat"), m.get("act"), m.get("bird"))
print("buckets:", len(m.buckets))
print([b for b in m.buckets if b])

3 7 2
buckets: 8
[[['cat', 3], ['act', 7]], [['bird', 2]], [['dog', 5]]]

"cat" and "act" have the same letters, so this simple hash always puts them in the same bucket; chaining keeps both. Python's real dict uses a different collision strategy (open addressing: try another slot), but the guarantees are the same.

Load factor and resizing#

The load factor is items ÷ buckets. As it grows, buckets get longer and lookups slow down. So a hash table resizes (here at 0.75), moving everything into twice as many buckets. Like a dynamic array, the occasional O(n) resize keeps the average cost of each insert at O(1).

The worst case needs a terrible hash function or deliberately chosen keys, which is why real hash functions are carefully designed.

What can be a key?#

Keys must be hashable: their hash must never change. Numbers, strings and tuples of those work; lists and dicts do not, because they can be modified after being stored.

seen = {(1, 2): "point"}
print(seen[(1, 2)])
try:
    bad = {[1, 2]: "list"}
except TypeError as e:
    print("Error:", e)

point
Error: unhashable type: 'list'

The classic: Two Sum#

Given a list of numbers and a target, return the indexes of two numbers that add up to the target.

Checking every pair is O(n²). With a dictionary that remembers each number's index, one pass is enough: for each number, ask "have I already seen target - number?"

def two_sum(nums, target):
    index_of = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in index_of:
            return index_of[need], i
        index_of[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([1, 2, 3], 7))

(0, 1)
(1, 2)
None

O(n) time and O(n) space: the time-memory trade-off at its best.

Grouping with a hash map#

Grouping words that are anagrams of each other: anagrams have the same sorted letters, so use those as the key.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Common mistakes#

Practice#

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:          # x starts a run
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))
print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))
print(longest_consecutive([]))

4
9
0

Key takeaway#

Next: a pattern that needs no extra memory at all, Two Pointers.