Multiplikative Methode

Die multiplikative Methode ist ein Schema, nachdem Hash-Funktionen entwickelt werden können. Dabei wird das Produkt des Schlüssels mit einer Zahl A gebildet und der ganzzahlige Anteil abgeschnitten, so dass der Schlüssel in das Intervall [0,1] abgebildet wird. Das Ergebnis wird mit der Anzahl der Hashtabellenadressen m multipliziert und nach unten abgerundet. In Formelschreibweise ist eine Hash-Funktion h, die die multiplikative Methode implementiert, definiert als:

$h(k) = \lfloor m(kA\mod 1)\rfloor = \lfloor m (k A - \lfloor k A \rfloor)\rfloor,\qquad 0<A<1$

Algorithmus

Entscheidend für die Verteilung der Schlüssel auf den Adressbereich der Hashtabelle ist bei dieser Methode die Wahl von A, die unabhängig von der Wahl von m ist. In der Literatur wird der Goldene Schnitt für eine gute Wahl von A vorgeschlagen^[1][2], mit dem in der Praxis mit vielen typischen Eingabedaten die Verteilung der Hash-Werte der Schlüssel nahezu gleichverteilt ist. Wird diese Zahl verwendet, so nennt man die resultierende Hash-Funktion auch den Fibonacci-Hash.

$A = \Phi^{-1} = \frac{\sqrt{5} - 1}{2} \approx 0{,}6180339887 \ldots$

Die multiplikative Methode lässt sich als Verallgemeinerung der Divisionsrestmethode sehen. Setzt man $A = \frac{1}{m}$ so ist

$h(k) = \left \lfloor m \left( k \frac{1}{m} - \left\lfloor k \frac{1}{m} \right\rfloor \right) \right\rfloor = \left \lfloor m \left ( \left(k \frac{1}{m} \right) \ \bmod \ 1 \right) \right\rfloor = \left\lfloor m \frac{(k \ \bmod \ m)}{m} \right\rfloor = k \ \bmod \ m$

In der Theorie des Hashens wird durch die Gleichverteilung der Schlüssel auf die Adressen der Hashtabelle im Allgemeinen versucht die Schlüssel gleichmäßig auf die Tabelle zu verteilen und dadurch eine Minimierung von Kollisionen zu erreichen.

Die Gleichverteilung ist ein Zufallsexperiment mit der Wahrscheinlichkeit $P(\omega)=\frac{1}{n}$, wenn ω ein Elementarereignis ist und n die Anzahl der Elementarereignisse, z.B. der Münzwurf $p=\frac{1}{2}$ oder der Würfel $p= \frac{1}{6}$.

Der goldene Schnitt ist eine irrationale Zahl, d.h. sie ist aus $R \setminus Q$, und er erreicht eine gute Verteilung der Schlüssel auf den Adressbereich der Hashtabelle durch folgende Eigenschaft von irrationalen Zahlen:

Sei A eine irrationale Zahl. Platziert man die Punkte $A - \lfloor A \rfloor, 2A - \lfloor 2A \rfloor, 3A - \lfloor 3A \rfloor, \ldots, nA - \lfloor nA \rfloor$ in das Intervall [0,1], dann haben die n + 1 Intervallteile höchstens drei verschiedene Längen. Außerdem fällt der nächste Punkt, $(n+1) A - \lfloor (n+1) A \rfloor$, in einen der größten Intervallteile.^[3]

Jeder periodische Dezimalbruch bzw. Dualbruch stellt eine rationale Zahl dar. Natürliche oder rationale Zahlen mit endlich vielen Stellen, z. B. $\frac{1}{2}=0.5$ sind 0-periodisch, d. h. man setzt die restlichen unendlichen Stellen gleich 0.

Jede irrationale Zahl lässt sich nur durch einen nicht periodischen unendlichen Dezimalbruch bzw. Dualbruch darstellen. Ist A aus $R \setminus Q$, so lässt es sich als Grenzwert eines b-a-dischen Bruches darstellen.

Die Gleichverteilung und der goldene Schnitt lassen sich somit nur näherungsweise durch Algorithmen errechnen.

Bewertung

Die Gleichverteilung erreicht man nur unzureichend, und dadurch werden die Schlüssel, gerade von gut sortierten Mengen (z.B. 1, 2, 3, ..), ungleichmäßig auf die Hashtabelle verteilt, was lange Ketten und leere Adressplätze zur Folge haben kann und damit einen langsameren Zugriff auf die Daten.

Den goldenen Schnitt kann man auf beliebig viele Stellen genau berechnen und damit gut annähern, hat jedoch das Problem, dass gleichverteilte Mengen nicht optimal auf die Hashtabelle verteilt werden, da nach dem Satz von Vera Turan Sós^[3] nur gut sortierte Mengen optimal zwischen [0,1] verteilt werden.

Da man in der Praxis im Allgemeinen weder gleichverteilte noch sortierte Mengen vorfindet, ist der goldene Schnitt eine gute Wahl für die multiplikative Methode.

Lum, Yuen und Dodd haben das Verhalten verschiedener Hashfunktionen miteinander verglichen und stellten fest, dass die Divisionsrestmethode im Allgemeinen keine schlechteren Resultate als andere Hash-Funktionen liefert.^[4]

Implementierung

Sei beispielsweise $A = s/w = (\sqrt{5}-1)/2 = 0.6180339887$ mit w = 2³². Dann ist s = 2654435769.

Dann lautet die zugehörige multiplikative Hash-Funktion h

$h(k) = \left\lfloor m (\frac{ks}{w} \mod 1) \right\rfloor = \left\lfloor m \frac{ks \mod w}{w} \right\rfloor$

wobei m mit 0 < m < 2³² − 1 die Hashtablegröße und k mit $0\le k<2^{32}$ einen Schlüsselwert bezeichnen.

Eine allgemeine Implementierung in der Programmiersprache C:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <inttypes.h>
 
static const double s = 2654435769.0,  w = 4294967296.0;
 
uint32_t mult_hash(uint32_t k, uint32_t m)
{
  return (uint32_t) floor( ( (double) m * fmod( s * (double) k, w) ) / w );
} 
 
int main(int argc, char **argv)
{
  uint32_t l = mult_hash(atoi(argv[1]), 1024);
  printf("%" PRIu32 "\n", l);
  return 0;
}

Wählt man m = 2ⁱ als Zweierpotenz, so lässt sich der Algorithmus wesentlich effizienter Implementieren:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <inttypes.h>
 
static const uint32_t s = 2654435769;  
 
uint32_t mult_hash(uint32_t kk, uint32_t i)
{
  uint64_t k = kk;
  uint64_t t = s * k & 0x00000000FFFFFFFF;
  return t >> (32 - i);
}
 
int main(int argc, char **argv)
{ 
  uint32_t l = mult_hash(atoi(argv[1]), 10);
  printf("%" PRIu32 "\n", l);
  return 0;
}

Literatur

• Donald E. Knuth: The Art of Computer Programming Volume 2. 3. Auflage. Addison Wesley, 1998, ISBN 0-201-89684-2, S. 70 ff.
• Donald E. Knuth: The Art of Computer Programming Volume 3. 2. Auflage. Addison Wesley, 1998, ISBN 0-201-89685-0, S. 516 ff.
• Cormen et. al.: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, ISBN 0-262-03293-7, S. 231 ff.
• William H. Press, Saul A. Teukolsky, William T. Vetterling und Brian P. Flannery: Numerical Recipes in C++ / The Art of Scientific Computing. Cambridge University Press, 2nd edition, 1988.

Einzelnachweise

1. ↑ Donald E. Knuth: The Art of Computer Programming / Sorting and Searching. Volume 3. Addison-Wesley, Massachusetts, 2rd edition, 1997; Seite 516
2. ↑ Thomas Ottmann und Peter Widmayer: Algorithmen und Datenstrukturen. B.I. Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich, zweite Edition, 1993
3. ↑ ^{a b} Vera Turan Sós (Acta Math. Acad. Sci. Hung. 8 (1957), 461–471)
4. ↑ V. Y. Lum, P. S. T. Yuen und M. Dodd: Key-to-address transform techniques: Performance study on large existing formatted files. Communications of the ACM, 14(4):228--239, April 1971.