Collision Resolution

Since a hash function can map multiple different keys to the same index, a strategy for handling these 'collisions' is essential for any hash table implementation. There are two primary methods for collision resolution: Separate Chaining and Open Addressing. In Separate Chaining, each slot in the hash table array does not hold the value itself, but rather a pointer to another data structure, typically a linked list, which stores all the key-value pairs that hashed to that index. When inserting a new element, we hash its key to find the correct linked list and then append the element. Searching involves hashing the key and then performing a linear search on the corresponding list. The performance depends on the length of these lists (chains). In Open Addressing, all key-value pairs are stored within the array itself. When a collision occurs upon insertion (the target slot is already occupied), we 'probe' for an alternative slot in the table. The sequence of slots to check is the probe sequence. Common probing strategies include Linear Probing (checking the next slot, `i+1`, `i+2`, etc.), Quadratic Probing (checking `i+1^2`, `i+2^2`, etc.), and Double Hashing (using a second hash function to determine the step size). Open addressing saves memory by not using pointers but can suffer from 'clustering', where occupied slots group together, degrading performance.