Hash-Tabellen

Eine Hash-Tabelle implementiert ein Wörterbuch, indem sie eine Hash-Funktion verwendet, um Schlüssel auf Array-Positionen abzubilden, was bei gut verwalteten Kollisionen eine erwartete konstante Zeit für das Einfügen, Löschen und Nachschlagen unterstützt.

Definition

Eine Hash-Tabelle ist eine Datenstruktur, die Schlüssel-Wert-Paare in einem Array speichert, wobei eine Hash-Funktion verwendet wird, um aus jedem Schlüssel einen Index in das Array zu berechnen, mit einem Kollisionsauflösungsschema, um unterschiedliche Schlüssel zu behandeln, die auf denselben Index hashen.

Scope

Dieses Thema behandelt Hashing-basierte Wörterbücher: Hash-Funktionen und ihre wünschenswerten Eigenschaften, Strategien zur Kollisionsauflösung (separate Verkettung und offene Adressierung), Lastfaktor und Größenänderung, die universellen und perfekten Hashing-Frameworks, die nachweisbare Garantien bieten, sowie verwandte probabilistische Strukturen wie Bloom-Filter. Ausgeschlossen sind geordnete Wörterbuchstrukturen, die unter Suchbäumen behandelt werden.

Core questions

• Was macht eine Hash-Funktion gut und wie wird sie gewählt, um Schlüssel gleichmäßig zu verteilen?
• Wie werden Kollisionen durch Verkettung oder offene Adressierung aufgelöst und wie beeinflussen sie die Kosten?
• Wie steuert der Lastfaktor die erwartete Operationszeit und löst eine Größenänderung aus?
• Wie bieten universelles und perfektes Hashing nachweisbare Leistungsgarantien?
• Wann ist eine speichereffiziente probabilistische Struktur wie ein Bloom-Filter einer exakten Tabelle vorzuziehen?

Key concepts

• Hash-Funktion
• separate Verkettung
• offene Adressierung
• Lastfaktor
• Rehashing und Größenänderung
• universelles Hashing
• perfektes Hashing
• Bloom-Filter

Key theories

Universelles Hashing

Durch die zufällige Auswahl der Hash-Funktion aus einer sorgfältig entworfenen (universellen) Familie kann eine geringe erwartete Anzahl von Kollisionen für jede feste Menge von Schlüsseln garantiert werden, wodurch Worst-Case-Angriffe unwahrscheinlich werden.

Kollisionsauflösung und Lastfaktor

Die separate Verkettung speichert kollidierende Schlüssel in Listen pro Slot, während die offene Adressierung alternative Slots sondiert; die erwartete Operationszeit wird durch den Lastfaktor (Einträge pro Slot) bestimmt, und Tabellen werden in ihrer Größe angepasst, um diesen begrenzt zu halten.

Clinical relevance

Hash-Tabellen gehören zu den am häufigsten verwendeten Datenstrukturen in der Informatik: Sie implementieren Wörterbücher und Mengen in Standardbibliotheken, treiben Datenbankindizierung und In-Memory-Caches an, unterstützen Symboltabellen in Compilern und bilden die Grundlage für Deduplizierung und Mitgliedschaftstests. Bloom-Filter skalieren Mitgliedschaftsabfragen in Datenbanken und Netzwerken, wo eine exakte Speicherung nicht praktikabel ist.

History

Das Hashing entstand in den 1950er Jahren mit Arbeiten, die Hans Peter Luhn bei IBM zugeschrieben werden. Burton Bloom führte 1970 den speichereffizienten Bloom-Filter ein. Carter und Wegman formalisierten Ende der 1970er und Anfang der 1980er Jahre das universelle und später das stark universelle Hashing und gaben dem Hashing damit seine rigorose theoretische Grundlage.

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

Warum werden Hash-Tabellen-Operationen als erwartetes O(1) und nicht als garantiertes O(1) beschrieben?

Wenn viele Schlüssel kollidieren, können Operationen zu O(n) degenerieren. Konstante Zeit gilt erwartungsgemäß unter einer guten Hash-Funktion und einem begrenzten Lastfaktor; universelles Hashing macht einen schlechten Fall unwahrscheinlich, aber Worst-Case-Garantien erfordern perfektes Hashing oder andere Techniken.

Was ist ein Bloom-Filter und wie unterscheidet er sich von einer Hash-Tabelle?

Ein Bloom-Filter ist eine kompakte probabilistische Struktur, die die Mengenmitgliedschaft mithilfe mehrerer Hash-Funktionen über ein Bit-Array testet. Er kann falsch positive Ergebnisse liefern, aber niemals falsch negative, und er speichert keine Schlüssel, wodurch er im Vergleich zu einer Hash-Tabelle Genauigkeit gegen große Platzeinsparungen eintauscht.