Data Structures: Hash Tables — The Most Useful Structure You'll Ever Use

Post #3 covered arrays’ genuinely fast index access — array[5] jumps straight to a memory address, no searching required. But what if you do not want to look something up by a numeric position at all — what if you want to look it up by a name, a word, a user ID? This is exactly the problem hash tables solve, and they solve it so well that they have become arguably the single most-used data structure in all of modern software, hiding in plain sight behind names like “dictionary,” “map,” and “object.”

The Core Idea: A Function That Turns Any Key Into an Array Index

A hash table’s genuine insight: use a hash function to convert an arbitrary key — a string, a number, anything — into a number, then use that number as an index into a plain array, exactly the O(1) direct-access structure covered in Post #3.

def simple_hash(key: str, table_size: int) -> int:
    """A genuinely simplified hash function, for illustration only."""
    total = sum(ord(char) for char in key)
    return total % table_size

print(simple_hash("apple", 10))   # some number between 0 and 9
print(simple_hash("banana", 10))   # a different number between 0 and 9

Store "apple"’s associated value at the array index the hash function computes for "apple". To retrieve it later, run "apple" through the exact same hash function again, get the exact same index back, and go directly there — no searching required, exactly the same direct-access speed arrays provide, now applied to arbitrary keys instead of only sequential numeric positions.

Collisions: When Two Keys Hash to the Same Index

Any hash function mapping a large space of possible keys down to a small array will eventually produce the same index for two different keys — this is called a collision, and it is not a bug or a rare edge case; it is a mathematical certainty for any hash table that stores more items than its underlying array has slots.

Handling Collisions With Chaining

The most common approach: instead of storing a single value at each array index, store a small list (a chain) of every key-value pair that happens to hash to that index.

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return sum(ord(c) for c in str(key)) % self.size

    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # update existing key
                return
        bucket.append((key, value))  # add new key-value pair

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)


table = SimpleHashTable()
table.put("apple", 1.50)
table.put("banana", 0.75)
print(table.get("apple"))  # 1.50

When a collision occurs, the lookup checks each entry in that specific bucket’s small chain until it finds the matching key — still fast in practice, because a well-designed hash function spreads keys evenly enough that any individual chain stays short, close to a single item on average.

Why This Achieves O(1) Average-Case Access

With a good hash function spreading keys evenly across the underlying array, each bucket holds only a small, roughly constant number of entries regardless of how many total items are stored — meaning both storing and retrieving a value take, on average, a constant amount of time, independent of the hash table’s total size. This “average case,” and the important caveat that it is not a guaranteed worst case, gets full, precise treatment once Post #7 formally covers Big O notation — for now, the intuition (spread keys evenly, keep chains short, get near-instant access) is the genuinely important takeaway.

Python’s dict Has Been a Hash Table This Entire Time

Every dictionary used throughout this blog’s Python series — every task = {"description": "...", "completed": False} — is, underneath, exactly the structure covered in this post.

task = {"description": "Learn hash tables", "completed": False, "priority": "high"}

print(task["description"])  # near-instant — Python hashes "description", jumps to that bucket

This is precisely why dictionary access is O(1) average case, a fact this blog’s Python series stated directly without explaining the underlying mechanism — now you understand exactly what makes it true, rather than accepting it as an unexplained rule.

Real-World Use Cases

Deduplication: Checking whether a value has already been seen — exactly the set-based deduplication pattern covered in this blog’s Python series — relies on the same hash-based O(1) membership testing covered in this post.

Caching: Storing previously computed results keyed by their inputs, so a repeated request retrieves the cached result instantly instead of recomputing — the memoization pattern covered elsewhere on this blog is a hash table application directly.

Database indexing: A database index, covered fully once Post #14 addresses databases directly, frequently uses a hash-table-like structure (among other options) to make looking up rows by a specific column value dramatically faster than scanning every row.

Counting and grouping: Any “count occurrences of each distinct value” task — word frequency counting, vote tallying — relies directly on a hash table’s fast, key-based access to maintain a running count per distinct key.

Common Mistakes and Gotchas

⚠️ Mistake 1: Assuming hash table access is guaranteed O(1), not just average-case In a genuinely pathological scenario — a poor hash function, or specially crafted input designed to force collisions — a hash table’s worst-case performance degrades toward the chain-search cost, potentially O(n). Real hash table implementations, including Python’s, include safeguards against this, but understanding that “average case” and “worst case” are different guarantees matters for genuinely performance-critical or security-sensitive code.

⚠️ Mistake 2: Using a mutable object as a dictionary key

bad_key = [1, 2, 3]
my_dict = {bad_key: "value"}  # TypeError: unhashable type: 'list'

This is not an arbitrary restriction — a hash table needs a key’s hash value to remain constant for as long as it is stored, and a mutable object’s contents (and therefore its hash) could change after insertion, breaking the entire lookup mechanism; this is precisely why Python requires dictionary keys to be hashable (immutable) types.

⚠️ Mistake 3: Writing a poor custom hash function that clusters keys unevenly The simple_hash example in this post, summing character codes, is deliberately simplified for illustration — a genuinely poor hash function can cause far more collisions than a well-designed one for the same data, degrading the average-case performance this post relies on; production hash table implementations use carefully designed hash functions specifically to avoid this.

⚠️ Mistake 4: Assuming hash tables preserve any meaningful ordering Historically, hash tables offered no ordering guarantee at all — Python dictionaries have specifically guaranteed insertion order since 3.7 (covered in this blog’s Python series), which is a deliberate language design choice layered on top of the underlying hash table mechanism, not an inherent property of hash tables generally across every language and implementation.

Quick Reference

# Python's dict IS a hash table
d = {}
d["key"] = "value"       # O(1) average — hash "key", store at that index
value = d["key"]           # O(1) average — hash "key" again, look up directly
"key" in d                  # O(1) average — same mechanism, membership check

# Python's set is also hash-table-based
s = {1, 2, 3}
4 in s                       # O(1) average

# Manual hash table structure
buckets = [[] for _ in range(size)]  # array of chains, handling collisions
index = hash_function(key) % size      # map key to an array position

Exercises

Exercise 1 — Direct application Extend the SimpleHashTable class from this post with a delete(key) method that removes a key-value pair from the correct bucket.

Exercise 2 — Slight variation Write a function first_duplicate(items: list) -> any that uses a hash-based structure (a Python set or dict) to find the first value that appears more than once in a list, in a single pass through the list.

Exercise 3 — Real-world combination Using only the SimpleHashTable class from this post (not Python’s built-in dict), implement a word frequency counter that reads a string of text and counts how many times each word appears.

Exercise 4 — Open-ended challenge Deliberately write a “bad” hash function that maps every possible key to the same single index, use it with the SimpleHashTable class, and observe how lookup performance degrades as more items are added — connecting the result directly to this post’s coverage of worst-case behavior.

FAQ

Q: What’s the actual difference between a hash table, a dictionary, and a map? A: These terms are largely interchangeable across different programming languages and contexts — “hash table” describes the underlying implementation covered in this post, while “dictionary” (Python), “map” (many other languages), and “object” (JavaScript, covered in this blog’s JavaScript series) are language-specific names for data types built on top of that same underlying mechanism.

Q: How does Python actually hash a string internally? A: Python uses a considerably more sophisticated hash function than this post’s simplified illustration, designed specifically to spread keys evenly and resist adversarial inputs — the exact algorithm is an implementation detail beyond this introductory post’s scope, but the fundamental idea (deterministically map a key to a number) is identical to what’s covered here.

Q: Why can’t I use a list as a dictionary key, but I can use a tuple? A: Directly covered above — lists are mutable (their contents can change after creation), while tuples are immutable, exactly the hashability requirement this post explains; a tuple’s contents, and therefore its hash value, cannot change after creation, satisfying the requirement a mutable list cannot.

Q: Is a hash table always the right choice when I need fast lookups? A: For lookups by an arbitrary key (a name, an ID, any non-sequential identifier), yes, almost always. For lookups requiring sorted order or range queries (“find all values between X and Y”), the tree structures covered in Post #5 are frequently the better-suited choice instead — the right structure depends on what operations you actually need to be fast.

Summary and Next Steps

You now understand exactly how a hash table achieves its signature near-instant, average-case access — a hash function converting arbitrary keys into array indices, with chaining to handle the inevitable collisions — and why Python’s dictionary, used throughout this blog’s Python series, has been built on precisely this mechanism the entire time. This is very likely the single most practically useful data structure covered in this entire series, given how constantly it appears across virtually every category of real software.

Your next step: Complete Exercise 4 — deliberately breaking your own hash table with a bad hash function — since watching performance genuinely degrade as collisions pile up is the clearest possible demonstration of why hash function quality matters, not just the existence of a hash function at all.

Last updated: August 2026.