www.wikidata.de-de.nina.az

Divisionsrestmethode Die siehe auch Modulo liefert eine Hashfunktion Die Funktion lautet h k k mod m displaystyle h k k

Divisionsrestmethode

Die Divisionsrestmethode (siehe auch Modulo) liefert eine Hashfunktion.

Die Funktion lautet:

ist die Größe der Hashtabelle.

Eigenschaften 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 zum Beispiel die Wahl einer Zweierpotenz für , 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.

Hashing von Zeichenketten 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 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 Bearbeiten

Einzelnachweise Bearbeiten

  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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Divisionsrestmethode siehe auch Modulo liefert eine Hashfunktion Die Funktion lautet h k k mod m displaystyle h k k bmod m m displaystyle m ist die Grosse der Hashtabelle Inhaltsverzeichnis 1 Eigenschaften 2 Hashing von Zeichenketten 3 Literatur 4 EinzelnachweiseEigenschaften BearbeitenDie Hash Funktion kann sehr schnell berechnet werden Die Wahl der Tabellengrosse m displaystyle m nbsp beeinflusst die Kollisionswahrscheinlichkeit der Funktionswerte von h displaystyle h nbsp Fur die meisten Eingabedaten ist zum Beispiel die Wahl einer Zweierpotenz fur m displaystyle m nbsp also m 2 i displaystyle m 2 i nbsp ungeeignet da dies der Extraktion der i displaystyle i nbsp niedrigstwertigen Bits von k displaystyle k nbsp entspricht so dass alle hoherwertigen Bits bei der Hash Berechnung ignoriert werden Fur praxisrelevante Anwendungen liefert die Wahl einer Primzahl fur m displaystyle m nbsp welche keine Mersenne Primzahl ist eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen 1 Hashing von Zeichenketten BearbeitenZeichenketten konnen mit der Divisionsmethode gehasht werden indem sie in ganze Zahlen zur Basis b displaystyle b nbsp umgewandelt werden wobei b displaystyle b nbsp die Zeichensatzgrosse bezeichnet Um Integer Uberlaufe zu vermeiden kann fur die Berechnung des Hashwertes bei Schlusseln das Horner Schema angewendet werden Das folgende Beispiel zeigt eine Berechnung eines Hashwertes fur eine 7 Bit ASCII Zeichenkette s displaystyle s nbsp k mod m s 1 128 s 2 mod m 128 s 3 mod m 128 s l 1 mod m 128 s l mod m 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 nbsp Somit kann als Zwischenergebnis maximal m 1 128 127 displaystyle left m 1 right cdot 128 127 nbsp auftreten Dargestellt in Pseudocode Parameter naturliche Zahlen i h 0 Feld s for i 0 to i lt lange von s h h 128 s i mod m Ergebnis h Die Multiplikation mit 128 2 7 entspricht der Links Bit Shift Operation lt lt 7 Literatur BearbeitenDonald 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 Bearbeiten 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 Abgerufen von https de wikipedia org w index php title Divisionsrestmethode amp oldid 194077299