Open Hashing (Separate Chaining)

Open Hashing, also known as Separate Chaining, is a technique used in hash tables to handle collisions. In a hash table, a collision occurs when two different keys are hashed to the same index. Open Hashing addresses this by storing all elements that hash to the same index in a linked list or another data structure at that index.

Table of Contents

What is Open Hashing?

In open hashing, keys are stored in linked lists attached to cells of a hash table. Each list contains all the keys hashed to its cell. Consider, as an example, the following list of words:

A, FOOL, AND, HIS, MONEY, ARE, SOON, PARTED

As a hash function, we will use the simple function for strings mentioned above, i.e., we will add the positions of a word’s letters in the alphabet and compute the sum’s remainder after division by 13.

  • We start with the empty table. The first key is the word A; its hash value is h(A) =1 mod 13 = 1.
  • The second key, the word FOOL— is installed in the ninth cell since (6 + 15+15+12)mod 13 = 9,and soon.
  • The final result of this process can be seen in the below image.
Open Hashing

Note: A collision of the keys ARE and SOON because h(ARE)= (1+18+5)mod 13 = 11 and h(SOON) = (19+15+15+14)mod 13 = 11.

How do we search in a dictionary implemented as such a table of linked lists? We do this by simply applying to a search key the same procedure that was used for creating the table. To illustrate, if we want to search for the key KID in the hash table of the above image, we first compute the value of the same hash function for the key: h(KID) = 11.

Since the list attached to cell 11 is not empty, its linked list may contain the search key. But because of possible collisions, we cannot tell whether this is the case until we traverse this linked list. After comparing the string KID first with the string ARE and then with the string SOON, we end up with an unsuccessful search. 

In general, the efficiency of searching depends on the lengths of the linked lists, which, in turn, depend on the dictionary and table sizes, as well as the quality of the hash function.

Advantages of Open Hashing

  1. Easy to Implement: The concept of chaining with linked lists is straightforward and relatively simple to implement.
  2. Flexible Size: The linked lists can dynamically grow as more keys hash to the same index, making the hash table more flexible in handling collisions.
  3. No Clustering: Unlike some collision resolution methods, open hashing doesn’t suffer from primary or secondary clustering, where multiple keys cause continuous collisions at adjacent indexes.

Disadvantages of Open Hashing

  1. Memory Overhead: Each node in the linked list typically requires extra memory for pointers, leading to higher memory usage compared to other methods.
  2. Performance: If many collisions occur, and the linked lists become long, the time complexity for search, insertion, and deletion can approach O(n) in the worst case, where n is the number of elements in the linked list at a particular index.