Konsistente Hash-Funktion

Konsistente Hash-Funktion
Oben: Ausgangsverteilung, dann Entfernung des dritten Behälters. Neuordnung bei inkonsistentem (mitte) bzw. Umordnung bei konsistentem Hashing (unten)

Eine konsistente Hash-Funktion ist eine Hashfunktion, die die Anzahl der Neuzuordnungen minimiert. Neuzuordnungen erfolgen immer dann, wenn Behälter hinzukommen 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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Distributed Hash Table — Eine verteilte Hashtabelle (VHT) [engl.: distributed hash table (DHT)] ist eine Datenstruktur, die versucht, das allgemeine Problem in P2P Systemen – das Finden des Speicherorts einer gesuchten Datei – mit möglichst geringem Aufwand effizient zu… …   Deutsch Wikipedia

  • Distributed Hashtable — Eine verteilte Hashtabelle (VHT) [engl.: distributed hash table (DHT)] ist eine Datenstruktur, die versucht, das allgemeine Problem in P2P Systemen – das Finden des Speicherorts einer gesuchten Datei – mit möglichst geringem Aufwand effizient zu… …   Deutsch Wikipedia

  • Verteilte Hashtabelle — Eine verteilte Hashtabelle (engl. distributed hash table, DHT) ist eine Datenstruktur, die zum Beispiel dazu genutzt werden kann, den Speicherort einer Datei in einem P2P System zu speichern. Dabei steht die Dezentralisierung und die Effizienz… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”