266. What is a hash function? Describe any three hash functions.

Ans:
Hash function : This is the function from the set 'K' of keys into the set 'L' of
memory addresses.
H : K
L
These are used to determine the address of a record with the use of some key. Such a
function 'H' may not yield distinct values: it is possible that two diff keys Kl and K2
will yield the same hash address;
This situation is called collision and some method must be used to resolve it.
Examples
1. Division method: Choose a number 'm' larger than the number 'n' of keys in K:
(The number m is usually chosen to be a prime number). The hash function 'H' is
defined by
H(K)= k (mod m)
Where K(mod m ) denotes the remainder when 'K' is divided by m.
2. Midsquare method: The key 'K' is squared, then the hash function 'H' is defined
by
H (K) =1 Where 1 is obtained by deleting digits from both
ends of K2.
3. Folding Method: The key 'K' is partitioned into a no. of parts k1, k2,……kT,
Where each part except , possibly the last, has the same number of digits as the
required address. Then the parts are added together, ignoring the last carry, that is
H (k) = k1, k2,……kT,. Where the leading digits carries, if any, are ignored.