Page 197 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes The hash table therefore is the one shown below:

0
1 45

2 101
3 25

4 102

5 201
6

7
8 96

9 162
10 197

Task ”A Hash Function must be deterministic and stateless.” Discuss.

9.2 Hash Functions

Some of the methods of defining hash function are discussed below:

1. Modular arithmetic: In this method, first the key is converted to integer, then it is divided

by the size of index range, and the remainder is taken to be the hash value. The spread
achieved depends very much on the modulus. If modulus is power of small integers like 2
or 10, then many keys tend to map into the same index, while other indices remain unused.
The best choice for modulus is often but not always is a prime number, which usually has
the effect of spreading the keys quite uniformly.
2. Truncation: This method ignores part of key, and use the remainder part directly as hash
value. (considering non-numeric fields as their numerical code) If the keys for example

are eight digit numbers and the hash table has 1000 entries, then the first, second, and fi fth
digit from right might make hash value. So 62538194 maps to 394. It is a fast method, but
often fails to distribute keys evenly.

3. Folding: In this method, the identifier is partitioned into several parts all but the last part
being of the same length. These parts are then added together to obtain the hash value.
For example an eight digit integer can be divided into groups of three, three, and two
digits. The groups are the added together, and truncated if necessary to be in the proper
range of indices. Hence 62538149 maps to, 625 + 381 + 94 = 1100, truncated to 100. Since all
information in the key can affect the value of the function, folding often achieves a better
spread of indices than truncation.
4. Mid square method: In this method, the identifier is squared (considering non-numeric

fi elds as their numerical code), and then the appropriate number of bits from the middle

192 LOVELY PROFESSIONAL UNIVERSITY