Hash tables are, without exaggeration, one of the data structures I reach for the most in everyday programming. Whenever I need fast lookups by key — a dictionary, a cache, a set of unique items — a hash table is almost always my first instinct. What I find fascinating about them is how they trade a small amount of theoretical worst-case guarantee for extremely fast average-case performance, achieving expected $O(1)$ time for search, insertion, and deletion, something no comparison-based structure like a binary search tree can match.
I want to walk through not just how to use a hash table, but how it actually works underneath: how keys get mapped to positions in an array, what happens when two keys collide, and why the choice of hash function matters so much for performance in practice.
History and Background
Hashing as a technique dates back to the early 1950s. Hans Peter Luhn, a researcher at IBM, is often credited with proposing the core idea of hashing in an internal IBM memo around 1953, aiming to speed up search in symbol tables. The term “hashing” itself and further formalization came through subsequent work by researchers including Arnold Dumey, who discussed the idea in a 1956 paper on computer indexing.
Collision resolution techniques, including both chaining and open addressing, were developed and refined through the 1960s, with significant contributions by researchers publishing in the Communications of the ACM and other venues of that era. Universal hashing, which provides strong theoretical guarantees against adversarial inputs, was introduced by J. Lawrence Carter and Mark N. Wegman in their 1979 paper “Universal Classes of Hash Functions,” a major theoretical advance that underlies much of the rigorous analysis used in modern textbook treatments.
Problem Statement
I want to implement a dictionary (also called an associative array or symbol table): a data structure supporting INSERT, SEARCH, and DELETE operations on a dynamic set of key-value pairs, ideally all in $O(1)$ expected time, regardless of how large the set of possible keys is. A direct-address table (an array indexed directly by key) achieves $O(1)$ worst-case time, but only works when the universe of possible keys is small enough to allocate an array of that size — which is rarely practical, since keys might be strings, large integers, or other complex objects.
Core Concepts
- Universe of keys ($U$): The set of all possible keys that could occur, often much larger than the number of keys actually stored.
- Hash function ($h$): A function $h: U \rightarrow {0, 1, \dots, m-1}$ that maps a key to a slot index in a table of size $m$.
- Collision: When two distinct keys $k_1 \ne k_2$ map to the same slot, i.e., $h(k_1) = h(k_2)$.
- Load factor ($\alpha$): Defined as $\alpha = n / m$, where $n$ is the number of stored elements and $m$ is the number of slots; this ratio strongly influences performance.
- Chaining: A collision-resolution strategy where each slot holds a linked list of all elements hashing to that slot.
- Open addressing: A collision-resolution strategy where, on a collision, the algorithm probes a sequence of alternative slots within the same array until it finds an empty (or matching) one.
- Simple uniform hashing (assumption): An idealized assumption that any given key is equally likely to hash to any of the $m$ slots, independent of where other keys hash — used to simplify average-case analysis.
- Universal hashing: A technique where the hash function itself is chosen randomly from a carefully designed family of functions at runtime, guaranteeing good average performance even against adversarially chosen input keys.
How It Works
When I insert a key-value pair, I compute h(key) to get a slot index, and then place the pair at that slot. If chaining is used, I simply add the pair to the front (or end) of the linked list stored at that slot — collisions are handled gracefully since multiple entries can coexist in the same slot’s list. If open addressing is used, and the computed slot is already occupied by a different key, I compute an alternative probe position using a probe sequence, and repeat until I find an empty slot.
Searching for a key follows the same process: compute h(key), then either scan the linked list at that slot (chaining) or follow the same probe sequence used during insertion (open addressing) until I find the key or conclusively determine it’s absent (an empty slot, in the case of open addressing, signals the key isn’t present, assuming careful handling of deletions).
Deletion under chaining is simple — I find the node in the appropriate list and unlink it. Deletion under open addressing is trickier, because simply emptying a slot could break the probe sequence for other keys that were placed after a collision; this is typically handled by marking slots as “deleted” (a tombstone) rather than truly empty, so that searches continue to probe past them correctly.
Working Principle
The reason hash tables achieve such fast average performance is rooted in the simple uniform hashing assumption: if a good hash function spreads keys roughly evenly across the $m$ slots, then the expected number of keys per slot is the load factor $\alpha = n/m$. As long as $m$ is kept proportional to $n$ (i.e., $\alpha = O(1)$), the expected work per operation stays constant.
The internal mechanism differs meaningfully between the two collision-resolution strategies. Chaining essentially degrades gracefully — even under a bad hash function, correctness is never at risk, only speed, since a linked-list scan will always eventually find the key if it’s present. Open addressing is more delicate: the entire table’s occupied slots and empty slots must be consistent with the deterministic probe sequences used, and this interdependency is what makes deletion and dynamic resizing require extra care.
Mathematical Foundation
Expected search time in chaining, under simple uniform hashing. For a hash table with $m$ slots and $n$ stored keys using chaining, the expected length of a linked list at any slot is:
$$ \alpha = \frac{n}{m} $$
For an unsuccessful search (the key is not present), the expected number of elements examined is exactly $\alpha$, since the expected chain length is $\alpha$ and every element in that chain must be examined to confirm absence:
$$ E[\text{unsuccessful search}] = \Theta(1 + \alpha) $$
For a successful search, the expected number of elements examined is:
$$ E[\text{successful search}] = \Theta\left(1 + \frac{\alpha}{2}\right) = \Theta(1 + \alpha) $$
The $+1$ term accounts for the constant time needed to compute the hash function itself, which is independent of $\alpha$. If $m$ is chosen proportional to $n$, then $\alpha = O(1)$, giving expected $O(1)$ time per operation.
Open addressing probe sequence. The hash function is extended to include a probe number $i$:
$$ h(k, i) : U \times {0, 1, \dots, m-1} \rightarrow {0, 1, \dots, m-1} $$
For linear probing with an auxiliary hash function $h’$:
$$ h(k, i) = (h'(k) + i) \bmod m $$
For double hashing, using two auxiliary hash functions $h_1$ and $h_2$:
$$ h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m $$
Expected number of probes under uniform hashing (open addressing). For an unsuccessful search with load factor $\alpha < 1$:
$$ E[\text{probes, unsuccessful}] \le \frac{1}{1 – \alpha} $$
For a successful search:
$$ E[\text{probes, successful}] \le \frac{1}{\alpha} \ln\left(\frac{1}{1 – \alpha}\right) $$
These formulas show clearly why open addressing performance degrades sharply as $\alpha$ approaches 1 — the denominator $1 – \alpha$ shrinks toward zero, causing the expected probe count to blow up.
Diagrams
flowchart TD
A[Key k arrives for insert/search] --> B[Compute slot index using h of k]
B --> C{Slot occupied?}
C -->|No| D[Place key here - chaining: new list node
open addressing: store directly]
C -->|Yes, chaining| E[Append/search within linked list at that slot]
C -->|Yes, open addressing| F[Compute next probe using h of k, i+1]
F --> CPseudocode
Chained hash table:
CHAINED-HASH-INSERT(T, x)
insert x at the head of list T[h(x.key)]
CHAINED-HASH-SEARCH(T, k)
search for an element with key k in list T[h(k)]
CHAINED-HASH-DELETE(T, x)
delete x from the list T[h(x.key)]
Open-addressing hash table:
HASH-INSERT(T, k)
i = 0
repeat
j = h(k, i)
if T[j] == NIL or T[j] == DELETED
T[j] = k
return j
i = i + 1
until i == m
error "hash table overflow"
HASH-SEARCH(T, k)
i = 0
repeat
j = h(k, i)
if T[j] == k
return j
i = i + 1
until T[j] == NIL or i == m
return NIL
Step-by-Step Example
Let me trace chained hashing with a table of size $m = 7$ and the simple hash function $h(k) = k \bmod 7$. I insert keys 10, 22, 31, 4, 15, 28 in that order.
10: $10 \bmod 7 = 3$ → slot 3 gets10.22: $22 \bmod 7 = 1$ → slot 1 gets22.31: $31 \bmod 7 = 3$ → collision at slot 3!31is added to the front of slot 3’s list, which now holds31 -> 10.4: $4 \bmod 7 = 4$ → slot 4 gets4.15: $15 \bmod 7 = 1$ → collision at slot 1! Slot 1’s list becomes15 -> 22.28: $28 \bmod 7 = 0$ → slot 0 gets28.
Final table:
Slot 0: 28
Slot 1: 15 -> 22
Slot 2: (empty)
Slot 3: 31 -> 10
Slot 4: 4
Slot 5: (empty)
Slot 6: (empty)
If I now search for 31, I compute $h(31) = 3$, go to slot 3’s list, and find 31 at the front — a fast, one-comparison search. If I search for 100, I compute $h(100) = 2$, find slot 2 empty, and correctly conclude 100 isn’t in the table.
Time Complexity
- Chaining, expected case ($\alpha = O(1)$): $O(1)$ for search, insertion, and deletion.
- Chaining, worst case: $O(n)$, if all $n$ keys happen to hash to the same slot (a pathologically bad hash function or adversarial input).
- Open addressing, expected case: $O(1)$ for search and insertion when $\alpha$ is bounded away from 1, though the constant factor grows as $\alpha$ increases, per the formulas above.
- Open addressing, worst case: $O(n)$, similarly, in pathological cases, or when the table is nearly full ($\alpha$ close to 1).
- Dynamic table resizing (rehashing): Using a doubling strategy when $\alpha$ exceeds a threshold gives amortized $O(1)$ time per insertion, even accounting for the occasional $O(n)$-time resize operation.
Space Complexity
A chained hash table uses $\Theta(n + m)$ space: $\Theta(m)$ for the array of slot headers, and $\Theta(n)$ for the actual stored elements distributed across the linked lists. An open-addressing hash table uses $\Theta(m)$ space total, since all elements are stored directly within the array itself with no extra linked-list overhead — this is one of open addressing’s practical advantages when memory efficiency matters, though it requires $m \ge n$ always, whereas chaining can technically handle $\alpha > 1$ (at a performance cost).
Correctness Analysis
For chaining, correctness is straightforward: since every key that hashes to a given slot is guaranteed to be somewhere in that slot’s linked list, a full scan of the list will always correctly find the key if present, or correctly conclude its absence if the list is exhausted without a match.
For open addressing, correctness depends critically on the probe sequence being a genuine permutation of ${0, 1, \dots, m-1}$ for each key — meaning that as $i$ ranges from 0 to $m-1$, $h(k, i)$ visits every slot in the table exactly once. This guarantees that if there’s an empty slot anywhere in the table, the insertion algorithm will eventually find it. Search correctness in open addressing crucially depends on this same guarantee, plus correct handling of deletions: if a naive deletion sets a slot back to genuinely empty (NIL) rather than using a “deleted” tombstone marker, a subsequent search might incorrectly stop probing early at that empty slot and wrongly report a key as absent even though it exists further along the original probe sequence.
Advantages
- Expected $O(1)$ time for search, insertion, and deletion, which is asymptotically better than the $O(\lg n)$ guaranteed by balanced trees.
- Simple conceptually and often simple to implement, especially the chaining variant.
- Naturally supports arbitrary key types (strings, tuples, objects) as long as a reasonable hash function is defined for them.
- Open addressing variants can be extremely memory-efficient since they avoid pointer overhead from linked lists.
Disadvantages
- No guaranteed worst-case performance — a poorly chosen hash function, or an adversary who knows the hash function, can force $O(n)$ behavior on every operation.
- Doesn’t naturally support ordered operations like finding the minimum, maximum, or iterating in sorted order — for that, a balanced tree is a better choice.
- Requires careful tuning of load factor and resizing strategy to maintain good performance as the table grows or shrinks.
- Open addressing’s deletion complexity (needing tombstones) and sensitivity to high load factors make it trickier to implement correctly than chaining.
Applications
- Implementing dictionaries, maps, and sets in essentially every major programming language’s standard library (Python’s
dict, Java’sHashMap, C++’sunordered_map). - Caching systems, where fast key-based lookup is essential (e.g., memoization tables, web caches, CPU cache-line lookup structures).
- Database indexing for equality lookups (though B-trees are preferred when range queries matter).
- Symbol tables in compilers and interpreters, associating variable names with their storage locations or values.
- Detecting duplicates or counting frequency of items efficiently in data processing pipelines.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 7
typedef struct HashNode {
int key;
int value;
struct HashNode* next;
} HashNode;
typedef struct {
HashNode* buckets[TABLE_SIZE];
} HashTable;
void initTable(HashTable* table) {
for (int i = 0; i < TABLE_SIZE; i++) {
table->buckets[i] = NULL;
}
}
/* A simple hash function: key mod table size. In production code,
I would use a stronger hash function to spread keys more evenly. */
int hashFunction(int key) {
return key % TABLE_SIZE;
}
void insert(HashTable* table, int key, int value) {
int index = hashFunction(key);
/* Check whether the key already exists, and update it if so */
HashNode* current = table->buckets[index];
while (current != NULL) {
if (current->key == key) {
current->value = value;
return;
}
current = current->next;
}
/* Otherwise, insert a new node at the head of the chain */
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table->buckets[index];
table->buckets[index] = newNode;
}
int search(HashTable* table, int key, int* found) {
int index = hashFunction(key);
HashNode* current = table->buckets[index];
while (current != NULL) {
if (current->key == key) {
*found = 1;
return current->value;
}
current = current->next;
}
*found = 0;
return -1;
}
void deleteKey(HashTable* table, int key) {
int index = hashFunction(key);
HashNode* current = table->buckets[index];
HashNode* prev = NULL;
while (current != NULL) {
if (current->key == key) {
if (prev == NULL) {
table->buckets[index] = current->next;
} else {
prev->next = current->next;
}
free(current);
return;
}
prev = current;
current = current->next;
}
}
void printTable(HashTable* table) {
for (int i = 0; i < TABLE_SIZE; i++) {
printf("Slot %d: ", i);
HashNode* current = table->buckets[i];
while (current != NULL) {
printf("(%d,%d) -> ", current->key, current->value);
current = current->next;
}
printf("NULL\n");
}
}
int main(void) {
HashTable table;
initTable(&table);
int keys[] = {10, 22, 31, 4, 15, 28};
int n = sizeof(keys) / sizeof(keys[0]);
for (int i = 0; i < n; i++) {
insert(&table, keys[i], keys[i] * 100); /* store key*100 as a sample value */
}
printf("Hash table contents:\n");
printTable(&table);
int found;
int value = search(&table, 31, &found);
printf("\nSearch for key 31: %s (value=%d)\n", found ? "Found" : "Not found", value);
deleteKey(&table, 31);
printf("\nHash table after deleting key 31:\n");
printTable(&table);
return 0;
}
I want to point out that insert here checks for an existing key first and updates its value rather than blindly adding a duplicate node — this mirrors how most real dictionary implementations behave, where inserting an already-present key updates it rather than creating a second entry.
Sample Input and Output
Input:
Insert keys (with value = key*100): 10, 22, 31, 4, 15, 28
Search for key: 31
Delete key: 31
Output:
Hash table contents:
Slot 0: (28,2800) -> NULL
Slot 1: (15,1500) -> (22,2200) -> NULL
Slot 2: NULL
Slot 3: (31,3100) -> (10,1000) -> NULL
Slot 4: (4,400) -> NULL
Slot 5: NULL
Slot 6: NULL
Search for key 31: Found (value=3100)
Hash table after deleting key 31:
Slot 0: (28,2800) -> NULL
Slot 1: (15,1500) -> (22,2200) -> NULL
Slot 2: NULL
Slot 3: (10,1000) -> NULL
Slot 4: (4,400) -> NULL
Slot 5: NULL
Slot 6: NULL
This matches my hand-traced example precisely, and shows the deletion correctly unlinking 31 while leaving 10 (which shared the same slot) intact.
Optimization Techniques
- Choosing a strong hash function: Techniques like the multiplication method, or using well-tested hash functions like MurmurHash or FNV for strings, spread keys much more evenly than a naive modulo operation, especially for non-random or patterned keys.
- Dynamic resizing (rehashing): Growing (or shrinking) the table and rehashing all elements when the load factor crosses a threshold (commonly $\alpha > 0.75$ for growing) keeps performance close to $O(1)$ amortized, even as the number of elements changes significantly over time.
- Universal hashing: Randomly selecting the hash function from a well-designed family at runtime protects against adversarial inputs specifically crafted to cause worst-case collisions.
- Using prime table sizes: For simple modulo-based hash functions, choosing $m$ to be a prime number (not close to a power of 2) tends to reduce clustering caused by patterns in the input keys.
- Robin Hood hashing / other advanced open-addressing variants: These techniques reduce the variance in probe lengths across the table, improving worst-case-ish behavior in practice compared to plain linear or quadratic probing.
Common Mistakes
- Using a naive or poor hash function, such as simply using the first character of a string, which causes massive clustering and defeats the purpose of hashing entirely.
- Forgetting to handle load factor growth, leading to performance degrading silently over time as more elements are inserted into a fixed-size table.
- Incorrect deletion in open addressing, specifically clearing a slot to truly empty instead of using a tombstone, which breaks the probe-sequence invariant that search relies on.
- Off-by-one or modulo errors when computing hash indices, especially when combining multiple hash components (as in double hashing), leading to indices outside the valid table range or improper wraparound.
- Not checking for duplicate keys during insertion, which either silently allows duplicates (in a structure meant to be a dictionary) or fails to update existing values correctly.
- Memory leaks in C implementations, especially forgetting to free chained nodes during table destruction or during a delete operation.
Further Reading
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Chapter 11: “Hash Tables,” MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Carter, J. Lawrence, and Mark N. Wegman, “Universal Classes of Hash Functions,” Journal of Computer and System Sciences (1979): https://www.sciencedirect.com/science/article/pii/0022000079900448
- Knuth, Donald E., The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- MIT OpenCourseWare, “Table Doubling, Karp-Rabin”: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- GeeksforGeeks, “Hashing Data Structure”: https://www.geeksforgeeks.org/dsa/hashing-data-structure/
