A hash table is a data structure that maps keys to values by applying a hash function to each key to compute a bucket index, providing O(1) average-case lookup, insertion, and deletion at the cost of O(n) worst-case when collisions are uncontrolled.
A hash table is a structure that turns a key (like a name) into a number (via a hash function), uses that number to find a slot in an array, and stores the value there — giving nearly instant lookup by key.
The hash function
A hash function maps a key to a non-negative integer. That integer, taken modulo the table's capacity, gives a bucket index. For key "Alice" with capacity 16: hash("Alice") → 74929384, 74929384 % 16 = 8. The value for "Alice" is stored in bucket 8. Looking up "Alice" later: same computation, same bucket — O(1).
# Python dict is a hash table
user = {
"Alice": {"age": 30, "city": "Mumbai"},
"Bob": {"age": 25, "city": "Delhi"},
}
# O(1) average lookup
print(user["Alice"]["city"]) # Mumbai
# O(1) average insert
user["Carol"] = {"age": 28, "city": "Pune"}
# O(1) average delete
del user["Bob"]
# O(1) membership test
print("Alice" in user) # True
print("Bob" in user) # FalseComplexity table
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Search (lookup) | O(1) | O(n) | Worst case: all keys collide |
| Insert | O(1) | O(n) | Amortised; worst on rehash |
| Delete | O(1) | O(n) | Amortised |
| Space | O(n) | O(n) | Plus wasted capacity for load factor |
Average case assumes a good hash function and load factor <0.75.
Collisions
Two different keys may hash to the same bucket — a collision. Collision resolution strategies: chaining — each bucket holds a linked list of all entries that hash there; lookup scans the list. Open addressing — on collision, probe other buckets in a deterministic sequence until an empty slot is found. Python uses open addressing with pseudo-random probing. Java's HashMap uses chaining (each bucket holds a linked list; converted to a balanced tree when list length exceeds 8).
When to use a hash table
When you need O(1) lookup by a key that isn't an integer index. Counting word frequencies, caching computed results, symbol tables in compilers, database indexes, and any application needing fast key-value access all use hash tables.
Load factor and rehashing
Load factor α = n/m where n is the number of stored entries and m is the table capacity. High load factor means more collisions. Python resizes when α > 0.67 (2/3); Java HashMap resizes at α = 0.75. On resize: allocate a new table (typically 2× capacity), reinsert all existing entries using the new modulus — O(n) work. Amortised over all operations: O(1) per operation.
Hash function quality
A good hash function produces values that distribute keys uniformly across buckets. The requirements: (1) same input always produces same output; (2) x == y ⇒ hash(x) == hash(y); (3) collisions are rare. Python's built-in hash uses SipHash-1-3 for strings (since Python 3.4, PEP 456) — a keyed hash seeded per-process to prevent HashDoS attacks. Java's String.hashCode() uses the Horner polynomial: h = 31⋅h + char[i].
// Java String.hashCode() — Horner polynomial
// hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
String s = "Alice";
int h = 0;
for (char c : s.toCharArray()) {
h = 31 * h + c;
}
// h overflows int (intentional — Java arithmetic wraps mod 2^32)
System.out.println(h == s.hashCode()); // trueOpen addressing: linear, quadratic, double hashing
Linear probing: on collision at slot i, try i+1, i+2, …. Simple, cache-friendly, but causes primary clustering (long runs form and grow). Quadratic probing: try i+1, i+4, i+9, … Reduces clustering but may not probe all slots if capacity is not prime. Double hashing: step size = hash2(key); try i, i+step, i+2⋅step, …. Best distribution. Python uses a pseudo-random probe sequence derived from the hash value.
Universal and perfect hashing
Universal hashing (Carter & Wegman, 1979): choose a hash function randomly from a family where, for any two distinct keys x, y, Pr[h(x) = h(y)] ≤ 1/m (m = table size). This makes the expected number of collisions O(1) per key regardless of input distribution. Perfect hashing: for a static set of n keys, construct a hash function with zero collisions — O(1) worst-case lookup. FKS hashing (Fredman, Komlós, Szemerédi, 1984) achieves this with O(n) space.
Java HashMap treeification
Java 8+ HashMap uses a technique called treeification: when a single bucket's chain length exceeds 8 entries, the chain is converted from a linked list to a balanced Red-Black tree — reducing worst-case bucket lookup from O(n) to O(log n). When the count drops below 6, it converts back to a linked list. This guarantees O(log n) worst case even with many collisions. Specified in java.util.HashMap javadoc and the HashMap source code (jdk.java.net).
Cormen, T. H. et al. (2022). CLRS (4th ed.), Chapter 11 — Hash Tables. Carter, J. L. & Wegman, M. N. (1979). "Universal classes of hash functions." JCSS 18(2). Python SipHash: PEP 456. Java HashMap treeification: JDK source code openjdk.org.