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 1

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

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.

Data Structures