Resizing, sets, and applications
Hash tables stay fast by growing as they fill. Beyond maps, hashing powers sets, caches, duplicate detection, and probabilistic structures that use tiny amounts of memory.
Rehashing
When the load factor passes a threshold, often 0.75 for chaining or about 0.5 to 0.7 for open addressing, the table allocates a larger array, usually double the size, and reinserts every item, since each key's bucket depends on m. A resize costs O(n), but as with dynamic arrays, doubling makes the amortised cost per insertion O(1).
Worst case versus average
Hash table operations are O(1) on average, assuming a good hash function, but O(n) in the worst case if every key lands in one bucket. For guarantees, use a balanced tree, with O(log n) worst case, or a hash table with defences such as randomised seeds and tree-based buckets.
Hash sets and counting
A hash set stores keys without values, answering 'have I seen this?' in O(1) average time. This turns many O(n^2) algorithms into O(n): detecting duplicates, finding two numbers that sum to a target, or intersecting two lists. Hash maps from items to counts give frequency tables, the basis of word counts and histograms.
Caching and memoisation
Caches store expensive results keyed by their inputs. Memoising a function stores each argument's result in a hash map, so repeated calls return instantly. An LRU cache adds a doubly linked list so the least recently used entry can be evicted in O(1). Web servers, databases, and processors all depend on caching.
Hashing beyond tables
Checksums and cryptographic hashes, such as SHA-256, verify that files have not changed and identify content: Git names every file version by its hash. Consistent hashing places servers and keys on a ring so that adding or removing a server moves only a small fraction of keys, which is vital for distributed caches and databases.
Bloom filters
A Bloom filter, invented by Burton Bloom in 1970, tests set membership using a bit array and k hash functions. Adding an item sets k bits; checking an item tests those k bits. If any is 0, the item is definitely absent; if all are 1, it is probably present. False positives are possible but false negatives are not. Browsers and databases use Bloom filters to skip expensive lookups for items that are certainly absent.
Choosing between hash tables and trees
Use a hash table when you need fast exact lookups and do not care about order. Use a balanced search tree when you need sorted iteration, range queries, nearest keys, or guaranteed worst-case bounds. Many applications use both, for example a hash map for lookup by ID plus a tree index for date ranges.
Worked example
Two-sum: given [2, 7, 11, 15] and target 9, find two numbers adding to 9. Scan once with a hash set of numbers seen: at 2, check whether 9 - 2 = 7 is in the set: no; add 2. At 7, check 9 - 7 = 2: yes, so the answer is 2 and 7. This takes O(n) time instead of the O(n^2) of checking every pair, at the cost of O(n) extra memory.
Key takeaways
Hash tables rehash into a larger array when the load factor passes a threshold; doubling keeps insertion amortised O(1). Operations are O(1) on average but O(n) in the worst case; trees give O(log n) guarantees. Hash sets and count maps turn quadratic tasks such as duplicate detection and two-sum into linear ones. Caches and memoisation store results by key; LRU caches add a linked list. Cryptographic hashes verify and identify content; consistent hashing distributes keys across servers. Bloom filters test membership compactly with possible false positives but no false negatives.
Flashcard
Reinserting all items into a larger table
Check your understanding
A Bloom filter says an item is not in the set. How certain is that?