Collision Handling Techniques
Understand collision handling in hash tables by exploring chaining and open addressing methods. Learn how JavaScript implementations manage insertions, searches, and deletions using linked lists and probing sequences to maintain efficient data storage and retrieval.
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 JavaScript it is commonly represented using an array.
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 ...