Divisionsrestmethode
# Divisionsrestmethode

Die Divisionsrestmethode (siehe auch Modulo) liefert eine Hashfunktion.

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

$m$ ist die Größe der Hashtabelle.

## Eigenschaften

* Die Hash-Funktion kann sehr schnell berechnet werden
* Die Wahl der Tabellengröße $m$ beeinflusst die Kollisionswahrscheinlichkeit der Funktionswerte von $h$.

Für die meisten Eingabedaten ist zum Beispiel die Wahl einer Zweierpotenz für $m$, also $m=2^{i}$, 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 keine Mersenne-Primzahl ist, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen.

## Hashing von Zeichenketten

Zeichenketten können mit der Divisionsmethode gehasht werden, indem sie 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 eine 7-Bit-ASCII-Zeichenkette $s$.

$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 $\left(m-1\right)\cdot 128+127$ auftreten.

Dargestellt in Pseudocode:

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

