|
Benötigt wird eine Funktion, die Schlüssel (für gewöhnlich ganze Zahlen oder kurze Zeichenfolgen) in ganze Zahlen aus dem Intervall [0 ... M-1] transformiert, wobei M die Anzahl von Datensätzen ist, die in dem verfügbaren Speicher untergebracht werden kann.
Hierfür werden in der Literatur eine Vielzahl von Hash-Algorithmen vorgeschlagen. Eine der bekanntesten Funktionen ist das Divisionsrestverfahren.
Hier ist für M eine günstige Primzahl zu wählen, so daß für den beliebigen Schlüssel k der Wert des Schlüssels nach der Formel h(k) = k mod M berechnet wird. Dies ist ein sehr einfaches Verfahren, das sich häufig leicht realisieren läßt und eine gute Verteilung der Schlüssel ergibt.
Beispiel: Gegeben ist eine Tabelle mit einer Größe M=101. Mit Hilfe der oben stehenden Hash-Funktion soll für den vierstelligen Schlüssel \" A KEY\" die Tabellenadresse berechnet werden.
Als erstes muß der Schlüssel in eine Zahl codiert werden:
Schlüssel
A K E Y
Alphabetpos.
1 11 5 25
Pos. in Binärzahl
00001 01011 00101 11001
Hieraus ergibt sich die Binärzahl 00001010110010111001 = 44217
44217 mod 101 = 80
Somit wird der Schlüssel A KEY an die, von der Hash-Funktion berechneten, Position 80 in der Tabelle abgebildet.
|
