Divisions-Rest-Methode

Divisions-Rest-Methode

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.

Inhaltsverzeichnis

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 = 2i, 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 nicht zu nah an einer Zweierpotenz liegt, 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.

In Pseudocode würde dies in etwa so aussehen:

h = s[1] mod m
for i in 2...l:
   h = (h * 128 + s[i]) mod m

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


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hasch-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hasch-Verfahren — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Algorithmus — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Wert — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashcode — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashen — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashing — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashwert — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Kollisionsfreiheit — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”