Hashing and Hash Tables

Learning Objectives

By the end of this page, you should be able to:

Explain what a hash function does and list the properties a good one needs.
Compute a simple hash value using the division method and modulus.
Implement a hash table with chaining and with linear probing in Python.
Compare chaining, linear probing, quadratic probing, and double hashing.
Calculate load factor and explain when and why a hash table rehashes.
Analyze average-case and worst-case time complexity for insert, search, and delete.
Identify real-world systems (dictionaries, caches, deduplication) that rely on hashing.

Quick Answer

A hash table is a data structure that stores key-value pairs and gives you average O(1) insert, search, and delete. It works by running each key through a hash function, which converts it into an array index. The magic — and the risk — is that two different keys can map to the same index, called a collision. How you resolve collisions (chaining with linked lists, or open addressing with probing) determines real-world performance. Python's dict, database indexes, caches, and duplicate-detection systems all run on this idea. The catch: hash tables trade guaranteed speed for average-case speed — a bad hash function or a full table can degrade performance to O(n).

Why Hashing Exists

Arrays give you O(1) access only if you already know the index. Searching by value in an unsorted array is O(n); even a sorted array with binary search is O(log n). Hashing's whole purpose is to skip searching altogether — compute the index directly from the key. That's the trade you're making: you spend a little time computing a hash, and in exchange you get near-constant-time lookups regardless of how many items are stored.

Hash Functions

Definition

A hash function takes an input (the key — a string, number, or object) and deterministically produces a fixed-size integer, the hash value, which is then reduced (usually via modulus) to a valid index in the underlying array.

Explanation — what makes a hash function good

Deterministic — same input always produces the same output. Without this, you could insert a key and never find it again.
Uniform distribution — spreads keys evenly across the table so no single bucket gets overloaded.
Fast to compute — O(1) ideally; if hashing itself is slow, you've lost the whole point.
Fixed-size output — a "abc" and a 10,000-character string both compress to one integer.
Avalanche effect (for good general-purpose hashes) — a tiny change in input causes a large, unpredictable change in output, which helps distribution.

Note: for hashing used in hash tables (unlike cryptographic hashing), non-invertibility isn't a strict requirement — speed and distribution matter more.

Example

The division method is the simplest approach:

def hash_function(key, table_size):
    return key % table_size

hash_function(123, 10)   # 3
hash_function(456, 10)   # 6

For strings, Python converts characters to numbers first (e.g., summing ASCII/Unicode values or using polynomial hashing) before applying modulus.

Real-World Example

Python's built-in hash() function does exactly this under the hood for dict and set. When you write my_dict["apple"] = 10, Python hashes "apple", reduces it modulo the table's internal size, and stores the pair at that bucket.

Why It Matters

Every time you use a dict, HashMap, HashSet, or database index, a hash function is doing the heavy lifting. Choosing table sizes as prime numbers (rather than powers of two) is a common technique to reduce clustering when using the division method.

Common Misunderstanding

Students often think a hash function encrypts data. It doesn't — hashing for hash tables is about speed and distribution, not security. (Cryptographic hashes like SHA-256 are a specialized subset built for irreversibility and collision resistance, used in security contexts, not everyday hash tables.)

Hash Collisions

Definition

A collision happens when two different keys hash to the same index. Because the input space (all possible keys) is usually far larger than the table size, collisions are mathematically unavoidable — this is the pigeonhole principle in action.

Explanation

No hash function eliminates collisions entirely for arbitrary input. A well-designed hash table doesn't try to prevent all collisions; it just resolves them efficiently. There are two main families of resolution strategies:

1. Chaining (Separate Chaining)

Each array slot holds a linked list (or dynamic array) of all key-value pairs that hashed to that index.

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

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        self.table[index].append([key, value])

    def get(self, key):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        raise KeyError(key)

    def delete(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                del bucket[i]
                return
        raise KeyError(key)

ht = HashTableChaining()
ht.insert("apple", 10)
ht.insert("grape", 20)   # may collide with "apple" — no problem, both live in the same bucket list
print(ht.get("apple"))   # 10

2. Open Addressing

All entries live directly in the array itself — no linked lists. On a collision, the algorithm probes for the next open slot according to a fixed sequence.

Linear Probing: check (hash + 1) % size, then (hash + 2) % size, and so on. Simple, but prone to clustering — consecutive filled slots grow into large blocks that slow down future probes.
Quadratic Probing: check (hash + 1²) % size, (hash + 2²) % size, (hash + 3²) % size... Reduces primary clustering but can still cluster (secondary clustering) and may fail to find an empty slot even when one exists, depending on table size.
Double Hashing: use a second hash function to determine the probe step size: (hash1(key) + i * hash2(key)) % size. Gives the best distribution of the three because the probe sequence itself depends on the key.

class HashTableLinearProbing:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        for _ in range(self.size):
            if self.keys[index] is None or self.keys[index] == key:
                self.keys[index] = key
                self.values[index] = value
                return
            index = (index + 1) % self.size   # linear probe
        raise Exception("Hash table is full")

    def get(self, key):
        index = self._hash(key)
        for _ in range(self.size):
            if self.keys[index] == key:
                return self.values[index]
            if self.keys[index] is None:
                raise KeyError(key)
            index = (index + 1) % self.size
        raise KeyError(key)

ht = HashTableLinearProbing()
ht.insert("apple", 10)
ht.insert("grape", 20)
print(ht.get("grape"))   # 20

Deletion in open addressing is trickier than it looks: you can't just set a slot to None, because that would break the probe chain for keys stored after it. Implementations use a special "deleted" marker (a tombstone) instead of a true empty slot.

Real-World Example

Python's dict uses open addressing internally (a variant with pseudo-random probing), while Java's HashMap uses chaining (with a switch to balanced trees when a bucket gets too large, in modern versions). Both are legitimate, battle-tested designs — the choice reflects different trade-offs around memory locality and worst-case behavior.

Why It Matters

Interview questions constantly probe (pun intended) whether you understand why collisions happen and how each resolution strategy affects worst-case behavior. This is also the most commonly miscoded part of hash table implementations.

Common Misunderstanding

Students think collisions mean the hash function is "broken." They're not — collisions are expected and normal. A hash function's job is to make them rare and well-distributed, not to make them impossible.

Load Factor and Rehashing

Definition

Load factor (α) = number of stored entries ÷ table size. It measures how "full" the table is.

Explanation

As α grows, performance degrades:

In chaining, buckets grow longer, so lookups inside a bucket take longer.
In open addressing, probe sequences get longer as free slots become scarce, and once α approaches 1, insertion can fail entirely.

Most hash table implementations trigger rehashing once load factor crosses a threshold — commonly 0.7 for open addressing, or 1.0 for chaining. Rehashing:

Allocates a new, larger array (typically double the size, often rounded to a prime).
Recomputes the hash of every existing key against the new size (you can't just copy slots over — the modulus changed).
Reinserts all entries into the new table.

def rehash(self):
    old_table = self.table
    self.size *= 2
    self.table = [[] for _ in range(self.size)]
    for bucket in old_table:
        for key, value in bucket:
            self.insert(key, value)

Real-World Example

Python lists and dicts both over-allocate and resize by a growth factor when they get full, amortizing the cost of resizing across many insertions — the same principle behind hash table rehashing.

Why It Matters

Rehashing is what keeps average-case O(1) performance honest over the table's lifetime. Without it, a hash table that started small would slowly degrade into a glorified linked list.

Common Misunderstanding

Students assume resizing is free or instantaneous. A single rehash operation is O(n) — expensive — but because it happens rarely (only when doubling is triggered), the amortized cost per insertion stays O(1).

Hash Table Structure (Diagram)

This shows chaining: "apple" and "grape" collide at bucket 2, so both hang off the same linked list. "kiwi" and "mango" land in their own buckets with no collision.

Complexity Analysis

Operation	Chaining (Avg)	Chaining (Worst)	Open Addressing (Avg)	Open Addressing (Worst)
Insert	O(1)	O(n)	O(1)	O(n)
Search	O(1)	O(n)	O(1)	O(n)
Delete	O(1)	O(n)	O(1)	O(n)
Space	O(n)	O(n)	O(n) — fixed array	O(n)

The worst case (O(n)) happens when every key collides into the same bucket (chaining) or the probe sequence has to scan nearly the whole table (open addressing) — typically the result of a poor hash function or an overloaded table (high load factor).

Real-World Applications

Language dictionaries/maps: Python dict, Java HashMap, JavaScript Object/Map — all hash tables under the hood.
Caching: LRU caches and memoization tables use hash tables to check "have I computed this already?" in O(1).
Deduplication: checking if an item has been seen before (e.g., set() in Python, detecting duplicate transactions) is a direct hash table application.
Database indexing: hash indexes give O(1) equality lookups (though B-trees are preferred for range queries).
Password storage: cryptographic hashing (a specialized, security-focused sibling of general hashing) stores password hashes instead of raw passwords.

Key Terms

Term	Definition
Hash function	A function that maps a key to a fixed-size integer used as a table index.
Hash value / hash code	The integer output of a hash function.
Collision	When two distinct keys map to the same index.
Chaining	Collision resolution where each bucket holds a list of entries.
Open addressing	Collision resolution where all entries live directly in the array, found via probing.
Linear probing	Open addressing that checks the next slot sequentially on collision.
Quadratic probing	Open addressing that checks slots at increasing squared offsets.
Double hashing	Open addressing that uses a second hash function to set the probe step.
Load factor (α)	Ratio of stored entries to table size; measures fullness.
Rehashing	Resizing the table and reinserting all entries when load factor gets too high.
Tombstone	A marker left in place of a deleted entry in open addressing, to preserve probe chains.

Common Mistakes

Misconception	Why It's Wrong	Correct Understanding
"Hash tables guarantee O(1) lookups."	O(1) is the average case, assuming a good hash function and a controlled load factor. Worst case is O(n) when many keys collide.	Say "average O(1), worst-case O(n)." Interviewers specifically check whether you know this distinction.
"Deleting a slot in open addressing just means setting it to None/null."	This breaks the probe chain — a later lookup would stop searching at the empty slot and miss keys that were actually inserted further along the probe sequence.	Use a tombstone/deleted marker so searches keep probing past it, while insertions can reuse the slot.
"A collision means the hash function is bad."	Collisions are mathematically guaranteed once you have more possible keys than table slots (pigeonhole principle) — even a perfect hash function collides eventually.	A good hash function makes collisions rare and evenly distributed, not nonexistent. Judge a hash function by distribution quality, not by whether collisions occur at all.

Comparison and Connections

Aspect	Chaining	Open Addressing
Storage	Array of linked lists/arrays	Single flat array
Memory overhead	Extra pointers per node	None — more cache-friendly
Performance at high load factor	Degrades gracefully	Degrades sharply; can fail to insert
Deletion	Simple — remove from list	Needs tombstones
Cache locality	Poor (pointer chasing)	Better (contiguous array)
Used by	Java `HashMap`	Python `dict`

Aspect	Hash Table	Balanced BST / TreeMap
Average lookup	O(1)	O(log n)
Worst-case lookup	O(n)	O(log n) — guaranteed
Ordered iteration	No (arbitrary order)	Yes (sorted by key)
Range queries (e.g., "keys between 10 and 50")	Inefficient	Efficient
Best when	You need raw average speed and don't care about order	You need sorted order or guaranteed worst-case bounds

Practice Questions

Recall

What is a hash collision, and why is it mathematically unavoidable? Answer guidance: two different keys hashing to the same index; unavoidable because the key space is larger than the table size (pigeonhole principle).
Define load factor and give its formula. Answer guidance: α = number of entries ÷ table size; measures how full the table is.

Understanding

Explain why open addressing needs a tombstone marker for deletions but chaining does not. Answer guidance: in open addressing, setting a slot to empty breaks the probe sequence for later keys; chaining just removes a node from an independent list, so no other key's search path is affected.
Why is double hashing generally better distributed than linear probing? Answer guidance: linear probing's fixed +1 step creates primary clustering; double hashing's step size depends on the key itself via a second hash function, spreading probe sequences differently for different keys.

Application

You're building a cache that must check "have I seen this request before?" for millions of requests per second. Which data structure would you use and why? Answer guidance: a hash set/table — average O(1) membership checks scale far better than a list's O(n) scan.
You have a fixed-size hash table using linear probing at 90% load factor and insertions are slowing down noticeably. What's happening, and what should you do? Answer guidance: heavy clustering — long probe sequences are needed to find empty slots; trigger a rehash into a larger table to bring load factor back down (e.g., under 0.7).

Analysis

Compare chaining and open addressing for a system with strict memory constraints and unpredictable key counts. Which would you choose and why? Answer guidance: open addressing avoids pointer overhead (more memory-efficient per entry) but degrades badly if key counts spike unpredictably past capacity; chaining degrades more gracefully under unexpected load but costs more memory per entry. Discuss trade-offs rather than picking one "correct" answer.
A hash table implementation always uses table_size = 10. What problems could arise, and how would you fix them?
Answer guidance: fixed size means load factor climbs indefinitely as entries grow, degrading toward O(n); also 10 (non-prime) can worsen clustering for keys with common factors of 10. Fix: implement rehashing that grows the table (ideally to a prime size) once load factor crosses a threshold.

FAQ

Q: Is a hash table the same thing as a dictionary/map? A: "Hash table" is the underlying data structure; "dictionary" or "map" is often the higher-level abstract data type (a collection of key-value pairs) that's commonly implemented using a hash table — though it could also be implemented with a balanced BST.

Q: Why isn't hash table lookup always O(1)? A: O(1) assumes collisions are rare and the load factor is controlled. If many keys collide (bad hash function) or the table is nearly full, lookups can degrade to O(n) in the worst case.

Q: Can I use any object as a dictionary key in Python? A: Only hashable, immutable objects (strings, numbers, tuples of hashables). Lists and dicts aren't hashable because their contents — and thus their hash — could change after insertion, which would break the table.

Q: What's the difference between hashing for hash tables and cryptographic hashing (like SHA-256)? A: Hash-table hashing optimizes for speed and even distribution. Cryptographic hashing additionally requires that it be computationally infeasible to reverse the hash or find two inputs producing the same output — a much stronger, slower guarantee, used for security (passwords, digital signatures), not everyday lookups.

Q: Why do hash tables often use prime-sized arrays? A: Prime sizes reduce systematic clustering that can occur with the division method when keys share common factors with a composite table size (e.g., all even keys landing in even-indexed slots if the size is a power of two).

Q: How do modern languages handle a bucket that grows too large in chaining? A: Some (like Java's HashMap since Java 8) convert an overloaded bucket's linked list into a balanced tree once it passes a threshold, improving that bucket's worst case from O(n) to O(log n).

Quick Revision

Hash function: deterministic, fast, fixed-size output, uniform distribution.
Collisions are unavoidable (pigeonhole principle) — a good hash function just minimizes and spreads them.
Chaining = buckets hold lists; simple deletion; more memory overhead; degrades gracefully.
Open addressing = entries stored directly in the array; needs tombstones for deletion; better cache locality; degrades sharply near full.
Linear probing: +1, +2, +3... — simple but clusters.
Quadratic probing: +1², +2², +3²... — less clustering, may miss slots.
Double hashing: step size depends on a second hash function — best distribution.
Load factor α = entries / table size; controls when to rehash.
Rehashing: resize (usually double) + reinsert everything; O(n) per rehash but amortized O(1) per insert.
Average-case: O(1) for insert/search/delete. Worst-case: O(n).
Python dict uses open addressing; Java HashMap uses chaining (+ trees for large buckets).
Real uses: dictionaries/maps, caches, deduplication (set), database hash indexes.

Prerequisites

Arrays and array indexing
Linked lists (needed to understand chaining)
Big-O notation and time complexity basics

Related Topics

Sets and their relationship to hash tables
Binary search trees / balanced trees (TreeMap) as an ordered alternative
Bloom filters (a probabilistic hashing-based structure)

Next Topics

Trees and binary search trees
Graph representations (adjacency lists often use hash maps)
Dynamic programming with memoization (hash-table-backed caching)

Learning Objectives​

Quick Answer​

Why Hashing Exists​

Hash Functions​

Definition​

Explanation — what makes a hash function good​

Example​

Real-World Example​

Why It Matters​

Common Misunderstanding​

Hash Collisions​

Definition​

Explanation​

1. Chaining (Separate Chaining)​

2. Open Addressing​

Real-World Example​

Why It Matters​

Common Misunderstanding​

Load Factor and Rehashing​

Definition​

Explanation​

Real-World Example​

Why It Matters​

Common Misunderstanding​

Hash Table Structure (Diagram)​

Complexity Analysis​

Real-World Applications​

Key Terms​

Common Mistakes​

Comparison and Connections​

Practice Questions​

Recall​

Understanding​

Application​

Analysis​

FAQ​

Quick Revision​

Related Topics​

Learning Objectives

Quick Answer

Why Hashing Exists

Hash Functions

Definition

Explanation — what makes a hash function good

Example

Real-World Example

Why It Matters

Common Misunderstanding

Hash Collisions

Definition

Explanation

1. Chaining (Separate Chaining)

2. Open Addressing

Real-World Example

Why It Matters

Common Misunderstanding

Load Factor and Rehashing

Definition

Explanation

Real-World Example

Why It Matters

Common Misunderstanding

Hash Table Structure (Diagram)

Complexity Analysis

Real-World Applications

Key Terms

Common Mistakes

Comparison and Connections

Practice Questions

Recall

Understanding

Application

Analysis

FAQ

Quick Revision

Related Topics