Collision Handling Techniques
Explore collision handling strategies in hash tables, focusing on chaining and open addressing methods. Understand insertion, search, and deletion processes, and learn how to implement these techniques in Python, including linear probing, quadratic probing, and double hashing to manage collisions efficiently.
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 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, although in Python it is commonly represented using a 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. ...