Divisionsrestmethode

Die Divisionsrestmethode (siehe auch Modulo) liefert eine Hashfunktion.

Die Funktion lautet: ${\displaystyle h(k)=k{\bmod {m}}}$

${\displaystyle m}$ ist die Größe der Hashtabelle.

Eigenschaften

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

Für die meisten Eingabedaten ist zum Beispiel die Wahl einer Zweierpotenz für ${\displaystyle m}$, also ${\displaystyle m=2^{i}}$, ungeeignet, da dies der Extraktion der ${\displaystyle i}$-niedrigstwertigen Bits von ${\displaystyle 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 ${\displaystyle m}$, welche keine Mersenne-Primzahl ist, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen.^[1]

Hashing von Zeichenketten

Zeichenketten können mit der Divisionsmethode gehasht werden, indem sie in ganze Zahlen zur Basis ${\displaystyle b}$ umgewandelt werden, wobei ${\displaystyle 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 eine 7-Bit-ASCII-Zeichenkette ${\displaystyle s}$.

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

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

Dargestellt in Pseudocode:

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

Die Multiplikation mit 128 = 2^7 entspricht der Links-Bit-Shift-Operation << 7.

Literatur

• Donald E. Knuth: The Art of Computer Programming. Band 3: Sorting and Searching. 2nd edition. Addison-Wesley, Upper Saddle River NJ unter anderem 1998, ISBN 0-201-89685-0, S. 515.

Einzelnachweise

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press unter anderem, Cambridge MA unter anderem 2001, ISBN 0-262-03293-7, S. 231.