Hashing and hash functions
Hash tables deliver average O(1) insertion, deletion, and lookup by turning keys directly into array positions. Everything depends on a good hash function.
The idea
If keys were small integers, we could store each item at array index equal to its key: a direct-address table with O(1) operations. Real keys, such as names, URLs, or large numbers, come from huge universes. A hash function maps each key to an index in a much smaller array of m buckets, so table[h(key)] can be found in constant time.
What makes a good hash function
A good hash function is deterministic (the same key always gives the same index), fast to compute, and spreads keys evenly and seemingly randomly across buckets, so similar keys such as "user1" and "user2" land far apart. Uneven spreading causes many keys to pile into a few buckets, destroying performance.
Hashing integers
The division method uses h(k) = k mod m; it works best when m is a prime not close to a power of 2, because patterns in keys, such as all being even, would otherwise cluster. The multiplication method multiplies k by a constant, keeps the fractional part, and scales it by m, and is less sensitive to m's value.
Hashing strings
Strings are hashed by combining their characters, typically with a polynomial: h = (c0 x p^(n-1) + c1 x p^(n-2) + ... + c(n-1)) mod m, computed efficiently by Horner's rule, h = h x p + c for each character. Java's String.hashCode uses p = 31. Simply adding character codes is poor because anagrams such as "listen" and "silent" collide.
Collisions are inevitable
Because there are more possible keys than buckets, different keys must sometimes share a bucket: a collision. The birthday paradox shows how quickly this happens: among just 23 people, there is about a 50% chance two share a birthday among 365 days. In general, collisions become likely after about the square root of m keys, so tables must handle them.
Hash tables in libraries
Python's dict and set, Java's HashMap and HashSet, C++'s std::unordered_map, and JavaScript's Map and objects are hash tables. Keys must be hashable and their hash must not change while stored; that is why Python forbids mutable lists as dictionary keys. In Java, objects used as keys must override hashCode consistently with equals.
Cryptographic and security considerations
Ordinary hash functions favour speed, not secrecy. If attackers can predict them, they can craft many keys that collide, turning a server's O(1) operations into O(n) and slowing it to a crawl: hash-flooding attacks. Modern languages defend by randomising hash seeds per process, as Python does for strings, and Java's HashMap converts very long bucket chains into balanced trees.
Worked example
Hash "cab" with p = 31 and m = 101 using character codes c = 99, a = 97, b = 98. Horner's rule: h = 99; h = 99 x 31 + 97 = 3,166; h = 3,166 x 31 + 98 = 98,244. Then 98,244 mod 101 = 72, since 101 x 972 = 98,172 and 98,244 - 98,172 = 72. So "cab" goes in bucket 72. "abc", with the same letters, gives 96,354 mod 101 = 0, a different bucket, unlike a simple sum.
Key takeaways
Hash tables map keys to array buckets with a hash function, giving average O(1) operations. Good hash functions are deterministic, fast, and spread keys evenly. Use k mod m with prime m, or the multiplication method, for integers, and polynomial hashing via Horner's rule for strings; plain character sums collide on anagrams. Collisions are inevitable, appearing after about the square root of m keys, as the birthday paradox shows. Library maps and sets are hash tables requiring stable, consistent hashes. Randomised seeds defend against hash flooding.
Flashcard
Array of buckets indexed by a hash function
Check your understanding
Why is adding up character codes a poor hash function for words?