Konsistente Hashfunktion

Eine konsistente Hashfunktion ist eine Hashfunktion, die die Anzahl der Neuzuordnungen minimiert. Neuzuordnungen erfolgen immer dann, wenn Behälter hinzukommen oder entfernt werden.

Oben: Ausgangsverteilung, dann Entfernung des dritten Behälters. Neuordnung bei inkonsistentem (Mitte) bzw. Umordnung bei konsistentem Hashing (unten)

Das Bild zeigt im oberen Bereich eine Verteilung von Schlüsseln auf Behälter. Wird nun ein Behälter entfernt, wie im mittleren Bildbereich geschehen, so werden bei Gebrauch einer inkonsistenten Hash-Funktion alle Schlüssel neu auf die nun verfügbaren Behälter verteilt. Verwendet man jedoch eine konsistente Hash-Funktion, wie im unteren Bereich gezeigt, so werden nur die Schlüssel des entfernten Behälters auf die umliegenden Behälter verteilt. Alle anderen Behälter bleiben unberührt.

Konsistente Hash-Funktionen haben folgende Eigenschaften:

• Einwegberechenbarkeit
• Kollisionsresistenz
• Gleichverteiltheit
• effiziente Berechenbarkeit

Konsistente Hash-Funktionen sind Grundlage verteilter Hashtabellen.