When two keys hash to the same table cell, open addressing gives the collision another chance. It stores entries directly in the table array instead of using linked lists. section 12.17 section 12.19
For each key, a probing function checks table positions in sequence. Insertion stops at an empty cell; search stops successfully when it finds the key and unsuccessfully when it reaches an empty cell. section 12.19
A key gets another chance
To insert key 714, the probes visit index 3, then index 1, and finally index 6. The first two cells are occupied, so the entry is stored at the empty sixth cell. section 12.19
A valid probing design must cover the table correctly:
- Make the sequence of probes for every key a permutation of all table indexes, so every cell can be reached. section 12.19
- Use linear probing, p(k,i) = (h(k) + i) % m, or quadratic probing, p(k,i) = (h(k) + a*i + b*i²) % m. section 12.19
- Expect fixed capacity, possible clustering, and slower operations as the table fills. section 12.20 section 12.22
- Treat deletion carefully: clearing a cell can make later searches stop too early, while deleted markers add search work. section 12.20
Open addressing saves the memory overhead of linked lists, but it cannot store more entries than the array has cells. Because deletion is difficult and performance worsens as the table fills, chaining is usually preferable when removal is required. section 12.20 section 12.22
