Collision Handling Techniques
Explore collision handling methods in hash tables, focusing on chaining and open addressing strategies. Understand how to insert, search, and delete keys effectively, while learning probing techniques like linear, quadratic, and double hashing. Gain practical Go implementations and insights into managing collisions efficiently in hash table design.
We'll cover the following...
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 slice 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, although in Go it is commonly represented using a slice.
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 ...