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

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

Kategorie:
Hash

Игры ⚽ Поможем написать реферат

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

Academic dictionaries and encyclopedias