Divisionsrestmethode

Die Divisions-Rest-Methode (siehe auch Modulo) liefert eine Hash-Funktion.

Die Funktion lautet: $h(k) = k \mod m$

m ist die Größe der Hashtabelle.

Eigenschaften

1. Die Hash-Funktion kann sehr schnell berechnet werden
2. Die Wahl der Tabellengröße m beeinflusst die Kollisionswahrscheinlichkeit der Funktionswerte von h.

Für die meisten Eingabedaten ist z.B. die Wahl einer Zweierpotenz für m, also m = 2ⁱ, ungeeignet, da dies der Extraktion der i-niedrigstwertigen Bits von k entspricht, so dass alle höherwertigen Bits bei der Hash-Berechnung ignoriert werden.

Für praxisrelevante Anwendungen liefert die Wahl einer Primzahl für m, welche keine Mersenne-Primzahl ist, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen^[1].

Hashing von Strings

Strings können mit der Divisionsmethode gehasht werden, indem die Zeichenketten in ganze Zahlen zur Basis b umgewandelt werden, wobei b die Zeichensatzgröße bezeichnet.

Um Integer-Überläufe zu vermeiden, kann für die Berechnung des Hashwertes bei Schlüsseln das Horner-Schema angewendet werden. Das folgende Beispiel zeigt eine Berechnung eines Hashwertes für einen 7-Bit ASCII-String s.

$k \mod m = (\ldots (s_{1} \cdot 128 + s_{2}) \mod m) \cdot 128 + s_{3}) \mod m) \cdot 128 + \ldots + s_{l-1}) \mod m) \cdot 128 + s_{l}) \mod m$

Somit kann als Zwischenergebnis maximal $\left(m - 1\right) \cdot 128 + 127$ auftreten.

dargestellt in Pseudocode:

Parameter: natürliche Zahlen i, h=0; Feld s
1. for i = 0 to i < länge_von(s) 
2.      h = (h * 128 + s[i]) mod m;
Ergebnis: h.

Die Multiplikation mit 128 = 2^7 entspricht der Links-Bitshiftoperation << 7.

Einzelnachweise

1. ↑ Cormen et. al.: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, ISBN 0-262-03293-7, S. 231.

Literatur

• Donald E. Knuth: The Art of Computer Programming Volume 3. 2. Auflage. Addison Wesley, 1998, ISBN 0-201-89685-0, S. 515.