Hashing Introduction

Introduction 

Searching Techniques:

        There are several searching techniques like linear search, binary search etc. In these techniques, time taken to search any particular element depends on the total number of elements. For Example complexity of Linear Search O(n), Binary Search O(logn), Hash table O(1).

Hashing:

          Hashing is an algorithm that calculates a fixed-size bit value from indexes. It is a searching technique that Used to Uniquely identify a specific object from a group of similar object.

Hash:

          Hash is a function that convert one value to another. Hashing data is a common practice in computer science and is used for several different purposes.

Hash Function:

      Hash function is a function that maps any number or string to a small integer value. Hash function takes the data item as an input and returns a small integer value as an output. The small integer value is called as a hash value. Hash value of the data item is then used as an index for storing it into the hash table.

 h(k) = k mod (%) SizeOfArray

Properties of Hash Function:

- It is efficiently computable.

          - It minimizes the number of collisions.

          - It distributes the keys uniformly over the table.

Collision:

        Hash function is get a number of a key, there is possibility that there are two key result in same value. The situation where a newly inserted key maps to an already occupied slot in hash table is called collision. We must need to solve it. There are basic two methods of solving collision.

 

2. Separate Chaining:

             In this technique, each cell point to a linked list of a record. If any key has same number than that index creates a linked list Which have same function value.

2. Open Addressing: 

        Like separating chaining, open addressing is also a method for handling collisions. In this collision, All the element is stored in a separate index (itself) in hash table. If any bucket is already occupied, then it is increased key every time until it found empty index to place. It has also three types.

i.                   Quadratic Probing:

Quadratic probing is similar to linear probing but it has one difference When collision occurs, we probe for 𝑘^2 bucket in 𝑘^𝑡ℎ iteration. We keep probing until an empty bucket is found. Formula h(k) =  mod (%) SizeOfArray

ii.                   Quadratic Probing:

Quadratic probing is similar to linear probing but it has one difference When collision occurs, we probe for 𝑘^2 bucket in 𝑘^𝑡ℎ iteration. We keep probing until an empty bucket is found. Formula h(k) =  mod (%) SizeOfArray

iii.                   Double hashing:

Double hashing is similar to linear probing but it has also difference We use another hash function hash2(k) and look for k * hash2(k) bucket in 𝑘^𝑡ℎ iteration. It requires more computation time as two hash functions need to be computed. h(k) = key mod(%) SizeOfArray

h(k) = (h(k) –k) mod(%) h(k)

Functions in Hashing

Insertion:

          Move to the bucket corresponds to the above calculated hash index and insert the new node at the end of the list.

int insert(int k, int v){

            int hash = HashFun(k);

            while (temp[hash] != NULL && temp[hash]->key == k) {

                 hash = HashFun(hash + 1);

         }

         if (temp[hash] != NULL)

            delete temp[hash];

         temp[hash] = new insert(int k,int v);

}

Searching:

          For search value from hash table, calculate the hash index for the key, move to the bucket corresponds to the calculated hash index, search the list in the current bucket.

void SearchKey(int k){

         int h = HashFunc(k);

         while (temp[h] != NULL && temp[h]->key != k){

            h = HashFunc(h + 1);

         }

         if (temp[h] == NULL)

            return -1;

         else

            return temp[h]->value;

}

Deletion:

       To delete a node from hash table, calculate the hash index for the key, move to the bucket corresponds to the calculated hash index, search the list in the current bucket to find and remove the node with the given key (if found).

void Delete(int k) {

         int h = HashFun(k);

         while (temp[h] != NULL) {

            if (temp[h]->key == k)

               break;

            h = HashFun(h + 1);

         }

         if (temp[h] == NULL) {

            cout<<"No Element found at key "<<k<<endl;

            return;

         } else {

            delete temp[h];

         }

}

Implementation Of Hash Table