O (1) Hash-Lookups?

Question

Ich lief über eine Behauptung, dass HashSet <T> .Contains() ist eine O (1) -Operation. Das hat mich überrascht, da jede Diskussion über Hashing die Möglichkeit von Kollisionen erwähnt, die möglicherweise zu O (n) Laufzeit führen.

Neugierig, ich schaute in Dokumentation für HashSet <T>. Enthält und auch HashTable.Contains. Die Dokumentation für beide Methoden macht denselben Anspruch.

Wenn ich in Reflektor schaue, HashSet <T> .Contains() ist mit einer for-Schleife implementiert, durchläuft eine Liste von Steckplätzen mit Werten, die den gleichen Hash haben.

Nun haben die gleichen Diskussionen über Hashing auch erwähnt, dass ein guter Hashing-Algorithmus Kollisionen vermeidet und unter diesen Umständen wird die Suche in der Tat O (1) sein. Aber mein Verständnis der Big-O-Notation ist, dass es die schlechteste Laufzeit ist, nicht die beste.

Also ist die O (1) Behauptung falsch? Oder fehlt mir etwas?

Answer 1

Aber mein Verständnis der Big O-Notation ist, dass es die schlechteste Laufzeit ist, nicht die beste.

Leider gibt es keinen "Standard" für Big-O bei der Beschreibung von Algorithmen. Oft wird es verwendet, um den allgemeinen oder durchschnittlichen Fall zu beschreiben - nicht den schlimmsten Fall.

Von Wikipedia:

... diese Notation jetzt häufig auch bei der Analyse von Algorithmen verwendet einen Algorithmus, der Nutzung von Rechenressourcen zu beschreiben: den schlimmsten Fall oder durchschnittlichen Fall ...

In diesem Fall beschreibt es einen Standardfall, bei richtigem Hashing. Wenn Sie ein richtiges Hashing haben, wird das Begrenzungsverhalten für die Größe N konstant sein, also O (1).

Answer 2

Im Allgemeinen ist es O (1).

Answer 3

Nein, Big O definiert nicht "Worst Case", es definiert ein Limit. Hash-basierte Suchvorgänge (mit guten Hashing-Algorithmen, die eine effiziente Werteverteilung und eine geringe Kollisionsrate bieten) werden mit steigender Anzahl von Elementen zu einem konstanten Wert fortlaufend (sie erreichen niemals oder diesen konstanten Wert, aber das ist der Punkt, der eine Grenze darstellt)).

Answer 4

Ich glaube, es bedeutet O (1) im Durchschnitt.

Answer 5

Mein Verständnis von Big Oh ist, dass der "schlimmste Fall" im Allgemeinen in Bezug auf die Anzahl der beteiligten Elemente ist. Wenn also eine Funktion O (n) mit 10 Elementen, aber O (n Quadrat) mit 100 oder mehr ausführen würde (nicht sicher, ob ein solcher Algorithmus tatsächlich existiert), dann wird der Algorithmus als O (n-Quadrat) betrachtet.

Answer 6

O (1) bedeutet nicht unbedingt "schlimmster Fall". Bei Hashes sagt man normalerweise, dass die "erwartete" Nachschlagezeit O (1) ist, da die Wahrscheinlichkeit von Hash-Kollisionen gering ist.

Answer 7

Für eine ordnungsgemäß implementierte Hash-Tabelle haben Lookups amortized konstante Zeit Komplexität.

In der Praxis kann ein einzelnes Nachschlagen bei Kollisionen O (n) sein, wie Sie sagen. Wenn Sie jedoch eine große Anzahl von Suchvorgängen durchführen, ist die durchschnittliche Zeitkomplexität pro Operation konstant.

Zitiert wikipedia:

Amortisierte Analyse unterscheidet sich von der durchschnittlichen Fall Leistung in diese Wahrscheinlichkeit nicht beteiligt ist; Die amortisierte Analyse garantiert die Zeit pro Vorgang gegenüber der Worst-Case-Leistung.

Die Methode erfordert Kenntnisse, welche Reihe von Operationen möglich sind. Dies ist am häufigsten bei Datenstrukturen der Fall, bei denen der Zustand zwischen den Operationen bestehen bleibt. Der Grundgedanke ist, dass eine Worst-Case-Operation den Zustand so verändern kann, dass der Worst-Case lange nicht mehr auftreten kann und die Kosten "amortisieren".

Answer 8

Nein, Big-O-Notation ist nicht unbedingt auf den Worst-Case beschränkt. Normalerweise wird Big-O für den besten Fall, den Durchschnitts- und den schlimmsten Fall veröffentlicht. Es ist nur so, dass die meisten Menschen sich auf den schlimmsten Fall konzentrieren. Außer im Falle einer Hashtabelle passiert der schlimmste Fall selten, so dass die Verwendung des Durchschnittsfalls sinnvoller ist.

Ja, eine gute Hash-Funktion reduziert die Wahrscheinlichkeit einer Kollision. Eine ungültige Hash-Funktion kann den Clustering-Effekt verursachen (bei dem unterschiedliche Werte auf denselben Wert oder denselben Wert synchronisiert werden). Es ist leicht zu demonstrieren, dass HashSet tatsächlich O (n) werden kann, indem die GetHashCode Funktion in einer solchen Weise implementiert wird, dass sie die ganze Zeit den gleichen Wert zurückgibt.

In einem nutshull, ja HashSet und Dictionary kann beschrieben werden als mit O (1) Laufzeit Komplexität, weil der Schwerpunkt auf dem durchschnittlichen Fall-Szenario ist.

Big-O kann übrigens auch zur Analyse der amortisierten Komplexität verwendet werden. Amortisierte Komplexität ist, wie sich eine Folge separater (und manchmal sogar unterschiedlicher) Operationen verhält, wenn sie zusammen gruppiert werden, als wären sie eine große Operation. Zum Beispiel wird gesagt, dass ein gespreizter Baum eine amortisierte O (log (n)) Such-, Einfügungs- und Löschungskomplexität hat, obwohl der schlechteste Fall für jedes O (n) und der beste Fall O (1) ist.

Answer 9

Hash-Tabellen haben nicht nur eine durchschnittliche Fall-Performance O (1), aber wenn die Hash-Funktion zufällig ist, für einen bestimmten Prozentsatz P < 100%, die Leistung, die P% der Zeit von einem richtig erhalten werden kann entworfene Hash-Geschichte ist O (1). Obwohl die extremen parasitären Fälle mit steigendem N immer stärker werden, wird dies durch die Tatsache ausgeglichen, dass selbst mäßig parasitäre Fälle immer weniger wahrscheinlich werden.