Warum wird über die Taste O (1) auf ein Element eines Wörterbuchs zugegriffen, obwohl die Hash-Funktion möglicherweise nicht O (1) ist?

74

Ich sehe, wie Sie per Schlüssel auf Ihre Sammlung zugreifen können. Die Hash-Funktion selbst hat jedoch viele Operationen hinter den Kulissen, nicht wahr?

Vorausgesetzt, Sie haben eine nette Hash-Funktion, die sehr effizient ist, kann es dennoch viele Operationen erfordern.

Kann das erklärt werden?

c# dictionary hashtable big-o monogate
quelle
39
Bei der O-Notation geht es darum, die the growthKomplexität mit verschiedenen Eingaben zu messen . Es geht nicht darum, wie viele Operationen Sie haben. Beispiel: Mit 1 Wert haben Sie xSekunden, mit nWerten benötigen Sie roughly x*nSekunden => O (n). xkönnte viele Operationen zusammen sein.
Khanh
33
Datenstrukturen haben keine O-Notationskomplexität, Operationen auf ihnen.
user6144226
3
Also, welche Operation machen wir?
Patrick Hofman
@PatrickHofman Es erklärt einige Fakten über O (1) -Komplexitäten im Wörterbuch, vielleicht ist verwandt ein besseres Wort.
user6144226
1
"viele Operationen" und O (1) sind perfekt kompatibel - O (1) oder konstante Zeit bedeutet, dass, wenn sich die Anzahl der Elemente der Unendlichkeit nähert, eine endliche Konstante existiert, die die Ausführungszeit begrenzt. Diese Konstante kann beliebig groß sein - die Verwendung einer Hash-Funktion, die garantiert innerhalb eines Jahres abgeschlossen wird, würde das System nicht daran hindern, O (1) zu sein.
Peteris

Antworten:

117

Das HashFuncselbst hat viele Operationen hinter den Kulissen

Das ist sicherlich wahr. Die Anzahl dieser Operationen hängt jedoch von der Größe des Schlüssels ab , nicht von der Größe der Hash-Tabelle, in die der Schlüssel eingefügt wird: Die Anzahl der Operationen zur Berechnung der Hash-Funktion ist für einen Schlüssel in einer Tabelle mit zehn oder gleich mit zehntausend Einträgen.

Aus diesem Grund wird der Aufruf der Hash-Funktion häufig als O (1) betrachtet. Dies funktioniert gut für Schlüssel mit fester Größe (Integralwerte und Zeichenfolgen mit fester Länge). Es bietet auch eine anständige Annäherung für Tasten mit variabler Größe und einer praktischen Obergrenze.

Im Allgemeinen kbeträgt die Zugriffszeit einer Hash-Tabelle jedoch O (k), wobei die Obergrenze für die Größe des Hash-Schlüssels liegt.

Sergey Kalinichenko
quelle
8
Bedenken Sie auch, dass es unmöglich ist, eine Hash-Tabelle mit nunterschiedlichen Elementen zu haben, wenn nicht mindestens ein Element durch mindestens log(n)Bits dargestellt wird.
Owen
Leider sind alle Operationen exponentiell, wenn Sie die Bitgröße der Eingänge nicht einschränken. Aber das ist kein sehr interessantes oder nützliches Ergebnis, oder?
Joker_vD
1
@Owen: Es ist auch nicht möglich, mehr Elemente in einer In-Memory-Hashtabelle zu haben, als eindeutige zugewiesene Schlüssel, die in eine Variable mit Zeigergröße passen.
Joshua
the number of these operations depends on the size of the keyund auf die Größe der gehashten Daten.
Eric J.
kmuss keine Obergrenze sein. Die Suchzeit ist in der Schlüsselgröße linear , also ist es tatsächlich dort, O(k)wo kdie Schlüsselgröße ist. Wenn kes als Obergrenze verstanden wird, dann ist es tatsächlich O(1).
usr
136

O(1)bedeutet nicht sofort. O(1)bedeutet konstant ohne Rücksicht auf die Größe der Daten . Die Hash-Funktion benötigt eine bestimmte Zeit, aber diese Zeit skaliert nicht mit der Größe der Sammlung.

Paarth
quelle
1
Es ist jedoch möglich, eine Hash-Funktion zu schreiben, die von der Größe der Sammlung abhängt. Es wäre dumm und erfunden, aber du kannst es schaffen. Die Aussage, dass die Suche nach einem Hashset tatsächlich unter der Annahme erfolgt, dass die Berechnung des Hashs O (1) ist, was praktisch immer, aber nicht unbedingt der Fall ist.
Servy
@Servy Nicht unbedingt so dumm und erfunden. Eine benutzerdefinierte Listenimplementierung, bei der zwei Listen mit gleichen Elementen als gleich verglichen werden sollen, kann überschrieben werden GetHashCode(), um die Hash-Codes der Elemente auf irgendeine Weise zu kombinieren. Wenn ich eine solche Klasse für eine erste Implementierung implementieren würde, würde ich GetHashCode()genau so implementieren . Das würde ich natürlich auch später ändern.
1
@hvd Das wäre ein O (m) -Hash, wobei m die Größe der inneren Sammlungen ist. Es würde immer noch nicht mit der Größe der äußeren Sammlung (der tatsächlichen Hash-basierten Struktur) zusammenhängen. Die Elemente in der Sammlung müssen alle Elemente derselben Hash-basierten Sammlung anzeigen, in der sie sich derzeit befinden, damit diese Elemente ein O (n) (oder eine beliebige Funktion von n) für ihren Hash-Code haben. Das wäre ziemlich dumm und erfunden.
Servy
1
@Servy Oh, das hast du gemeint. Ja, das wäre dumm. :) Ich kann mir kein plausibles Szenario aus der Ferne einfallen lassen, in dem Sie das vielleicht wollen.
@Servy Der allgemeine Punkt beim Hashing besteht darin, die O (n) -Suchzeit zu vermeiden. Wenn Sie also eine Hash-Funktion erstellen, die O (n) ist, wird der Zweck völlig zunichte gemacht. Sie könnten es tun, aber es wäre, als würden Sie die Addition rekursiv mit Peano-Zahlen implementieren: möglich, aber nicht wirklich praktisch.
Barmar
15

Unabhängig von der Größe Ihrer Sammlung dauert das Abrufen eines Mitglieds fast genauso lange.

Mit anderen Worten, ein Wörterbuch mit 5 Mitgliedern benötigt etwa 0,002 ms, um auf eines von ihnen zuzugreifen, und ein Wörterbuch mit 25 Mitgliedern sollte etwas Ähnliches benötigen. Big O bedeutet algorithmische Komplexität über die Sammlungsgröße anstelle der tatsächlich ausgeführten Anweisungen oder Funktionen

Vidas Vasiliauskas
quelle
1
Aber zur gleichen Zeit, wenn Ihre Hash-Funktion wirklich schlecht ist, können Sie viele Werte im Bucket haben, so dass O (1) nicht mehr halten wird
Klappvisor
3
@klappvisor, nicht notwendig, dass die Funktion schlecht ist. Es kann sein, dass die Eingabedaten erstellt werden. Deshalb ist O (1) hier amortisierte Komplexität, nicht die "wahre" Komplexität.
20.
Dies bedeutet nicht, dass jedes Mitglied die gleiche Zeit benötigt, sondern nur (ungefähr), dass die Obergrenze für diese Zugriffszeit nicht mit der Größe der Sammlung wächst. Überlegen Sie, wie eine Hash-Tabelle mit eindeutigen Kollisionen umgeht. In ähnlicher Weise ist das Nachschlagen eines Elements für einen binären Suchbaum O (log2 n), da der schlechteste Fall log2 mit der Größe N ist, ein Element in der Nähe der Wurzel jedoch weniger Zeit benötigt als beispielsweise ein Blattelement.
flauschig
@ n0rd Das bedeutet eigentlich nicht die "amortisierte" Klarstellung von O (1). Die Tatsache, dass es sich um ein ammortisiertes O (1) handelt, erklärt die Tatsache, dass ungefähr 1 / N der Ergänzungen (wenn Sie dem Satz hinzufügen) die Neuzuweisung eines neuen Hintergrundarrays erfordern, bei dem es sich um eine O (N) -Operation handelt Sie können also N Additionen in O (N) Zeit für eine amortisierte O (1) Addition hinzufügen, während eine einzelne Addition tatsächlich auch O (N) ist (wenn sie nicht amortisiert ist). Es ist eine separate Klarstellung der asymptotischen Komplexität, bei der davon ausgegangen wird, dass die Hashes ausreichend gut verteilt sind.
Servy
12

Wenn ein Wörterbuch / eine Karte als implementiert ist HashMap, hat es eine Best-Case-Komplexität von O(1), da es im besten Fall genau die Berechnung des Hash-Codes des Schlüsselelements zum Abrufen erfordert, wenn keine Schlüsselkollisionen vorliegen.

Eine Hash-Karte kann eine Worst-Case - Laufzeitkomplexität von O(n)wenn Sie eine Menge von Schlüsselkollisionen oder eine sehr schlechten Hash - Funktion, da es in diesem Fall zu einer linearen Abtastung des gesamten Arrays abbaut , die die Daten enthalten.

Bedeutet O(1)auch nicht sofort , es bedeutet, dass es eine konstante Menge hat. Die Auswahl der richtigen Implementierung für ein Wörterbuch kann also auch von der Anzahl der Elemente in der Sammlung abhängen, da sehr hohe konstante Kosten für die Funktion viel schlimmer sind, wenn nur wenige Einträge vorhanden sind.

Aus diesem Grund werden Wörterbücher / Karten für verschiedene Szenarien unterschiedlich implementiert. Für Java gibt es mehrere verschiedene Implementierungen, C ++ verwendet Rot- / Schwarzbäume usw. Sie haben sie basierend auf der Anzahl der Daten und basierend auf ihrer besten / durchschnittlichen / schlechtesten Laufzeiteffizienz ausgewählt.

Martin C.
quelle
1
Dies muss nicht so sein, z. B. greift Java 8 HashMapauf einen ausgeglichenen Baum zurück, falls mehrere Kollisionen erkannt werden.
Acelent
@acelent mag wahr sein, aber dann ist es nicht mehr die klassische Hash-Map. Für genau diesen Fall gibt es viele verschiedene Implementierungen für Karten / Wörterbücher. Ich habe die Antwort geändert, um darauf hinzuweisen.
Martin C.
6

Theoretisch ist es immer noch O (n), da im schlimmsten Fall alle Ihre Daten identischen Hash haben und zusammengebündelt werden. In diesem Fall müssen Sie alles linear durchlaufen.

twihoX
quelle
3

Siehe Beitrag Was bedeutet "O (1) Zugriffszeit"?

Die Anzahl der Operationen in einer Hash-Funktion ist irrelevant, solange für JEDES Element in der Sammlung dieselbe (konstante) Zeit benötigt wird. Der Zugriff auf ein Element in einer Sammlung von 2 Elementen dauert beispielsweise 0,001 ms, aber auch der Zugriff auf ein Element in einer Sammlung von 2.000.000.000 Elementen dauert 0,001 ms. Obwohl die Hash-Funktion Hunderte von if-Anweisungen und mehrere Berechnungen enthalten kann.

Esra
quelle
6
Konstante Zeit, nicht linear.
Kusalananda
Müsste eine Hash-Funktion nicht mehr "if-Anweisungen und mehrere Berechnungen" enthalten, um einen ausreichend langen Hash-Wert zu erzeugen, um 2 Milliarden Elemente eindeutig zu identifizieren, als dies bei 200 der Fall wäre?
Damian Yerrick
1

aus den Dokumenten:

Das Abrufen eines Werts mithilfe seines Schlüssels erfolgt sehr schnell in der Nähe von O (1), da die Klasse T: System.Collections.Generic.Dictionary`2 als Hash-Tabelle implementiert ist.

Es kann also O (1) sein, ist aber möglicherweise langsamer. Hier finden Sie einen weiteren Thread zur Leistung von Hashtabellen: Hash-Tabelle - warum ist sie schneller als Arrays?

JeReT
quelle
1

Wenn Sie die Tatsache berücksichtigen, dass immer größere Wörterbücher mehr Speicherplatz beanspruchen, die Cache-Hierarchie weiter unten durchlaufen und schließlich den Speicherplatz auf der Festplatte verlangsamen, ist es schwer zu argumentieren, dass es sich wirklich um O (1) handelt. Die Leistung des Wörterbuchs wird langsamer, wenn es größer wird, was wahrscheinlich zu einer zeitlichen Komplexität von O (log N) führt. Glaubst du mir nicht? Probieren Sie es selbst mit 1, 100, 1000, 10000 usw. Wörterbuchelementen aus, bis zu 100 Milliarden, und messen Sie, wie lange es in der Praxis dauert, ein Element nachzuschlagen.

Wenn Sie jedoch vereinfachend davon ausgehen, dass der gesamte Speicher in Ihrem System ein Direktzugriffsspeicher ist und in konstanter Zeit zugegriffen werden kann, können Sie behaupten, dass das Wörterbuch O (1) ist. Diese Annahme ist weit verbreitet, obwohl sie für keinen Computer mit Festplatten-Swap-Speicher wirklich zutrifft und angesichts der verschiedenen Ebenen des CPU-Cache auf jeden Fall ziemlich umstritten ist.

Ed Avis
quelle
Sie haben einen Punkt, aber wenn wir über algorithmische Komplexität sprechen, ist es sinnvoll, perfekte Hardware anzunehmen. Es geht darum, Eigenschaften eines Algorithmus zu definieren, nicht verschiedene reale Hardware-Implementierungen. Wenn Sie über ausreichend große Daten verfügen, ist außerdem die Komplexität des Algorithmus am wichtigsten: Ist dies z. B. O (1), (logN), O (n) oder O (n ^ 2)?
Tero Lahtinen
1
Es gibt auch das Problem der Kollision von Hash-Schlüsseln mit größeren Wörterbüchern. Sobald Sie groß genug sind, kollidieren die meisten neuen Einträge mit einem vorhandenen Eintrag, was zu einer linearen Suche in jedem Hash-Bucket führt und als O (n) endet. Es sei denn, Sie lassen die Hash-Schlüssel mit zunehmender Größe länger werden ... aber dann haben Sie auch kein O (1). Ich bin damit einverstanden, dass Sie es in der Praxis als konstante Zeit behandeln können, aber ich würde es vorziehen, mich von der formalen O-Notation für etwas fernzuhalten, das nur eine grobe Annäherung für ausreichend kleine Größen ist, kein formaler Beweis für jede Größe.
Ed Avis