Discuss Open Addressing, Double Hashing and Implementation of Open Addressing?

Software Development
#1

Open Addressing

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