Skip to main content

Collision Resolution: Chaining vs Open Addressing

What This Concept Is​

Chaining stores a collection at each bucket. Open addressing stores records inside the table and follows a probe sequence on collisions. Linear probing visits (h(key)+step) mod m. Its states must distinguish never-used empty, live entry, and deleted entry. Payload None may be legal and is not a safe empty marker.

Search stops at a never-used empty slot or after a bounded full probe cycle. It continues past tombstones. Insertion remembers the first tombstone but keeps searching for an existing equal key; otherwise an update can create duplicates.

Why It Matters Here​

A dictionary is a state machine. Single insert/get examples miss the important failures: deleting the first collision, updating a later key, wrapping past the end, reusing tombstones, and rebuilding after many deletes. Checking sequences against a simple trusted model tests the actual API contract.

Concrete Examples​

Capacity 8, hash key mod 8: put (0,A), (8,B), (16,C) into slots 0,1,2. Delete key 0. If slot 0 becomes never-used empty, get(16) incorrectly reports absence. Mark it deleted instead. Now put (8,new). A faulty implementation immediately fills slot 0 and leaves old key 8 in slot 1. Deleting the new entry can expose the obsolete one. Correct insertion remembers slot 0 but continues, finds key 8 in slot 1, and replaces its value without changing live size.

With keys 7,15,23, the same sequence wraps through slots 7,0,1. Modulo indexing and a maximum of m probes are needed even if normal load policy leaves empty slots. State the reachability invariant: no never-used empty slot lies on the probe path from a live key's home to its stored location.

Common Confusion / Misconceptions​

Deleting safely does not require exactly one technique. Tombstones work with eventual cleanup; carefully reinserting the following cluster or backward-shift deletion can also preserve reachability under their own proofs. Chaining can unlink a known node in O(1) with suitable links, but delete-by-key still pays the search cost. A bound for uniform independent probe sequences cannot simply be assigned to linear probing.

How To Use It​

Track live size and used occupancy separately: used includes tombstones. Grow for live load; rebuild at the same capacity when deletion history is the problem. Reinsert live entries under the destination capacity instead of copying their old positions. In Lab C, preserve arbitrary payloads and document missing-key behavior. A rebuild changes probe locations, not the abstract dictionary.

Check Yourself​

  1. Why is a tombstone different from an empty slot?
  2. Why must insertion search beyond the first tombstone?
  3. What makes a missing-key lookup terminate?
  4. Which counters change on update, delete, and tombstone reuse?

Mini Drill or Application​

Write state transitions for empty→live, live→live update, live→deleted, and deleted→live reuse. Test each inside a wraparound cluster. Use a dictionary oracle for long mixed sequences, including deletes of absent keys. Retain a minimal counterexample for each deliberate bug. See P10 and Lab C.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for linear probing, collision resolution, deletion, and tombstones. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.