Multiplikative Methode

Schema für Hashfunktionen

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

Algorithmus

Bearbeiten

Entscheidend für die Verteilung der Schlüssel auf den Adressbereich der Hashtabelle ist bei dieser Methode die Wahl von  , die unabhängig von der Wahl von   ist. In der Literatur wird der Goldene Schnitt für eine gute Wahl von   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.

 

Die multiplikative Methode lässt sich als Verallgemeinerung der Divisionsrestmethode sehen. Setzt man  , so ist

 

In der Theorie des Hashens wird durch die Gleichverteilung der Schlüssel auf die Adressen der Hashtabelle üblicherweise 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  , wenn   ein Elementarereignis ist und   die Anzahl der Elementarereignisse, z. B. der Münzwurf   oder der Würfel  .

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

Sei   eine irrationale Zahl. Platziert man die Punkte   in das Intervall  , dann haben die   Intervallteile höchstens drei verschiedene Längen. Außerdem fällt der nächste Punkt,  , 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.   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   aus  , so lässt es sich als Grenzwert eines  - -dischen Bruches darstellen.

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

Bewertung

Bearbeiten

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   verteilt werden.

Da man allgemein in der Praxis 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 unterschiedlicher Hashfunktionen miteinander verglichen und stellten fest, dass die Divisionsrestmethode statistisch keine schlechteren Resultate als andere Hash-Funktionen liefert.[4]

Implementierung

Bearbeiten

Sei beispielsweise   mit  . Dann ist  .

Dann lautet die zugehörige multiplikative Hash-Funktion  

 

wobei   mit   die Hashtablegröße und   mit   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   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

Bearbeiten

Einzelnachweise

Bearbeiten
  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, Peter Widmayer: Algorithmen und Datenstrukturen. zweite Edition. B.I. Wissenschaftsverlag, Mannheim / Leipzig / Wien / Zürich 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, M. Dodd: Key-to-address transform techniques: Performance study on large existing formatted files. In: Communications of the ACM, 14(4), April 1971, S. 228–239.