Multiplikative Methode

Die multiplikative Methode ist eine Hash-Funktion. Bei der multiplikativen Methode wird das Produkt des Schlüssels mit einer Zahl $\phi$ 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$ multiplizert und nach unten abgerundet, d. h.

$h(k)=\lfloor m(k\phi -\lfloor k\phi \rfloor )\rfloor .$

Entscheidend für die Verteilung der Schlüssel auf den Adressbereich der Hashtabelle ist bei dieser Methode die Wahl von $\phi$, die unabhängig von der Wahl von $m$ ist. In der Literatur wird der Goldene Schnitt für eine gute Wahl von $\phi$ vorgeschlagen [1c] (Seite 516), [2], mit dem ähnliche Ergebnisse wie mit der Gleichverteilung erreicht werden.

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

Die multiplikative Methode lässt sich auch als Verallgemeinerung der Divisionsrestmethode sehen. Setzt man $\phi ={\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 $\omega$ 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$ ("eine echte reelle Zahl", wie z.B. auch $e$ und $\pi$). Der goldene Schnitt erreicht eine gute Verteilung der Schlüssel auf den Adressbereich der Hashtabelle durch folgende Eigenschaft von irrationalen Zahlen:

Sei $\phi$ eine irrationale Zahl. Platziert man die Punkte $\phi -\lfloor \phi \rfloor ,2\phi -\lfloor 2\phi \rfloor ,3\phi -\lfloor 3\phi \rfloor ,\ldots ,n\phi -\lfloor n\phi \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)\phi -\lfloor (n+1)\phi \rfloor$, in einen der größten Intervallteile. (Vera Turan Sos (Acta Math. Acad. Sci. Hung. 8 (1957), 461-471))

Nun sollte man aus der Mathematik wissen: Jede rationale Zahl lässt sich als Dezimalbruch bzw. Dualbruch darstellen. Jeder periodische Dezimalbruch, bzw. Dualbruch stellt eine rationale Zahlen 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 Zahle lässt sich nur durch einen nicht periodischen unendlichen Dezimalbruch, bzw. Dualbruch darstellen. Ist $\phi$ aus $R\setminus Q$so lässt es sich als Grenzwert eines $b$-$a$-dischen Bruches darstellen.

Die Gleichverteilung als auch der goldene Schnitt lassen sich somit nur näherungsweise durch Algorithmen erreichen.

Dadurch erhält man folgendes Ergebnis:

Die Gleichverteilung erreicht man nur unzureichende 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 wohl auf beliebig viele Stelle genau berechen 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 Sos 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 Schitt eine gute Wahl für die multiplikative Methode.

Es wurden noch viele andere Methoden vorgeschlagen (siehe Hash-Funktion). Lum, Yuen und Dodd [3] haben das Verhalten verschiedener Hash-Funtions-Methoden miteinander verglichen und stellten fest, dass die Divisionsrestmethode im Allgemeinen nicht schlechtere Resultate als andere Hash-Funktionen liefert.

Implementation

Die allgemeine Form der Implementation in C sieht wie folgt aus:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define      m  1024             /* Anzahl der Hashtabellenadressen                            */
#define      A  2654435761.0     /* \phi = A/W                                                 */
#define      w  4294967296.0     /* w =2^32 => A =>  2654435761.0 / 4294967296.0 = 0.618033987 */


unsigned long int multiplication_hash(unsigned long int Key)
{ 
  return((unsigned long int) floor( ( ((double)m) * fmod( ((((double)A)*((double)Key))),((double)w)) ) / ((double)w) ) ); 
}

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define    m  10           /* m = 2^10 = 1024           */
#define    w  32           /* bitsizeof (unsigned int)  */
#define    A  2654435761   /*                           */

unsigned long int multiplication_hash(unsigned long int Key)
{
  return((A * Key) >> (w - m));
}

Literatur

[1a] Donald E. Knuth. The Art of Computer Programming/Fundamental Algorithms. Volume 1. Addison-Wesley, Massachusetts, 3rd edition, 1997.

[1b] Donald E. Knuth. The Art of Computer Programming/Seminumerical Algorithms, Volume 2. Addison-Wesley, Massachusetts, 3rd edition, 1997.

[1c] Donald E. Knuth. The Art of Computer Programming/Sorting and Searching. Volume 3.Addison-Wesley, Massachusetts, 2rd edition, 1997.

[2] Thomas Ottmann and Peter Widmayer. Algorithmen und Datenstrukturen. B.I. Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich, zweite Edition, 1993.

[3] V. Y. Lum, P. S. T. Yuen, and M. Dodd. Key-to-adress transform techniques: Performance study on large existing formatted files. Communications of the ACM, 14(4):228--239, April 1971.

[4] William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C++/ The Art of Scientific Computing. Cambridge University Press, 2nd edition, 1988.