Separate chaining
Separate chaining is a widely used method to resolve collisions in hash tables. When two or more elements are hash to the same location, these elements are represented into a singly-linked list like a chain. Since this method uses extra memory to resolve the collision, therefore, it is also known as open hashing.
How Separate Chaining Works
- Hash Table Structure: The hash table is an array of a fixed size. Each element of this array is a head pointer to a linked list.
- Hash Function: The hash function takes a key and computes an index in the array.
- Insertion:
- Apply the hash function to the key to get the index.
- Insert the key-value pair at the head of the linked list at this index.
- Searching:
- Compute the index for the key using the hash function.
- Search through the linked list at that index for the desired key.
- Deletion:
- Find the index using the hash function.
- Search the linked list for the key and remove the corresponding node.
Algorithm for Implementing Separate Chaining
Separate Chaining - Insert
Algorithm 1function INSERT (hash table, key, hash value)
if hash table[hash_value] = null then
hash_table[hash_value] = new LinkedList (key)
else
hash_table[hash_value). headInsert(key)
Separate Chaining - Insert Without Duplicates
Algorithm 2 function INSERT_NO_DUPLICATES (hash_table, key, hash_value)
if Search (hash_table, key, hash_value) != -1 then
return
if hash_table[hash_value] = null then
hash_table[hash_value] = new LinkedList(key)
else
hash_table[hash_value].headInsert(key)
Separate Chaining - Search
Algorithm 3 function SEARCH(hash_table, key, hash_value)
list ← hash_table[hash_value]
for i ← 0 to list.length -1 do
if list.get(i) = key then
return i
return -1
Advantages of Separate Chaining
- Simplicity: It is straightforward to implement.
- Less Sensitive to Hash Function: It works relatively well even with a poor hash function.
- Performance: The performance gracefully degrades as the load factor increases (the ratio of the number of elements to the number of buckets).
Disadvantages of Separate Chaining
- Memory Overhead: Every element requires extra memory for the pointers in the linked list.
- Cache Performance: Poor cache performance compared to open addressing due to the use of linked lists.
- Variable Length: The length of the chains can vary, leading to potentially poor performance if one chain becomes significantly longer than others.
Next Topic :Open addressing