|
Die Hash-Funktion ist eine mathematische Funktion, die aus dem Schlüssel eines Datensatzes einen Index für die Hash-Tabelle errechnet.
Diese Funktion soll so gewählt werden, daß
. die Daten so abgebildet werden, daß der Grenzwertindex nicht überschritten wird,
. die Daten möglichst gleich über die Hash-Tabelle verteilt sind und
. es zu möglichst wenigen Kollisionen kommt.
Zurück zum Inhaltsverzeichnis
3. 1. Geeignete Hash-Funktionen für Zahlen
Wenn der Schlüssel eines Datensatzes eine Zahl ist, so wird als Hash-Funktion meist das Divisionsrestverfahren bzw. eine etwas modifizierte Variante davon angewendet:
H(K) = K mod M
H(K) ist die Hash-Funktion, K der Schlüsselwert und M die Größe des Arrays.
Um die Kollisionsbearbeitung (siehe weiter unten) zu erleichtern, sollte für M nach Möglichkeit eine Primzahl gewählt werden.
Zurück zum Inhaltsverzeichnis
3. 2. Geeignete Hash-Funktionen für Zeichenketten
Die naheliegendste Lösung für Zeichenketten ist wohl, die Quersumme über die ASCII-Codes der einzelnen Zeichen zu bilden und auf das Ergebnis das Divisionsrestverfahren anzuwenden.
Weiters könnte man die ganze Zeichenkette als Zahl interpretieren und auf diese Zahl wiederum das Divisionsrestverfahren anwenden. Der Nachteil dabei ist allerdings, daß dabei relativ hohe Zahlen entstehen (z. B.: KARLI = 0x4B41524C49).
Um das zu verhindern, sollte man nach jedem Buchstaben die Modulu-Operation anwenden:
A = 65, I = 73, K = 75, L = 76, R = 82
Größe der Hash-Tabelle = 499
K: 75 mod 499 = 75
A: (75 * 256 + 65) mod 499 = 303
R: (303 * 256 + 82) mod 499 = 305
L: (305 * 256 + 76) mod 499 = 312
I: (312 * 256 + 73) mod 499 = 105
Der Datensatz mit dem Schlüsselwert \"KARLI\" wird somit in der Hash-Tabelle am Speicherplatz 105 gespeichert.
Beispiel für Implementierung:
unsigned int hash (char *key, unsigned int m)
{
int h;
for (h = 0; *key != \'\\0\'; key++) h = (256 * h + *key) % m;
return (h);
}
Hinweis: \"key\" ist der Schlüsselbegriff, \"m\" die Größe der Hash-Tabelle.
|
