Insert
Hash the key, pick a bucket, then place the key past any collisions.
1void insert(Table& t, int key) {2int b = key % t.m; // h(k) = k mod m3if ((t.n + 1.0) / t.m > 0.75) resize(t);4for (Node* c = t.bucket[b]; c; c = c->next)5if (c->key == key) return; // already stored6t.bucket[b].push_front(key);7t.n++;8}
h(19) = 547null0.57 Table · each bucket holds a chain of colliding keys
size4
resultnull
slots[0]=· · [1]=· · [2]=· · [3]=· · [4]=· · [5]=· · [6]=·
size4
resultnull
slots[0]=· · [1]=· · [2]=· · [3]=· · [4]=· · [5]=· · [6]=·
homeBucket.value null → 5 highlight
O(1) time · O(1) space
expectedA bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- h(k) = k mod m lands the key in its bucket with one arithmetic step.
- With uniform hashing, the expected chain or probe-run length is the load factor α = n/m, a constant.
- Constant expected work per operation is expected O(1) time with O(1) auxiliary space.
Assumptions behind this claim
- The teaching hash is h(k) = k mod m, where m is the bucket count.
- Expected-case analysis assumes keys distribute uniformly across buckets (simple uniform hashing).
- The load factor is kept bounded.
- Each displayed hash computation, comparison, read, write, or allocation is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
h(19) = 19 mod 7 = 5. The bucket is computed, never searched for.
About this implementation
h(k) = k mod m computes the bucket directly — it is never searched for. Under uniform hashing a lookup is expected O(1); a degenerate distribution collapses to one chain (O(n)). Linear probing leaves tombstones on delete so probe runs stay intact, and a resize rehashes every stored key into a doubled table.