¡EDouble hashing
h(k)
, h(k) + u , h(k) + 2u , ....... u = g(k) = h2(k)
Key |
A |
S |
E |
A |
R |
C |
H |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
Hash 1 |
1 |
0 |
5 |
1 |
18 |
3 |
8 |
9 |
14 |
7 |
5 |
5 |
1 |
13 |
16 |
12 |
5 |
Hash 2 |
16 |
15 |
12 |
16 |
16 |
14 |
9 |
8 |
3 |
10 |
12 |
10 |
16 |
4 |
1 |
5 |
12 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
A |
|
|
|
E |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
A |
|
|
|
E |
|
|
|
|
|
|
|
|
|
|
|
A |
|
S |
A |
|
|
|
E |
|
|
|
|
|
|
|
|
|
|
|
A |
R |
S |
A |
|
C |
|
E |
|
|
|
|
|
|
|
|
|
|
|
A |
R |
S |
A |
|
C |
|
E |
|
|
H |
|
|
|
|
|
|
|
|
A |
R |
S |
A |
|
C |
|
E |
|
|
H |
I |
|
|
|
|
|
|
|
A |
R |
S |
A |
|
C |
|
E |
|
|
H |
I |
|
|
|
|
N |
|
|
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
|
|
|
|
N |
|
|
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
E |
|
|
|
N |
|
|
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
E |
|
|
|
N |
X |
|
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
E |
A |
|
|
N |
X |
|
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
E |
A |
|
M |
N |
X |
|
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
E |
A |
|
M |
N |
X |
P |
A |
R |
S |
A |
|
C |
|
E |
|
G |
H |
I |
E |
A |
L |
M |
N |
X |
P |
A |
R |
S |
A |
|
C |
|
E |
E |
G |
H |
I |
E |
A |
L |
M |
N |
X |
P |
A |
R |
ÂŦâ²Ê±×Åé¦rªí¥Ü²Ä¤@¦¸¥X²{©Î¬O¥X²{
Collision
Performance |
Unsuccessful |
successful |
Separate chaing |
1 + (£\/ 2) |
(£\+ 1) / 2 |
Linear probing |
(1/2) + (1/ 2(1 - £\)^2) |
(1/2) + (1/2(1 - £\)) |
Double Hashing |
1 / ( 1 - £\) |
- ln(1 - £\) / £\ |
£\ = N / M ( load factor)