In Hasinghow does hash function h where h is random minimize

In Hasing...how does hash function \'h\', where h is random, minimize the number of collision?

-from chapter 11.2 page 257 of Introduction to Algorithm by Thomas Cormen

Solution

Answer:

Hash function is represented as : H(k) = (p*key) mode (table_size)

Where k is the key and p is the prime number. Suppose we have given some keys with index as :

1 2 3 4 5

13 14 9 11 18

Let us use hashing function as mod10

We will take a key and divide it with 10 and take its reminder as the index of the table . After that we will place the key in the index. If we get same remainder same as before but we already placed the key to that index , that means collosion occurs. Now we make a chain with the concept of linked lists and place the key in the chain to its same index and thus reduces the number of collisions.