Hashing Technique based Study Material for gate Computer Science

Hashing provides the direct access of record from the file no matter where then 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.

Usually the key space is much larger than the address space, therefore, many keys are mapped to the same address. Suppose that two keys K1 and K2 map to the same address. When the record with key K1 is entered, it is inserted at the hashed address, but when another record with key K2 is entered, it is a dilemma where to insert as a record with key K1 is already there. This situation is called a hash collision.

Here in this gate study material for computer science I am also going to explain two broad classes of collision.Two broad classes of collision resolution techniques are: open addressing and chaining.

Open addressing: The simplest way to resolve a collision is to start with the hash address and do a sequential search through the table for an empty location. The idea is to place the record in the next available position in the array. This method is called linear probing. An empty record is indicated by a special value called null. The major drawback of the linear probe method is clustering.

Chaining: In this technique, instead of hashing function value as location we use it as an index into an array of pointers. Each pointer access a chain that holds the element having same location. 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 keyto- address transformation.

Five popular hashing functions are as follows:

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

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 4th and 5th can be chosen, giving address 39.

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.

Multiplicative method: In this method a real number c such that 0

The author is a professional technical trainer, technical content writer in the field of Computer Science and Engineering. He loves to read and writes the content on the topic to be asked in Gate Computer Science Exam.