Explain Open Addressing. (Linear Probing, Quadratic Probing, Double Hashing)

Difficulty: 5/10

collision resolution, probing strategies, hash table performance

Open Addressing

Open addressing stores every entry directly inside the Hash Table's array. When the preferred slot is occupied, the algorithm probes other slots according to a deterministic sequence until it finds the key or an available position. Common strategies are linear probing, quadratic probing, and double hashing.

javascript

1
Linear probing checks consecutive slots and has good cache locality but can suffer from primary clustering.
2
Quadratic probing uses increasing probe distances and reduces primary clustering.
3
Double hashing uses a second hash function to produce a more independent probe sequence.
4
Open addressing requires careful handling of deletion, often using tombstones.
5
Performance degrades as the table becomes too full.
6
Resizing is generally necessary at a lower load factor than with some chaining implementations.

Scenario Questions

0-2 years experience

Follow-up Questions