Open Addressing

Open addressing is a collision resolution technique where all elements are stored directly within the hash table array. When a new key hashes to an index that is already occupied, the algorithm probes for an alternative empty slot. The main methods differ in how they generate the probe sequence. **Linear Probing**: This is the simplest method. If slot `h(k)` is occupied, we try `(h(k) + 1) % m`, then `(h(k) + 2) % m`, and so on, where `m` is the table size. It's easy to implement but suffers from a problem called primary clustering, where long runs of occupied slots build up, leading to long search times. **Quadratic Probing**: This method probes using a quadratic function of the attempt number `i`. We try `(h(k) + c1*i + c2*i^2) % m`. It avoids primary clustering but can suffer from a milder issue called secondary clustering, where keys that hash to the same initial slot will use the same probe sequence. **Double Hashing**: This is one of the most effective methods. It uses a second hash function, `h2(k)`, to determine the step size for the probe sequence. We try `(h(k) + i * h2(k)) % m`. Since the step size depends on the key itself, different keys that hash to the same initial slot will likely have different probe sequences, mitigating clustering. Deletion in open addressing is tricky; we can't simply empty a slot, as it might break a probe chain. Instead, we mark the slot as 'deleted'.