Hashing

~~~~~~~~~~~~~~~~~~~~ HASHING ~~~~~~~~~~~~~~~~~~~~

The searching methods Linear Search and Binary Search are based on compariosion of datas. Therefore we need search techniques whose search time is independent of number of elements. Using Hashing, the postion of particular element is determined by value of hash key of that element. 

Hash Table: Hash table is a structure arranged in a form of an array where we store a key value after applying the hash function. Each structure is capable of storing one data only. Therefore time required to locate any element in the hash table is O(1). Each position on a table is known as bucket. H(k) is home bucket for the hash table.

Hash Function: The function that transform the original data into hash data is known as hash function. 
For example: let A is the orginal data having key K and H is the hash function that gives value B, then A is stored in postion H(K); i.e. position B of hash table. 

 The various ways to find hash functions are

1. Division Method: Choose a number m larger than the number n  of elements, may be last prime number in the range 1 to n . The hash function H is defined by

H(K)=K mod m

For Example: Consider a file  and n=100. Let us suppose m=97 then hash function can be applied to some of the elements as follows

H(3205)=3205 mod 97 =4

H(7148)= 7148 mod 97=67

H(2345)=2345 mod 97=17

Hash Table

K     :   3205     7148     2345 ............

H(K) :     4          67         17  ..............

2. Mid Square Method: In this method, the square of elements is taken and then number of digit extracted from the square as hash data.

For Example: Consider a file of 100 elements then we can apply this method as follows

Hash Table

K      :  3205            7148               2345

K²    : 10272025     51093904      5499025    
H(K) :  72                  93                   99  

3. Folding Method: In this method elements are partitioned into number of parts  each of which has a same length except the last part. These parts are added together and hash value is obtained.
For Example:  Consider the file of 100 elements and each element is to be divided into single digit. This method can be applied as follows

Hash Table

K              :    3205          7148         2345
Parts         :   3,2,0,5      7,1,4,8      2,3,4,5
Sum H(K)  :     10             20             14
 

4. Digit Analysis Method: In this method, hash data is obtained by selecting and shifting digits or bits of the original data. Digits position having most uniform distribution is selected.

5. Length Dependent Method: In this method, the length of the data is used along with some original data position to produce hash key.

Following points must be remembered while using any of the above Hash Function

i. Function should be easy and quick to compute.

ii. There should be no or minimum collision.

To search a data with any key k, we compute first H(K) and see whether that data exists at position H(K) of the tabe.