Python Hash Tables

A hash table is a data structure that maps keys to values by using a hash function to compute an index into an array of storage slots, called buckets. Python does not expose a raw “HashTable” type in the standard library because you already use hash tables constantly — the built-in dict and set types are both hash tables under the hood. Understanding how they work internally explains why lookups are so fast, why dict keys must be immutable, and why you occasionally hit surprising bugs with custom objects.

Overview / How Hash Tables Work

The core idea of a hash table is simple: instead of searching through every element to find a key (as you would with a list, which takes O(n) time), you compute a number from the key using a hash function, and that number tells you almost exactly where to look. In theory this makes lookup, insertion, and deletion all average O(1) — constant time, regardless of how many items are stored.

Here is what actually happens when you do my_dict["apple"] = 3 in CPython:

• Python calls hash("apple"), which returns a large integer (positive or negative) that summarizes the key.
• That integer is reduced modulo the current table size (using bitwise masking, not the % operator, for speed) to get a bucket index, called a slot.
• Python checks the slot. If it’s empty, the key-value pair is stored there.
• If the slot is already occupied by a different key (a collision), CPython uses an algorithm called open addressing with a pseudo-random probing sequence to find the next candidate slot, repeating until an empty one is found.
• If the slot holds the same key (checked with == after confirming the hashes match), the existing value is overwritten.

Lookup (my_dict["apple"]) follows the identical path: hash the key, jump to the slot, and if there’s a collision, follow the same probing sequence until the matching key is found or an empty slot proves the key isn’t present.

Why keys must be hashable

This design only works if a key’s hash value never changes while it’s stored in the table — otherwise the table wouldn’t know which bucket to search. That’s why Python requires dict keys and set elements to be hashable, and by convention hashable objects should also be immutable. Built-in immutable types like str, int, float, bool, and tuple (of hashable items) are hashable. Mutable built-ins — list, dict, set — are explicitly unhashable so you can’t accidentally corrupt a table by mutating a key after insertion.

Why dicts remember insertion order

Since Python 3.7, dicts also maintain insertion order as a language guarantee. CPython achieves this with a clever two-array design: a sparse array of indices (the actual hash table) and a dense array holding the real key-value entries in insertion order. The hash table only stores integers pointing into the dense array, which is both memory-efficient and order-preserving. set objects do not make this guarantee — their iteration order is an implementation detail driven purely by hash values and table layout.

Syntax

You don’t construct a “hash table” directly — you use dict or set, and Python’s built-in hash() function tells you the value it will use internally:

hash(object)

my_dict = {key1: value1, key2: value2}
my_set = {item1, item2}

• hash(object) — returns the integer hash of any hashable object; raises TypeError if the object is unhashable.
• {key: value, ...} — dict literal; each key must be hashable, values can be anything.
• {item, ...} — set literal; every element must be hashable.
• Custom classes are hashable by default (using their id()), until you define __eq__, which disables the default __hash__ unless you define your own.

Average vs. worst-case complexity

Operation	list	dict / set (average)	dict / set (worst case)
Lookup by key/value	O(n)	O(1)	O(n)
Insert	O(1) append / O(n) elsewhere	O(1)	O(n)
Delete	O(n)	O(1)	O(n)

The worst case only shows up under pathological hash collisions, which is why Python randomizes string hashing per process (see the Common Mistakes section) — it prevents attackers from crafting keys designed to force worst-case behavior in web applications.

Examples

Example 1: A word-frequency counter with a dict

This is the most common real-world use of a hash table — counting occurrences by using each unique item as a key:

word_counts = {}
text = "the quick brown fox jumps over the lazy dog the fox runs"

for word in text.split():
    word_counts[word] = word_counts.get(word, 0) + 1

for word, count in sorted(word_counts.items()):
    print(f"{word}: {count}")

Output:

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

Every call to word_counts.get(word, 0) is a hash table lookup: Python hashes the string word, jumps straight to its bucket, and either finds the running count or falls back to 0. Even with a much longer text, each update stays roughly constant-time.

Example 2: Making a custom object hashable

To use your own class as a dict key or set member, you must implement both __eq__ and __hash__ consistently — two objects that compare equal must produce the same hash:

class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))

    def __repr__(self):
        return f"Point({self.x}, {self.y})"

points = {Point(0, 0), Point(1, 1), Point(0, 0)}
print(len(points))
print(sorted(points, key=lambda p: (p.x, p.y)))

visited: dict[Point, str] = {}
visited[Point(3, 4)] = "checkpoint A"
print(visited[Point(3, 4)])

Output:

2
[Point(0, 0), Point(1, 1)]
checkpoint A

Even though Point(0, 0) is created twice as two separate objects, the set collapses them into one entry because they hash identically and compare equal. The trick used here — delegating to hash((self.x, self.y)) — is the standard, safe way to hash a composite object: tuples are hashable as long as every element inside them is hashable.

Example 3: Building a tiny hash table from scratch

To really see the mechanism, here is a minimal hash table implemented with separate chaining (a list of buckets, each holding a small list of key-value pairs):

class SimpleHashTable:
    def __init__(self, capacity: int = 8):
        self.capacity = capacity
        self.buckets: list[list[tuple[str, int]]] = [[] for _ in range(capacity)]

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

    def put(self, key: str, value: int) -> None:
        index = self._index(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))

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

table = SimpleHashTable()
table.put("apples", 10)
table.put("bananas", 5)
table.put("apples", 12)

print(table.get("apples"))
print(table.get("bananas"))

Output:

12
5

_index hashes the key and reduces it modulo the table’s capacity, exactly like the real dict does internally (though CPython uses bit masking and much more sophisticated probing). Notice that inserting "apples" twice updates the existing entry rather than creating a duplicate, because put scans the bucket for a matching key before appending — this is exactly how collisions are resolved with separate chaining.

Under the Hood: Step by Step

• Step 1 – Hash. Python calls __hash__ on the key, producing a large signed integer. For strings and bytes, this hash is randomized per process using a secret seed (PEP 456), so hash("apple") differs between separate runs of your program.
• Step 2 – Mask to a slot. The hash is combined with the table’s size (always a power of two) using a bitmask to pick an initial slot index.
• Step 3 – Probe on collision. If that slot is taken by a different key, CPython computes a new candidate slot using a pseudo-random probing sequence derived from the hash, and repeats until it finds either the matching key or an empty slot.
• Step 4 – Compare. A matching hash doesn’t guarantee a matching key (different objects can share a hash — a true collision), so Python always double-checks with == before declaring a match.
• Step 5 – Resize. When the table gets about two-thirds full, CPython allocates a larger underlying array and re-inserts every entry. This keeps the average chain length short, which is what keeps operations close to O(1) even as the table grows.

Common Mistakes

Mistake 1: Using a mutable object as a dict key

Lists are unhashable, so this raises a TypeError:

cache = {}
cache[[1, 2, 3]] = "invalid key"

Result: TypeError: unhashable type: 'list'. Lists can change after creation, so Python refuses to let them be keys — if you mutated the list later, the hash table would have no way to relocate the entry to its new bucket. Use an immutable tuple instead:

cache = {}
cache[(1, 2, 3)] = "valid key"
print(cache[(1, 2, 3)])

Output:

valid key

Mistake 2: Defining __eq__ without __hash__

When you override __eq__ on a class, Python automatically sets __hash__ to None unless you define it yourself — because two objects that compare equal are now required to hash equally, and Python can’t guarantee that without your help:

class BadPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

points = {BadPoint(1, 2)}

Result: TypeError: unhashable type: 'BadPoint'. The fix is exactly what Example 2 showed — add a __hash__ method that’s consistent with __eq__, typically by hashing a tuple of the same fields used for comparison.

Mistake 3: Assuming set/dict iteration order reflects hash order

Because of collision resolution and resizing, the physical slot order has nothing to do with any meaningful ordering. Dicts preserve insertion order (a separate guarantee since 3.7), but sets guarantee no order at all — never write code that depends on the order elements come out of a set.

Best Practices

• Prefer dict.get(key, default) or collections.defaultdict over checking if key in dict and then indexing — it avoids a second hash lookup.
• Keep dict keys as simple immutable types (str, int, tuple) whenever possible; reserve custom hashable classes for when the key genuinely needs structure.
• When you implement __hash__ on a custom class, base it only on the same fields used in __eq__, and never on mutable attributes that can change after the object is stored.
• Don’t rely on hash() values being stable across different runs of your program for strings, bytes, or datetime objects — hash randomization means they will differ.
• Use set for fast membership testing (x in my_set) instead of x in my_list when the collection is large or checked repeatedly — it turns an O(n) scan into an O(1) average lookup.
• For counting, prefer collections.Counter over hand-rolled dict counting logic — it’s a dict subclass built exactly for this and reads more clearly.

Practice Exercises

• Exercise 1: Write a function first_duplicate(items: list[int]) -> int | None that returns the first value that appears twice in a list, using a set to track values seen so far in a single pass. Return None if there are no duplicates.
• Exercise 2: Create a class Currency with code (e.g. "USD") and country attributes. Implement __eq__ and __hash__ so that two Currency instances with the same code are treated as equal and hash identically, regardless of country. Verify by putting several into a set and checking the resulting length.
• Exercise 3: Extend the SimpleHashTable class from Example 3 with a __len__ method that returns the total number of stored key-value pairs across all buckets, and a delete(key) method that removes an entry (raising KeyError if the key isn’t found).

Summary

• A hash table maps keys to values by hashing each key into a bucket index, giving average O(1) lookup, insertion, and deletion.
• Python’s dict and set are both built on hash tables; dict additionally preserves insertion order via a separate dense array.
• Keys and set elements must be hashable; built-in mutable types like list, dict, and set are intentionally unhashable.
• Collisions are resolved internally via open addressing with probing; your own hash table can use simpler approaches like separate chaining.
• Custom classes need matching __eq__ and __hash__ implementations to behave correctly as dict keys or set members.
• String and bytes hashing is randomized per process for security, so never assume a specific hash value or iteration order across runs.