Hashing and Hash Tables
How hash tables achieve expected constant-time lookups, what happens on collisions, how load factor and resizing work, and when the worst case or an adversary matters.
What you will learn
How hash tables achieve expected constant-time lookups, what happens on collisions, how load factor and resizing work, and when the worst case or an adversary matters.
Prerequisites: Modules 3 (modular arithmetic) and 5.
Concepts
Hash function, hash table, buckets, collisions, chaining, open addressing, linear/quadratic probing, double hashing, load factor, resizing/rehashing, hash sets and maps.
A hash function maps a key to an integer; the table uses hash(key) mod buckets to choose a bucket. Different keys can land in the same bucket — a collision. Chaining stores a list per bucket; open addressing looks for another empty slot by probing (+1, +2, … linear; +1, +4, +9, … quadratic; +h₂(key)·i double hashing). The load factor α = elements / buckets controls chain length or probe count; tables resize (rehash every key into a larger table) when α passes a threshold.
Syntax
unordered_map<string, int> frequency;
++frequency["DSA"];Complexity and caveats
Hash operations are expected O(1) under suitable assumptions, but worst-case can be O(n). Ordered map/set operations are generally O(log n).
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The bucket counts show libstdc++ rehashing to roughly double the size (prime bucket counts) whenever the load factor would exceed 1.0. Note operator[] inserts a default value for a missing key — use find or count when you only want to test membership.
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, int> frequency;
for (string w : {"DSA", "graph", "DSA", "heap", "DSA", "graph"}) ++frequency[w];
map<string, int> ordered(frequency.begin(), frequency.end()); // print in sorted order
for (auto& [w, c] : ordered) cout << w << ": " << c << '\n';
unordered_set<int> s;
cout << "max_load_factor = " << s.max_load_factor() << '\n';
size_t lastBuckets = s.bucket_count();
cout << "bucket counts while inserting 0..99:";
for (int i = 0; i < 100; ++i) {
s.insert(i);
if (s.bucket_count() != lastBuckets) { lastBuckets = s.bucket_count(); cout << ' ' << lastBuckets; }
}
cout << "\nload factor now " << fixed << setprecision(2) << s.load_factor() << '\n';
// two-sum: one pass, value -> index
vector<int> a = {8, 3, 11, 7, 2};
int target = 9;
unordered_map<int, int> seen;
for (int i = 0; i < (int)a.size(); ++i) {
auto it = seen.find(target - a[i]);
if (it != seen.end()) { cout << "two-sum " << target << ": indices " << it->second << " and " << i << '\n'; break; }
seen[a[i]] = i;
}
}DSA: 3
graph: 2
heap: 1
max_load_factor = 1
bucket counts while inserting 0..99: 13 29 59 127
load factor now 0.79
two-sum 9: indices 3 and 4Applications
Frequency counts, two-sum, duplicate detection, grouping anagrams, caching, deduplication, and indexing.
Open addressing from scratch Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Keys 10, 18 and 26 all hash to slot 2 of 8 and form a cluster — linear probing's weakness. Deleting from an open-addressing table needs tombstones (a “deleted” marker), otherwise a later search could stop early at the hole and miss a key further along the probe sequence.
#include <bits/stdc++.h>
using namespace std;
struct LinearProbingSet {
vector<long long> slot; // LLONG_MIN = empty
size_t used = 0, probes = 0;
explicit LinearProbingSet(size_t cap) : slot(cap, LLONG_MIN) {}
size_t home(long long k) const { return (size_t)((k % (long long)slot.size() + (long long)slot.size()) % (long long)slot.size()); }
bool insert(long long k) {
if ((used + 1) * 10 > slot.size() * 7) rehash(slot.size() * 2); // keep load factor <= 0.7
size_t i = home(k);
while (slot[i] != LLONG_MIN) { ++probes; if (slot[i] == k) return false; i = (i + 1) % slot.size(); }
slot[i] = k; ++used; return true;
}
bool contains(long long k) {
size_t i = home(k);
while (slot[i] != LLONG_MIN) { ++probes; if (slot[i] == k) return true; i = (i + 1) % slot.size(); }
return false;
}
void rehash(size_t cap) {
vector<long long> old = move(slot);
slot.assign(cap, LLONG_MIN); used = 0;
for (long long k : old) if (k != LLONG_MIN) insert(k);
}
};
int main() {
LinearProbingSet s(8);
for (long long k : {10, 18, 26, 3}) s.insert(k); // 10, 18, 26 all
…slots: . . 10 18 26 3 . .
contains 26: true, contains 34: false
100000 keys, capacity 262144, load 0.38, average probes per unsuccessful lookup 0.81Advanced topics
Rolling hash, polynomial hashes, double hashing, collision attacks, custom hash functions, consistent hashing, Bloom filters, counting Bloom filters, cuckoo hashing, and hash-table security considerations.
Collision attacks: if an attacker knows the hash function, they can submit keys that all collide, turning O(1) operations into O(n) and a server into a slow one. Defences: keyed/randomised hashes (SipHash in many languages), or ordered maps for untrusted keys.
Custom hashes: unordered_map<pair<int,int>, int> needs a hash functor; combine fields carefully (e.g. h1 * 1000003 ^ h2) rather than adding them.
Bloom filter: k hash functions set bits in an m-bit array; membership answers “definitely not” or “probably yes” with a tunable false-positive rate; no false negatives (Module 42).
Consistent hashing: places servers and keys on a ring so adding a server moves only about 1/n of the keys.
hashtablePractice
Easy: first non-repeating character in a string.
Medium: count subarrays with sum k using prefix sums and a hash map of prefix frequencies.
Hard: design an LRU cache with O(1) get and put (hash map + doubly linked list; the capstone in Module 65).
Quiz
? Why did the probing demo place 10, 18 and 26 in consecutive slots?
+ They all hash to slot 2 of 8, and linear probing walks to the next free slot. :: That is primary clustering.
- They are sorted. :: Order is irrelevant.
- Quadratic probing was used. :: Linear probing was used.
- The table was full. :: Load was low.
? `frequency[key]` on a missing key in an `unordered_map<string,int>`…
+ inserts the key with value 0 :: Use `find` or `count` to test membership without inserting.
- throws an exception :: That is `at()`.
- returns -1 :: No.
- is undefined behaviour :: It is defined.
? Which are true of hash tables? (select all that apply)
+ Expected O(1) lookups under a good hash and bounded load factor :: The usual assumption.
+ Worst case O(n) per operation :: All keys can collide.
+ Open-addressing deletion needs tombstones (or rehashing) :: Otherwise searches stop at the hole.
- They keep keys in sorted order :: Use `map`/`set` for order.