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

1. 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.
2. Hash Function: The hash function takes a key and computes an index in the array.
3. 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.
4. Searching:
   • Compute the index for the key using the hash function.
   • Search through the linked list at that index for the desired key.
5. 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

function 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

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

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.