Divisionsrestmethode

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Divisions-Rest-Methode)
Wechseln zu: Navigation, Suche

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

Die Funktion lautet:

ist die Größe der Hashtabelle.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

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

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

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

Hashing von Zeichenketten[Bearbeiten | Quelltext bearbeiten]

Zeichenketten können mit der Divisionsmethode gehasht werden, indem sie in ganze Zahlen zur Basis umgewandelt werden, wobei 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 .

Somit kann als Zwischenergebnis maximal 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-Bit-Shift-Operation << 7.

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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