Hash Functions

Hash Functions

There are various types of hash functions or hash methods which are used to place the elements in hash table.

Division Method

The hash function depends upon the remainder of division.

Typically the divisor is table length. For example :-

If the record 54, 72, 89, 37 is to be placed in the hash table and if the table size is 10 then

Multiplicative Hash Function

The multiplicative hash function works in following steps

1) Multiply the key 'k' by a constant A where A is in the range 0 < A < 1. Then extract the fractional part of KA.

2) Multiply this fractional part by m and take the floor.

The above steps can be formulated as

h(k) = m {KA}]

Fractional part

Donald Knuth suggested to use A =0.61803398987

Example;

Let key k = 107, assume m = 50.

A = 0.61803398987

That means 107 will be placed at index 6 in hash table.

 Advantage: The choice of m is not critical

Extraction

In this method some digits are extracted from the key to form the address location in hash table.

For example: Suppose first, third and fourth digit from left is selected for hash key.

Mid Square

This method works in following steps

1) Square the key

2) Extract middle part of the result. This will indicate the location of the key element in the hash table.

Note that if the key element is a string then it has to be preprocessed to produce a number.

Let key = 3111

For the hash table of size of 1000

H(3111)=783

Review Question

1. What is hashing function? Explain any four types of hashing functions.