retagged by
2,553 views

2 Answers

2 votes
2 votes

Double Hashing:

It is the technique which is used in open addressing. In this, we use two hash functions. The first function used, is similar to linear probing, table size or the "key-mod" but if the collision occurs, then we apply the second hash function.

Double Hashing :→

H1(key) = key mod table size

H2(key) = M – (key mod M) * M is a Prime number, where M is a prime number less than the table size.

 

There are two conditions which need to be considered.

1. The second hash function never evaluates to be 0.

2. All cells must be probed means it must be reachable to all cells.

For example, we have:

37, 90, 45, 22, 17, 49, 55.

Indexes Values
0 90
1 17
2 22
3  
4  
5 45
6 55
7 37
8  
9 49

37 % 10 = 7

90 % 10 = 0

45 % 10 = 5

22 % 10 = 2

17 % 10 = 7 (But since, 7th location is already occupied, we will apply our second hash function now)

 

H2(17) = 7 – 17 % 7 = 4 ( We chose 7 because the prime number smaller and less than the table size of 10 is 7)

 

So, we will move 17 from the original location of 7 to the four positions ahead, that is,

7+1= 8

8+1 = 9

9+1 = 0

0+1 = 1 (We are just moving 4 positions from the current position)

 

49 % 10 = 9

 

H2(55) = 7 – (55 % 7) = 7 – 6 = 1 ( So move position from 5th location to 6)

 

edited by
1 votes
1 votes

1.Double hashing Comes under the category of open addressing.

2. As the name suggest it uses Two hash function instead of the other techniques which uses only one hash Function

3. first hash function : h(x) , second hash function let say h2(x)

First take the key and put the key in the first hash function and the index generated position is  already filled i.e Collision occours  then use the second hash function to rehash the values.

Example: h(x)%S is full then do ( h(x)+1*h2(x) )%S 

Note: here S is the table size

if ( h(x)+1*h2(x) )%S  is also full then do ( h(x)+2*h2(x) )%S  ....and so on.

This is called double hashing.

The advantage of double hashing over other techniques is that it Prevents Secondary Clustering.

 

 

Related questions

0 votes
0 votes
1 answer
1
5 votes
5 votes
2 answers
2
sunil sarode asked Dec 30, 2017
4,284 views
How many probes takes place to insert a sequence of numbers: 14, 17, 25, 37, 34, 16, 26, into a hash table of size 11, using Double hashing, where h(x) = x mod 11, h2(x) ...
6 votes
6 votes
0 answers
3
MiNiPanda asked Jan 21, 2018
2,308 views
Please explain primary and secondary clustering in brief. I tend to forget their difference because their definitions seem quite similar to me. And also, which one is tru...