imported>HilberTraum: /* Hashing von Zeichenketten */ das kann doch ganz raus, oder?

2019-11-15T18:51:45Z

Hashing von Zeichenketten: das kann doch ganz raus, oder?

Neue Seite

Die '''Divisionsrestmethode''' (siehe auch [[Modulo]]) liefert eine [[Hashfunktion]].

Die Funktion lautet:
<math>h(k) = k \bmod m</math>

<math>m</math> ist die Größe der Hashtabelle.

== Eigenschaften ==
# Die Hash-Funktion kann sehr schnell berechnet werden
# Die Wahl der Tabellengröße <math>m</math> beeinflusst die Kollisionswahrscheinlichkeit der Funktionswerte von <math>h</math>.

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

Für praxisrelevante Anwendungen liefert die Wahl einer [[Primzahl]] für <math>m</math>, welche keine [[Mersenne-Primzahl]] ist, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen.<ref>{{Literatur
| Autor=Thomas H. Cormen, [[Charles E. Leiserson]], [[Ronald L. Rivest]], Clifford Stein
| Titel=Introduction to Algorithms
| Verlag=MIT Press unter anderem
| Ort=Cambridge MA unter anderem
| Auflage=2.
| Jahr=2001
| ISBN=0-262-03293-7
| Seiten=231
}}
</ref>

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

<math>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</math>

Somit kann als Zwischenergebnis maximal <math>\left(m - 1\right) \cdot 128 + 127</math> auftreten.

Dargestellt in [[Pseudocode]]:

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

Die Multiplikation mit <code>128 = 2^7</code> entspricht der Links-[[Bitweise Verschiebung|Bit-Shift-Operation]] <code><< 7</code>.

== 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 ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Hash]]

Divisionsrestmethode - Versionsgeschichte

imported>HilberTraum: /* Hashing von Zeichenketten */ das kann doch ganz raus, oder?