# Separate Chaining or Open hashing

## Open Hashing alias Separate Chaining

### 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:

``` 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.

# Separate Chaining or Open hashing

## Open Hashing alias Separate Chaining

### 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:

``` 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.