Intermediate · INTERACTIVE LESSON
Hash table with chaining
Trace integer keys into buckets, compare colliding keys, and update or remove entries while watching chain length and load factor.
The interactive player is loading. If it does not appear, you can still read the explanation below.
THE IDEA BEHIND THE STEPS
How it works
A hash table maps keys to values. This lesson starts empty with b fixed buckets. The deterministic hash h(key) = ((key % b) + b) % b returns an index from 0 to b-1, including for negative keys. Distinct keys may collide: they share a singly linked chain but remain distinct entries. Matching a hash is not matching a key.
Enter 1–8 buckets and at most 32 operations with integer keys and values -999 through 999. insert(key, value) scans the selected chain for equality: a match updates that node's value, otherwise it appends a new node at the tail. search(key) returns the matching value or not found. delete(key) bypasses a matching node via its predecessor or bucket head, returning the removed value; a missing key leaves the table unchanged. Chains preserve insertion order. Node IDs use insertion operation numbers, survive value updates, and are never reused after deletion. Equal values at different keys are allowed.
Step through hashing, each node's key equality check, and the result. Head and next references show the conceptual chain. Load factor α = n/b is the average number of entries per bucket, not the maximum chain length or proof of balance. One bucket can hold every entry even when others are empty. Repeated-key updates keep n and α unchanged; deletion lowers both. Changing the input hides old results until Apply operations creates a new run.
Assuming constant-time bounded integer hashing, equality and allocation, and uniform distribution of keys across buckets, expected operation time is O(1 + α), hence expected O(1) only with bounded α. Simple modulo hashing does not guarantee these assumptions: keys differing by multiples of b collide. Worst-case operations scan O(n) entries; an empty bucket or head match may take O(1). Initialization is O(b), conceptual storage O(n + b), and iterative operations use O(1) auxiliary space. Resizing and rehashing are out of scope, so growing n with fixed b can increase cost.
Hash computations count once per attempt; key equality checks count each visited chain node once, including matches. Empty buckets require no equality checks. Completed attempts include updates and missing results. This deterministic simulator represents chains with arrays and copies snapshots/history; its array shifts, input validation and replay/rendering costs are outside the conceptual pointer-table bounds. Playback speed is not an algorithm benchmark. Reduced motion retains all states without movement. No concurrency or production hash implementation is simulated.