Like separate chaining, open addressing is a method for handling collisions. In Open Addressing, all elements are stored in the hash table itself. So at any point, the size of the table must be greater than or equal to the total number of keys.

The operations involved are-

• Insert(h)
• Search(h)
• Delete(h)

Double Hashing

It is a technique to resolve collisions in Open Addressed Hash Tables. As we see in the video, this can be done by applying a second hash function to key when a collision occurs.

Implementation

• Delete Operation
``````Declare Function Remove(int k)
Declare hash_val, init of the integer datatype.
initialize hash_val = HashFunc(k)
initialize init = -1
while (hash_val != init and (ht[hash_val]
== DelNode::getNode() or ht[hash_val]
!= NULL and ht[hash_val]->k!= k))
if (init == -1)
init = hash_val
hash_val = HashFunc(hash_val + 1)
if (hash_val != init and ht[hash_val] != NULL)
delete ht[hash_val]
ht[hash_val] = DelNode::getNode()
``````
• Search Operation
``````Declare Function SearchKey(int k)
Declare hash_val, init of the integer datatype.
initialize hash_val = HashFunc(k)
intialize init = -1
while (hash_val != init and (ht[hash_val]
== DelNode::getNode() or ht[hash_val]
!= NULL and ht[hash_val]->k!= k
if (init == -1)
init = hash_val
hash_val = HashFunc(hash_val + 1)
if (ht[hash_val] == NULL or hash_val == init)
return -1
else
return ht[hash_val]->v
``````