Double hashing is scheme for resolving collisions that uses two hash functions H
ID: 3731674 • Letter: D
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.Explanation / Answer
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
10
15
8
9
12
13
14
68
88
39
86
95
28
40
42
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.