Question

Double hashing is scheme for resolving collisions that uses two hash functions HCk, m) and hCk,m). It is similar to linear hashing except that instead of changing the index by 1, the value of the second hash function is used From the view of the general scheme, the Io(k, mHCk, m) Hi(k, m) -(H(k, m)+ h(k,m)) mod m H2 (k, m) = (H(k, m)+ 2 h(k,m)) mod m hash functions are. Hi (k, m) (H(k , m)+ h(k , m)) mod m values. As with linear hashing, the hash function Hi(k, m) CHi-1(k, m)+ h(k, m)) mod m can be defined in terms of the previous You must be careful when defining the second hash function.

Answer 1

Double hashing is a collision resolving technique in hashing. Double hashing used the idea of implementing second hash key when occur the collisions.

Double hashing cab be don using the following equation

(Hash1(key)+i*hash2(key)) % size of the table.

Here hash1() and hash2() are two hash functions

I is probe value

In general first hash function is hash1(key) = key % table size.

A popular second hash function is hash2(key) = any primenumber – (key % primenumber) where prime number is a prime small than the table size.

A good hash function in double hashing is

1.      Its never evaluate to zero

2.      Make sure that the all cells can be probed.

Suppose hash1(key) = key%15

            Hash2(key)=7-(key%7)

Here 7 is prime number which is less than 15.

Let us consider the following data and insert into table

10

15

8

9

12

13

14

68

88

39

86

95

28

40

42

Hash table is :

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
15			39		95			8	9	10	86	12	88	14

Above data is inserted without any collisions.

Now apply double hashing using above method

Key	Hash1 & Hash 2	Probe(i)	address	remarks
68	8	1	10	collision
	2	2	12	collision
		3	14	collision
		4	1	1 is index for 68

39	9	1	12	collision
	3	2	0	collision
		3	3	collision
		4	6	6 is index for 39

28	13	1	5	collision
	7	2	12	collision
		3	4	4 is index for 28

Implement same for 40 now it is 7

Implement same for 42 now it is 2

Finally the hash table for the given data is

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
15	68	41	39	28	95	39	40	8	9	10	86	12	88	14