Konsistente Hashfunktion

Konsistentes Hashing

Eine konsistente Hash-Funktion ist eine Hash-Funktion, die die Anzahl der Neuzuordnungen minimiert. Neuzuordnungen erfolgen immer dann, wenn Behälter hinzukommnen oder entfernt werden.

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 inkonsistenen 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.

Literatur

• Hashing over Peer-to-Peer Networks (engl.)