(Wann) ist Hash-Tabellensuche O (1)?

71

Es wird oft gesagt, dass die Hash-Tabellensuche in konstanter Zeit abläuft: Sie berechnen den Hash-Wert, der Ihnen einen Index für eine Array-Suche gibt. Dabei werden Kollisionen ignoriert. im schlimmsten Fall landet jedes Objekt im selben Bucket und die Suchzeit wird linear ( ). $\Theta(n)$

Gibt es Bedingungen für die Daten, die dazu führen können, dass die Hash-Tabellensuche wirklich ? Ist das nur im Durchschnitt, oder kann eine Hash-Tabelle Worst-Case-Lookup haben? $O(1)$ $O(1)$

Anmerkung: Ich komme hier aus der Perspektive eines Programmierers. Wenn ich Daten in einer Hash-Tabelle speichere, handelt es sich fast immer um Zeichenfolgen oder einige zusammengesetzte Datenstrukturen, und die Daten ändern sich während der Lebensdauer der Hash-Tabelle. Ich schätze zwar Antworten über perfekte Hashes, aber sie sind niedlich, aber anekdotisch und aus meiner Sicht nicht praktisch.

PS Follow-up: Für welche Art von Daten sind Hash-Tabellen-Operationen O (1)?

algorithm-analysis data-structures runtime-analysis hash-tables Gilles
quelle

3

Können Sie mit einer amortisierten Zugriffszeit von leben ? Im Allgemeinen hängt die Leistung von Hashtabellen stark davon ab, wie viel Overhead für seltene Hashtabellen Sie tolerieren und wie die tatsächlichen Hashwerte verteilt sind.

O (1)

$\cal{O}(1)$

Raphael

5

Übrigens: Sie können lineares Worst-Case-Verhalten vermeiden, indem Sie (ausgeglichene) Suchbäume anstelle von Listen verwenden.

Raphael

1

@Raphael Mich würde eine Antwort sehr interessieren, die (in groben Zügen) erklärt, wann ich mit amortisiert rechnen kann und wann nicht. Wie die Hash-Werte verteilt sind, ist ein Teil meiner Frage: Wie kann ich das wissen? Ich weiß, dass Hash-Funktionen Werte gut verteilen sollen. aber wenn sie es immer taten, würde der schlimmste Fall niemals erreicht werden, was keinen Sinn ergibt.

O (1)

$O(1)$

Gilles

1

Achten Sie auch auf eine vorzeitige Optimierung. Für kleinere Daten (mehrere tausend Elemente) habe ich oft gesehen, dass ausgeglichene Binärbäume aufgrund des geringeren Overheads die Hashtabellen übertreffen (Zeichenfolgenvergleiche sind erheblich billiger als Zeichenfolgenhashes).

O (\log n)

$O(\log n)$

Isturdy

Lassen Sie uns diese Diskussion im Chat fortsetzen .

Raphael

41

Es gibt zwei Einstellungen, unter denen Sie Worst-Case-Zeiten erhalten können. $O(1)$

Wenn Ihr Setup statisch ist, erhalten Sie durch FKS-Hashing die Worst-Case- -Garantien. Aber wie Sie angegeben haben, ist Ihre Einstellung nicht statisch. $O(1)$
Wenn Sie Cuckoo-Hashing verwenden, sind Abfragen und Löschvorgänge im schlimmsten Fall , aber das Einfügen wird nur mit erwartet. Kuckuck-Hashing funktioniert ganz gut, wenn Sie eine Obergrenze für die Gesamtzahl der Einfügungen haben und die Tabellengröße auf ungefähr 25% größer einstellen. $O(1)$ $O(1)$

Es stehen weitere Informationen hier .

Suresh
quelle

3

Könnten Sie FKS und Cuckoo erweitern? Beide Begriffe sind für mich neu.

Gilles

1

Was ist mit Dynamic Perfect Hashing? Es hat Worst-Case-Lookups und amortisiertes Einfügen und Löschen. ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8165 )

O (1)

$O(1)$

O (1)

$O(1)$

Joe,

2

FKS sind die Initialen von (Fredman, Komlós, Szemerédi) und Cuckoo ist der Name einer Brückenart. Es wird für diese Art von Hashing verwendet, da Kuckucksküken Zischeleier aus dem Nest schieben. Dies ähnelt in gewisser Weise der Funktionsweise dieser Hasing-Methode.

uli

1

@ Suresh: Wirklich? Ich dachte, Sie benötigen -unabhängige Funktionen, die ich immer mit der Notwendigkeit von Erweiterungen verband. Ich stehe korrigiert. Löscht meinen Kommentar in Kürze.

\log n

$\log n$

Louis

1

Um diese Antwort nützlicher zu kommentieren, funktioniert Kuckuck-Hashing, wie @Suresh betont, auch ohne die ausgefallenen (und großen) Hash-Funktionen, mit denen es theoretisch analysiert wird.

Louis

21

Diese Antwort fasst Teile von TAoCP Vol. 3, Kapitel 6.4 zusammen.

Angenommen, wir haben eine Menge von Werten , von denen wir in einem Array der Größe speichern wollen . Wir verwenden eine Hash-Funktion ; typischerweise ist . Wir nennen $V$ $n$ $A$ $m$ $h : V \to [0..M)$ $M \ll |V|$ denBelastungsfaktorvon. Hier nehmen wir das natürliche; in praktischen Szenarien haben wir, aber, und bis hinunter zur Karte hatihnen. $\alpha = \frac{n}{m}$ $A$ $m=M$ $m \ll M$ $m$

$h$ $\mathcal{O}(1)$

$[0..M)$ $C_n^S$ $C_n^U$

Verkettung

$\frac{n}{m}$

C_{n}^{S} \approx 1 + \frac{α}{2} and C_{n}^{U} \approx 1 + \frac{α^{2}}{2} .

$C_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C_n^U \approx 1 + \frac{\alpha^2}{2} .$

Lineare Abtastung

$v$

h (v), h (v) - 1, \dots, 0, m - 1, \dots, h (v) + 1

$h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1$

v

$v$

α \to 1

$\alpha \to 1$

C_{n}^{S} \approx \frac{1}{2} (1 + \frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{2} (1 + {(\frac{1}{1 - α})}^{2}) .

$C_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).$

α < 0.75

$\alpha < 0.75$

Double Hashing

$M$

C_{n}^{S} \approx \frac{1}{α} \ln (\frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{1 - α} .

$C_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C_n^U \approx \frac{1}{1-\alpha} .$

Beachten Sie, dass das Entfernen von Elementen aus und das Erweitern von Tabellen für die jeweiligen Methoden unterschiedliche Schwierigkeitsgrade aufweist.

$\mathcal{O}(1)$ $\alpha$ $h$

$h$
Hashtable

Raphael
quelle

10

$S$ $\{0, 1, 2, ..., n\}$ $O(1)$ $O(1)$ $l$ $S$ $l$ $x$ $x \in S$ $O(|l|)$ $S$ $O(|S|)$ $O(|l| + |S|)$ $O(|l||S|)$ $O(\log(|l|)|S|)$ $O(|l|)$ $l$

$O(|l|)$

$l$ $U \subset \mathbb{N}$ $S \subseteq U$ $x \in S$ $l$ $l$ $h: U \rightarrow \{true, false\}$ $h$ $h(x) = false$ $x \in U$ $y$ $l$ $h(y) = true$ $O(|l|)$ $O(|U|)$

$l$ $O(|U|)$ $O(|1|)$ $O(|U|)$

$U$ $h$

Patrick87
quelle

O (| l |)

$O(|l|)$

O (| S |)

$O(|S|)$

O (| l | \cdot | S |)

$O(|l|\cdot|S|)$

h

$h$

h : U \to {f a l s e, t r u e}

$h:U\to\{\mathrm{false},\mathrm{true}\}$

h

$h$

@ Gilles Es wird im Grunde nur als Nachschlagetabelle für die Listenmitgliedschaft verwendet. Wenn Sie eine perfekte Hash-Funktion mit einer bekannten und billigen Inverse haben, müssen Sie, anstatt das Ding selbst zu speichern, nur 1 Bit speichern (ob das Ding mit dem eindeutigen Hash hinzugefügt wurde). Wenn Kollisionen möglich sind, wird dies meines Erachtens als Bloom-Filter bezeichnet, kann aber auf jeden Fall die Frage der Mitgliedschaft mit einem eindeutigen "Nein" beantworten, was in vielen Szenarien immer noch nützlich ist.

Patrick87

9

$\cal{O}(1)$

$\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$

Nicholas Meyer
quelle

Eine perfekte Hash-Funktion wäre perfekt, aber wie bekomme ich eine? Wie viel kostet es mich? Und woher weiß ich, wie viele Kollisionen maximal oder zu erwarten sind?

Gilles

2

@Gilles Eine perfekte Hash-Funktion ist jede Funktion, die einen eindeutigen Hash für alle möglichen Eingaben erzeugt. Wenn Ihre möglichen Eingaben endlich (und eindeutig) sind, ist dies einfach zu tun.

Rafe Kettler

1

@RafeKettler Bei meinen Eingaben handelt es sich normalerweise um Zeichenfolgen oder zusammengesetzte Datenstrukturen. Normalerweise füge ich Einträge hinzu und entferne sie, wenn sich meine Daten weiterentwickeln. Wie mache ich einen perfekten Hash dafür?

Gilles

4

Ja, aber das ist der Punkt. Eine deterministische perfekte Hash-Funktion existiert nicht, wenn die Domäne größer als der Bereich ist.

Suresh

@Suresh: Wenn Sie bei einer Kollision eine neue Hash-Funktion auswählen und die Größe der Tabelle erhöhen dürfen, können Sie immer eine (deterministische) Hash-Funktion finden, die - für die bereits in der Tabelle enthaltenen Daten plus die neue Artikel, den Sie einfügen möchten - hat keine Kollisionen (ist "perfekt"). Aus diesem Grund wählt Dynamic Perfect Hashing regelmäßig eine zufällige neue Hash-Funktion aus.

David Cary

(Wann) ist Hash-Tabellensuche O (1)?

Antworten:

Verkettung

Lineare Abtastung

Double Hashing