Collision Handling Techniques
Explore core collision handling methods for hash tables in C++. Understand chaining, open addressing, and probing techniques like linear, quadratic, and double hashing. Learn how these strategies manage collisions, ensure efficient operations, and the nuances of deletion in open addressing.
As collisions are unavoidable, the next step is to determine how to handle cases where two keys map to the same index. This lesson introduces the two primary strategies for handling collisions in hash table implementations: chaining and open addressing.
Collision handling: The two main approaches
Every collision handling strategy must answer the same question: where do we put a new key-value pair when its computed index is already occupied? The two fundamental answers are:
Chaining: Allow multiple entries to share the same slot by storing them together in a list at that slot.
Open addressing: Keep only one entry per slot, but when a collision occurs, find a different empty slot elsewhere in the array.
Both approaches allow the hash table to continue functioning correctly after a collision. They differ in how they use memory and how they search for entries.
Chaining
In chaining, each slot in the backing array does not store just one entry. Instead, each slot stores a collection of entries whose keys hash to the same index. This collection is often implemented as a linked list, though in C++ it is commonly represented using a std::vector or std::list.
When two or more keys hash to the same index, they are stored together in the same bucket. In this way, collisions are handled by allowing multiple key-value pairs to coexist at a single array index.
Insertion with chaining
Insertion with chaining works as follows:
Compute the index from the key.
Go to the bucket at that index.
Check whether the key is already present in that bucket.
If the key is already present, update its value. ...