Data Structure

Ques. 1. What do you mean by hashing? Explain any five popular                          hash functions.

Ans

Hashing

Hashing provides the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing function H which map the key with the corresponding key address or location. It provides the key-to-address transformation.

Five popular hashing functions are as follows:-

1. Division Method:

 An integer key x is divided by the table size m and the remainder is taken as the hash value. It can be defined as

H(x)=x%m+1

For example, x=42 and m=13, H(42)=45%13+1=3+1=4

2. Midsquare Method:

A key is multiplied by itself and the hash value is obtained by selecting an appropriate number of digits from the middle of the square. The same positions in the square must be used for all keys. For example if the key is 12345, square of this key is value 152399025. If 2 digit addresses is required then position 4thand 5thcan be chosen, giving address 39.

3. Folding Method:

A key is broken into several parts. Each part has the same length as that of the required address except the last part. The parts are added together, ignoring the last carry, we obtain the hash address for key K.

4. Multiplicative method:

In this method a real number c such that 0 less than c less than 1 is selected. For a nonnegative integral key x, the hash function is defined as H(x)=[m(cx%1)]+1 Here,cx%1 is the fractional part of cx and [] denotes the greatest integer less than or equal to its contents.

5. Digit Analysis:

 This method forms addresses by selecting and shifting digits of the original key. For a given key set, the same positions in the key and same rearrangement pattern must be used. For example, a key 7654321 is transformed to the address 1247 by selecting digits in position 1,2,4 and 7 then by reversing their order.