Separate Chaining or Open hashing

<<Previous - Hashing Collision

Next - Closed Hashing>>




Open Hashing alias Separate Chaining

Open Hashing or Separate Chaining method maintains a list of all elements that are hashed to same location. It needs a small modification to the hash data structure. Instead of storing the element into the array, hash table uses linked list, they will be stored in the linked lists. For easy use, the lists have header. Now, each index of an array points to one of the linked list. Suppose we insert an element into the hash table, it is added to the linked list at the corresponding index in the array. Hence, the collisions no longer occur, because the linked list has no limit on its length. Therefore, if more than one keys hash to the same index, then both keys are stored in that linked list.

Open Hashing or Separate Chaining Example

Let us say that we have a sequence of numbers { 437, 325, 175, 199, 171, 189, 127, 509} and a hash function H(X) = X mod 10 Let us see the results of separate chaining hash table.

Separate Chaining Solution:

An Open Hash Table alias Separate Chaining


 For first key: 437
      		H (437) = 437 % 10 = 7
  		The index for 437 is 7.
 For key: 325
                H (325) = 325 % 10 = 5
                The index for 325 is 5.
 For key: 175
                H (175) = 175 % 10 = 5
                The index for 175 is 5.
 For key: 199
 		H (199) = 199 % 10 = 9
 		The index for 199 is 9.
 For key: 171
 		H (171) = 171 % 10 = 1
 		The index for 171 is 1.
 For key: 189
                H (189) = 189 % 10 = 9
                The index for 189 is 9.
 For key: 127
               H (127) = 127 % 10 = 7
               The index for 127 is =7.
 For key: 509
               H (509) = 509 % 10 = 9
               The index for 509 is 9.
 

Searching using Hashing

If you want to search a data, first we calculate an index by using hashing and then go to that location in the array and look down the list. There you see if that data is present in the list. The constant time required for this sear is O(1). For worst case, When every elements hashed to same location, in that we would be really doing a straight linear search on the linked list, which means that the time required to search an element is O(n).

Open Hashing or Separate Chaining - Disadvantages

  • Open Hashing requires pointer and this may slow down the process of inserting of an element into the table.
  • Open Hashing also needs the extra memory for linked list data structure.

To overcome the disadvantages, an alternative method Closed Chaining can be used to avoid the collision. Let us see that next.



<<Previous - Hashing Collision

Next - Closed Hashing>>







Separate Chaining or Open hashing

<<Previous - Hashing Collision

Next - Closed Hashing>>




Open Hashing alias Separate Chaining

Open Hashing or Separate Chaining method maintains a list of all elements that are hashed to same location. It needs a small modification to the hash data structure. Instead of storing the element into the array, hash table uses linked list, they will be stored in the linked lists. For easy use, the lists have header. Now, each index of an array points to one of the linked list. Suppose we insert an element into the hash table, it is added to the linked list at the corresponding index in the array. Hence, the collisions no longer occur, because the linked list has no limit on its length. Therefore, if more than one keys hash to the same index, then both keys are stored in that linked list.

Open Hashing or Separate Chaining Example

Let us say that we have a sequence of numbers { 437, 325, 175, 199, 171, 189, 127, 509} and a hash function H(X) = X mod 10 Let us see the results of separate chaining hash table.

Separate Chaining Solution:

An Open Hash Table alias Separate Chaining


 For first key: 437
      		H (437) = 437 % 10 = 7
  		The index for 437 is 7.
 For key: 325
                H (325) = 325 % 10 = 5
                The index for 325 is 5.
 For key: 175
                H (175) = 175 % 10 = 5
                The index for 175 is 5.
 For key: 199
 		H (199) = 199 % 10 = 9
 		The index for 199 is 9.
 For key: 171
 		H (171) = 171 % 10 = 1
 		The index for 171 is 1.
 For key: 189
                H (189) = 189 % 10 = 9
                The index for 189 is 9.
 For key: 127
               H (127) = 127 % 10 = 7
               The index for 127 is =7.
 For key: 509
               H (509) = 509 % 10 = 9
               The index for 509 is 9.
 

Searching using Hashing

If you want to search a data, first we calculate an index by using hashing and then go to that location in the array and look down the list. There you see if that data is present in the list. The constant time required for this sear is O(1). For worst case, When every elements hashed to same location, in that we would be really doing a straight linear search on the linked list, which means that the time required to search an element is O(n).

Open Hashing or Separate Chaining - Disadvantages

  • Open Hashing requires pointer and this may slow down the process of inserting of an element into the table.
  • Open Hashing also needs the extra memory for linked list data structure.

To overcome the disadvantages, an alternative method Closed Chaining can be used to avoid the collision. Let us see that next.



<<Previous - Hashing Collision

Next - Closed Hashing>>