Wie berücksichtigen Hash-Tabellen O (1) die Hash-Geschwindigkeit?

Hash-Tabellen sollen unter Verwendung von beispielsweise einfacher Verkettung und Verdoppelung bei einer bestimmten Kapazität amortisiert werden. $\Theta(1)$

Dies setzt jedoch voraus, dass die Längen der Elemente konstant sind. Um den Hash eines Elements zu berechnen, muss das Element durchlaufen werden, wobei Zeit benötigt wird, wobei die Länge ist. $\Theta(l)$ $l$

Um jedoch zwischen Elementen zu unterscheiden, müssen die Elemente eine Länge von mindestens Bits haben. Andernfalls werden sie nach dem Pigeonhole-Prinzip nicht unterschieden. Die Hash-Funktion, die Elementbits durchläuft , benötigt Zeit. $n$ $\lg n$ $\lg n$ $\Theta(\lg n)$

Können wir stattdessen sagen, dass die Geschwindigkeit einer Hash-Tabelle unter Berücksichtigung einer vernünftigen Hash-Funktion, die alle Teile der Eingabe verwendet, tatsächlich ? Warum sind Hash-Tabellen in der Praxis dann effizient zum Speichern von Elementen variabler Länge wie Zeichenfolgen und großen Ganzzahlen? $\Theta(\lg n)$

hash-tables dictionaries ithisa
quelle

Eng verwandt: (Wann) ist Hash-Tabellensuche O (1)? , Für welche Art von Daten sind Hash-Tabellenoperationen O (1)?

Gilles 'SO - hör auf böse zu sein'

Die Antwort ist, dass sie es nicht sind . Diese Art der Analyse von Hashing berücksichtigt nicht die Dimension (oder Anzahl der Bits) der Elemente, sondern nur deren Vielzahl.

Nikos M.

Aber wenn ein Hash - Map Nachschau das sei

ohne Berücksichtigung von Lese und Schreiben der Bits , wie beschrieben, ist &

, dann unter den gleichen Kriterien, eine binäre Suche oder ein anderes Verfahren wir in der Regel betrachten

würde tatsächlich sein

nicht wahr?

Θ (1)

$\Theta (1)$

\in Θ (l g

$\in \Theta (lg$

n)

$n)$

\in Θ l g

$\in \Theta lg$

n

$n$

\in Θ (l g^{2}

$\in \Theta( lg^2$

n)

$n )$

@tAllan cf Uniform vs logarithmisches Kostenmodell .

Raphael

@tAllan Eine reguläre binäre Suche wäre

Wenn Sie jedoch die Elemente nach den Bitfolgen ihrer Schlüssel sortieren und eine binäre Suche durchführen, indem Sie "ein Bit nach dem anderen" vergleichen (knifflige Details weggelassen), können Sie dies möglicherweise erreichen

Θ (\log^{2} n)

$\Theta(\log^2 n)$

Θ (\log n)

$\Theta(\log n)$

Stellen Sie Monica

Antworten:

Die Geschichte, dass Hash-Tabellen amortisiert werden ist ~~eine Lüge,~~ eine übermäßige Vereinfachung. $\Theta(1)$

Dies gilt nur, wenn:
- Die Menge der zu hashenden Daten pro Element im Vergleich zur Anzahl der K eys trivial ist und die Geschwindigkeit des Hashing eines K ey schnell ist - . - Die Anzahl der C ollisions ist klein - . - Wir nicht berücksichtigen Zeit benötigt , um R die Hash - Tabelle ESIZE - . $k$
$c$
$r$

Große Zeichenfolgen für Hash
Wenn die erste Annahme falsch ist, steigt die Laufzeit auf . Dies gilt definitiv für große Saiten, aber für große Saiten hätte ein einfacher Vergleich auch eine Laufzeit von . Ein Hash ist also nicht asymptotisch langsamer, obwohl das Hashing immer langsamer ist als ein einfacher Vergleich, da der Vergleich ein frühes Opt-out hat, also , und das Hashing immer den vollen String muss. $\Theta(k)$
$\Theta(k)$ $O(1)$ $\Omega(k)$ $O(k)$ $\Omega(k)$ .

Beachten Sie, dass Ganzzahlen sehr langsam wachsen. 8 Bytes können Werte bis zu speichern ; 8 Bytes sind eine triviale Menge an Hash. Wenn Sie Bigint speichern möchten, stellen Sie sich diese einfach als Zeichenfolgen vor. $10^{18}$

Langsamer Hash-Algorithmus
Wenn der Hashing-Betrag im Vergleich zur Speicherung der Daten nicht trivial ist, wird die Annahme offensichtlich unhaltbar. Sofern kein kryptografischer Hash verwendet wird, sollte dies kein Problem sein. $\Theta(1)$

Entscheidend ist , dass . Solange dies gilt, ist eine faire Aussage. $n$ $>>$ $k$ $\Theta(1)$

Viele Kollisionen
Wenn die Hashing-Funktion schlecht ist oder die Hash-Tabelle klein ist oder die Größe der Hash-Tabelle unangenehm ist, treten häufig Kollisionen auf und die Laufzeit geht auf . Die Hashing-Funktion sollte so gewählt werden, dass Kollisionen selten sind und dennoch so schnell wie möglich. Wenn Sie Zweifel haben, entscheiden Sie sich für weniger Kollisionen auf Kosten eines langsameren Hashing. Als Faustregel gilt, dass die Hashing-Tabelle immer zu weniger als 75% gefüllt sein sollte. Und die Größe der Hashing-Tabelle sollte keine Korrelation mit der Hashing-Funktion haben. Oft ist die Größe der Hashing-Tabelle (relativ) prim. $O(log(n))$

Ändern der Größe der Hash-Tabelle
Da eine fast vollständige Hash-Tabelle zu viele Kollisionen verursacht und eine große (leere) Hash-Tabelle Platzverschwendung darstellt, können Sie bei vielen Implementierungen die Hash-Tabelle nach Bedarf vergrößern (und verkleinern!).
Das Erweitern einer Tabelle kann eine vollständige Kopie aller Elemente (und möglicherweise eine Umbildung) umfassen, da der Speicher aus Leistungsgründen kontinuierlich sein muss.
Nur in pathologischen Fällen ist die Größenänderung der Hash-Tabelle ein Problem, sodass die (kostspieligen, aber seltenen) Größenänderungen über viele Aufrufe hinweg abgeschrieben werden.

Laufzeit
Die tatsächliche Laufzeit einer Hash-Tabelle ist also . Es wird angenommen, dass jedes von , , im Durchschnitt eine (kleine) Konstante in der amortisierten Laufzeit ist, und daher sagen wir, dass eine faire Aussage ist. $\Theta(kcr)$
$k$ $c$ $r$ $\Theta(1)$

Um auf Ihre Fragen zurückzukommen
Bitte entschuldigen Sie die Umschreibung. Ich habe versucht, verschiedene Bedeutungen zu extrahieren. Sie können gerne Kommentare abgeben, wenn ich einige verpasst habe

Sie scheinen besorgt über die Länge der Ausgabe der Hash-Funktion zu sein. Nennen wir dies ( wird im Allgemeinen als die Anzahl der zu hashenden Elemente angesehen). ist da m einen Eintrag in der Hash-Tabelle eindeutig identifizieren muss. Dies bedeutet, dass m sehr langsam wächst. Bei 64 Bit nimmt die Anzahl der Hash-Tabelleneinträge einen beträchtlichen Teil des weltweit verfügbaren RAM ein. Mit 128 Bit wird der verfügbare Festplattenspeicher auf dem Planeten Erde weit überschritten. Das Erstellen eines 128-Bit-Hashs ist nicht viel schwieriger als das Erstellen eines 32-Bit-Hashs. Nein , die Zeit zum Erstellen eines Hashs ist nicht $m$ $n$ $m$ $log(n)$

(oder wenn Sie so wollen). $O(m)$ $O(log(n))$

Die Hash-Funktion, die Bits des Elements durchläuft , benötigt Zeit. $log(n)$ $Θ(log(n))$

Die Hash-Funktion durchläuft jedoch keine Bits von Elementen. Pro Punkt (!!) geht es nur durch Daten. Auch die Länge der Eingabe (k) hat keine Beziehung zur Anzahl der Elemente. Dies ist wichtig, da einige Nicht-Hashing-Algorithmen viele Elemente in der Sammlung untersuchen müssen, um ein (nicht) übereinstimmendes Element zu finden. In der Hash-Tabelle werden durchschnittlich nur 1 oder 2 Vergleiche pro betrachtetem Element durchgeführt, bevor eine Schlussfolgerung gezogen wird. $log(n)$
$O(k)$

Warum sind Hash-Tabellen zum Speichern von Elementen variabler Länge effizient?

Da unabhängig von der Länge der Eingabe ( ) die Länge der Ausgabe ( ) immer gleich ist, sind Kollisionen selten und die Suchzeit konstant. Wenn jedoch die Schlüssellänge Vergleich zur Anzahl der Elemente in der Hash-Tabelle ( ) groß wird, ändert sich die Geschichte ... $k$ $m$
$k$ $n$

Warum können Hash-Tabellen große Zeichenfolgen effizient speichern?

Hash-Tabellen sind für sehr große Zeichenfolgen nicht sehr effizient .

Wenn (dh die Größe der Eingabe ist im Vergleich zur Anzahl der Elemente in der Hash-Tabelle ziemlich groß), können wir nicht mehr sagen, dass der Hash eine konstante Laufzeit hat, sondern auf eine Laufzeit von wechseln muss allem, weil es kein frühes Aus gibt. Sie müssen den vollständigen Schlüssel hashen. Wenn Sie nur eine begrenzte Anzahl von Elementen speichern, ist es möglicherweise viel besser, einen sortierten Speicher zu verwenden, da Sie beim Vergleich von deaktivieren können, sobald ein Unterschied festgestellt wird. $not$ $n >> k$ $\Theta(k)$ $k1$ $\ne$ $k2$

Wenn Sie jedoch Ihre Daten kennen, können Sie festlegen, dass nicht der vollständige Schlüssel, sondern nur der (bekannte oder angenommene) flüchtige Teil davon gehasht wird. Dabei wird die Eigenschaft wiederhergestellt, während die Kollisionen in Schach gehalten werden. $\Theta(1)$

Versteckte Konstanten
Wie jeder wissen sollte, bedeutet einfach, dass die Zeit pro verarbeitetem Element eine Konstante ist. Diese Konstante ist für das Hashing viel größer als für den einfachen Vergleich. Bei kleinen Tabellen ist eine binäre Suche schneller als eine Hash-Suche, da beispielsweise 10 binäre Vergleiche sehr wohl schneller sind als ein einzelner Hash. Für kleine Datensätze sollten Alternativen zu Hash-Tabellen in Betracht gezogen werden. Bei großen Datenmengen leuchten Hash-Tabellen wirklich. $\Theta(1)$

Johan
quelle

Ich verstehe deine Definition von . Es ist nicht wahr, dass die Größenänderung die amortisierte Laufzeit erhöht. Solange Sie die Größe entsprechend anpassen, können die Kosten für das Kopieren abgeschrieben werden und erhöhen die amortisierte Laufzeit nicht. Ich denke nicht, dass die Geschwindigkeit des Hash jemals ein Problem ist (selbst kryptografische Hashes sind sehr schnell; und auf jeden Fall laufen sie in konstanter Zeit, wenn die Länge der Eingabe durch eine Konstante begrenzt wird). Die -Runtime-Ansprüche hängen immer von der Verwendung einer guten Hash-Funktion ab (daher gibt es nur wenige Kollisionen).

k, c, r

$k,c,r$

O (1)

$O(1)$

Von den von Ihnen erwähnten Problemen denke ich, dass nur die Länge der Eingabe wirklich ein ernstes Problem ist. Dies beantwortet auch nicht wirklich die gestellte Frage. Die Frage bezieht sich auf die Länge der Ausgänge, und diese Länge der Ausgänge sollte am besten als -Bits und nicht als -Bits betrachtet werden. Das ist richtig, aber was übersehen wird, ist das Rechenmodell, das zur Berechnung der -Laufzeit verwendet wird. Diese Antwort scheint nicht darauf einzugehen, daher bin ich mir nicht sicher, ob dies das in der Frage aufgeworfene Problem betrifft.

Ω (\lg n)

$\Omega(\lg n)$

O (1)

$O(1)$

O (1)

$O(1)$

Ich wollte mit allen Elementen der Laufzeit komplett sein. Wir sind uns einig, dass beim Hashing nur die Schlüssellänge wirklich ein Problem darstellt. Ich habe das Log (n) -Problem behoben, das das OP ausgelöst hat. Ich habe das falsch verstanden, weil es beim Hashing von IMO so kein Problem ist.

Johan

Ich hoffe, die Antwort stimmt jetzt besser mit der Frage des OP überein.

Johan

Beginnen wir mit einer einfacheren Frage. Betrachten Sie die vielleicht einfachste Datenstruktur, die es gibt, ein Array . Stellen wir uns der Vollständigkeit halber eine Reihe von ganzen Zahlen vor. Wie lange dauert die Operation ? Die Antwort hängt vom Berechnungsmodell ab. Hierbei sind zwei Modelle relevant: das RAM-Modell (das häufiger verwendet wird) und das Bitmodell (das einfacher zu erklären ist). $A[i] = A[j]$

In dem Bit - Modell , ein basisches Operation mit Bits kostet . Wenn also die ganzen Zahlen Bits breit sind, wird die Operation ungefähr 2 . $N$ $N$ $w$ $A[i] = A[j]$ $2w$

Im RAM-Modell ist die Basisdateneinheit kein Bit, sondern ein Wort (manchmal auch als Maschinenwort bezeichnet ). Ein Wort ist eine Ganzzahl mit der Breite , wobei die Größe der Eingaben (in Bits) ist. Eine grundlegende Operation mit Worten kostet . In den meisten Fällen haben die benötigten Ganzzahlen, wenn Sie ein ganzzahliges Array haben, die Breite , sodass die Operation kostet . $\log n$ $n$ $N$ $N$ $O(\log n)$ $A[i] = A[j]$ $O(1)$

Wie ich oben sagte, analysieren wir normalerweise Algorithmen unter Verwendung des RAM-Modells. Die einzige häufige Ausnahme ist die Ganzzahlarithmetik, insbesondere die Ganzzahlmultiplikation, die häufig in Bezug auf die Anzahl der Bitoperationen analysiert wird.

Warum verwenden wir das RAM-Modell? Da es mehr Vorhersagekraft hat (gegenüber der Realität). Die Annahme, dass die Eingabegröße in der Größe eines Maschinenworts höchstens exponentiell ist, ist normalerweise gerechtfertigt, insbesondere für moderne 64-Bit-Prozessoren, und Operationen an Maschinenwörtern benötigen in tatsächlichen CPUs eine konstante Zeit.

Hash-Tabellen sind kompliziertere Datenstrukturen und umfassen drei Typen: den Schlüsseltyp, den Hash-Typ und den Werttyp. Aus Sicht des Wertetyps ist eine Hash-Tabelle nur ein verherrlichtes Array. Lassen Sie uns diesen Aspekt ignorieren. Es kann immer angenommen werden, dass der Hash-Typ aus einer kleinen Anzahl von Maschinenwörtern besteht. Der Schlüsseltyp erfüllt eine spezielle Eigenschaft: Er ist hashbar , was bedeutet, dass er eine Hash-Operation hat, die (mindestens) eine deterministische Funktion ist (eine Funktion, die immer den gleichen Wert zurückgibt ).

Wir können jetzt Ihre Frage beantworten: Wie lange dauert es, einen Schlüssel zu hashen? Die Antwort hängt vom Berechnungsmodell ab. Diesmal haben wir drei gemeinsame Modelle: die beiden früheren und das Orakelmodell.

Im Orakelmodell nehmen wir an, dass uns die Hash-Funktion von einem "Orakel" gegeben wird, das den Hash eines beliebigen Schlüssels in konstanter Zeit berechnen kann.

Im RAM-Modell und im Bitmodell ist die Hash-Funktion eine tatsächliche Funktion, und die zeitliche Komplexität der Hash-Tabelle hängt von der zeitlichen Komplexität der Hash-Funktion ab. Hash-Funktionen, die für Hash-Tabellen (und nicht für kryptografische Zwecke) verwendet werden, sind normalerweise sehr schnell und benötigen lineare Zeit für die Eingabe. Das heißt, wenn der Schlüsseltyp eine Länge von Bits (im Bitmodell) oder Wörtern (im RAM-Modell) hat, benötigt die Hash-Funktion die Zeit . Wenn eine Konstante ist, benötigt die Hash-Funktion eine konstante Zeit. $N$ $N$ $O(N)$ $N$

Wenn wir die Laufzeit von Hash-Tabellen-Algorithmen analysieren, verwenden wir normalerweise implizit das Orakelmodell. Dies wird oft in einer anderen Sprache ausgedrückt: Wir sagen einfach, dass wir die Anzahl der Aufrufe der Hash-Funktion zählen. Dies ist sinnvoll, da normalerweise Anwendungen der Hash-Funktion der dominierende Begriff in der Laufzeit von Hash-Tabellen-Algorithmen sind. Um die tatsächliche Zeitkomplexität zu analysieren, müssen Sie lediglich die Anzahl der Hash-Aufrufe mit der Laufzeit multiplizieren der Hash-Funktion.

Bei der Analyse der Laufzeit eines Algorithmus unter Verwendung einer Hash-Tabelle als Datenstruktur interessiert uns häufig die tatsächliche Laufzeit, normalerweise das RAM-Modell. Eine Möglichkeit besteht darin, das zu tun, was im vorhergehenden Absatz vorgeschlagen wurde, nämlich die Laufzeit von Hash-Tabellenoperationen (angegeben als Anzahl der Aufrufe von Hash-Funktionen) mit der Laufzeit der Hash-Funktion zu multiplizieren.

Dies ist jedoch nicht gut genug, wenn die Tasten unterschiedliche Längen haben. Stellen Sie sich zum Beispiel vor, wir haben Schlüssel der Größe , und wir berechnen den Hash von jedem von ihnen einmal. Die tatsächliche Zeitkomplexität beträgt , aber die obige Berechnung ergibt nur . Wenn dies in einer Anwendung der Fall ist, können wir dies auf Ad-hoc-Basis berücksichtigen, indem wir eine verfeinerte Analyse der Komplexität der zugrunde liegenden Hash-Tabelle verwenden. $1,2,4,\ldots,2^m$ $O(2^m)$ $O(m2^m)$

Yuval Filmus
quelle