|
Das doppelte Hashing verwendet die Methode der internen Kollisionsauflösung mit dem Ziel, Clusterbildung zu vermeiden. Das wird erreicht, indem nicht, so wie beim linearen Austesten, bei einer Kollision immer ein konstanter Betrag addiert wird, sondern ein vom Schlüssel abhängiger Wert.
Beispiel:
H2(K) = 1 + (K / M) mod (M - 1)
K ist der Schlüsselwert, M die Größe der Hash-Tabelle.
Bei der Division (K / M) handelt es sich um eine Ganzzahldivision.
Beispiel:
Die Hash-Tabelle bietet Platz für 11 Datensätze.
Schlüsselwerte sind Ganzzahlen (\"Personen-ID\").
Wenn Plätze nicht belegt sind, werden die Personen-ID und der berechnete Index auf -1 gesetzt.
1. Hash-Funktion: H(K) = K mod M
2. Hash-Funktion: H2(K) = 1 + (K / M) mod (M - 1)
. Einfügen:
37, Huber (Hashcode 4)
25, Meier (3)
20, Schmidt (9)
54, Gruber (10)
42, Stangl (9): H2(42) = 4
tatsächlicher Index berechneter Index Personen-ID Name Anz. Elemente mit diesem Hashcode
0 -1 -1 0
1 -1 -1 0
2 9 42 Stangl 0
3 3 25 Meier 1
4 4 37 Huber 1
5 -1 -1 0
6 -1 -1 0
7 -1 -1 0
8 -1 -1 0
9 9 20 Schmidt 2
10 10 54 Gruber 1
. Einfügen:
11, Böck (Hashcode 0)
15, Richter (4): H2(15) = 2
31, Wagner (9): H2(31) = 3
4, Steiner (4): H2(4) = 1
tatsächlicher Index berechneter Index Personen-ID Name Anz. Elemente mit diesem Hashcode
0 0 11 Böck 1
1 9 31 Wagner 0
2 9 42 Stangl 0
3 3 25 Meier 1
4 4 37 Huber 3
5 4 4 Steiner 0
6 4 15 Richter 0
7 -1 -1 0
8 -1 -1 0
9 9 20 Schmidt 3
10 10 54 Gruber 1
. Löschen:
15, Richter (Hashcode 4)
. Einfügen:
16, Bauer (5): H2(16) = 2
. Löschen:
42, Stangl (9)
tatsächlicher Index berechneter Index Personen-ID Name Anz. Elemente mit diesem Hashcode
0 0 11 Böck 1
1 9 31 Wagner 0
2 -1 -1 Stangl 0
3 3 25 Meier 1
4 4 37 Huber 2
5 4 4 Steiner 1
6 -1 -1 Richter 0
7 5 16 Bauer 0
8 -1 -1 0
9 9 20 Schmidt 2
10 10 54 Gruber 1
Die durchschnittliche Anzahl der Zugriffe beim Suchen nach einem Datensatz, der tatsächlich in der Tabelle existiert, berechnet sich bei diesem Verfahren nach folgender Formel:
-ln (1 - Auslastung) / Auslastung
Beim erfolglosen Suchen:
1 / (1 - Auslastung)
Beispiele:
Auslastung 50 % 70 % 80 %
durchschn. Zugriffe bei erfolgloser Suche 2,0 3,3 5,0
durchschn. Zugriffe bei erfolgreicher Suche 1,4 1,7 2,0
|
