← DSA I

Hashing execution laboratory

Hash Table Lab

0/7 traced

Insert

Hash the key, pick a bucket, then place the key past any collisions.

expected case O(1) time O(1) space
1void insert(Table& t, int key) {
2 int b = key % t.m; // h(k) = k mod m
3 if ((t.n + 1.0) / t.m > 0.75) resize(t);
4 for (Node* c = t.bucket[b]; c; c = c->next)
5 if (c->key == key) return; // already stored
6 t.bucket[b].push_front(key);
7 t.n++;
8}
hashingh(19) = 5
size n4
buckets m7
probe inull
load factor α 0.57

Table · each bucket holds a chain of colliding keys

0
21
1
·
2
30
3
·
4
·
5 h(k)
125
6
·
Home bucket h(k) Compared Collision chain
Exact work through this line 2 +2 on this line
O(1) time O(1) auxiliary space 0 peak reported values
0comparisons
1reads
1writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line

size4

resultnull

slots[0]=· · [1]=· · [2]=· · [3]=· · [4]=· · [5]=· · [6]=·

Variables after line

size4

resultnull

slots[0]=· · [1]=· · [2]=· · [3]=· · [4]=· · [5]=· · [6]=·

Reads, writes, and state changes on this line

homeBucket.value null → 5 highlight

Why this bound?

O(1) time · O(1) space

expected
fixed readfixed writeInput may grow; this fixed-width work does not → 1
Auxiliary memory model
cursortemporarycounter

A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.

  1. h(k) = k mod m lands the key in its bucket with one arithmetic step.
  2. With uniform hashing, the expected chain or probe-run length is the load factor α = n/m, a constant.
  3. 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.
Step 1 of 8 · hash-key Hash 19

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.

1 / 8