wake-up-neo.net

Warum Hashmap-Lookup ist O(1) konstante Zeit?

Wenn wir aus der Java-Perspektive schauen, können wir sagen, dass die Hashmap-Suche konstante Zeit benötigt. Aber wie sieht es mit der internen Umsetzung aus? Es müsste immer noch in einem bestimmten Bucket (für den übereinstimmenden Hashcode des Schlüssels) nach verschiedenen übereinstimmenden Schlüsseln gesucht werden. Bitte erkläre.

27
genonymous

Unter den entsprechenden Annahmen für die verwendete Hash-Funktion können wir sagen, dass die Hash-Tabellensuche erwartete O(1) -Zeit benötigt (vorausgesetzt, Sie verwenden ein Standard-Hash-Schema wie lineares Sondieren oder verkettetes Hashing). . Dies bedeutet, dass im Durchschnitt , der Arbeitsaufwand, den eine Hashtabelle zum Durchführen einer Suche ausführt, höchstens konstant ist.

Wenn Sie eine "gute" Hash-Funktion haben, würden Sie intuitiv erwarten, dass Elemente mehr oder weniger gleichmäßig in der Hash-Tabelle verteilt werden, was bedeutet, dass die Anzahl der Elemente in jedem Bucket der Anzahl der durch die Anzahl dividierten Elemente nahekommen würde von Eimern. Wenn die Hashtabellenimplementierung diese Anzahl niedrig hält (z. B. durch Hinzufügen weiterer Buckets, wenn das Verhältnis der Elemente zu den Buckets eine bestimmte Konstante überschreitet), wird die erwartete Menge an erledigter Arbeit letztendlich eine grundlegende Arbeit sein, um den Bucket auszuwählen sollte gescannt werden und dann "nicht zu viel" Arbeit damit verbringen, die Elemente dort zu betrachten, da auf Erwartung nur eine konstante Anzahl von Elementen in diesem Eimer vorhanden ist.

Dies bedeutet nicht, dass Hashtabellen garantiert O(1) Verhalten haben. Im schlimmsten Fall degeneriert das Hash-Schema, und alle Elemente werden in einem Bucket landen, sodass Lookups im ungünstigsten Fall Zeit Θ (n) benötigen. Deshalb ist es wichtig, gute Hash-Funktionen zu entwerfen.

Für weitere Informationen möchten Sie vielleicht ein Lehrbuch für Algorithmen lesen, um zu sehen, warum Hashtabellen so effizient Abfragen unterstützen. Dies ist normalerweise Bestandteil eines typischen Universitätslehrgangs zu Algorithmen und Datenstrukturen. Es gibt viele gute Ressourcen online.

Interessante Tatsache: Es gibt bestimmte Arten von Hashtabellen (Kuckucks-Hashtabellen, dynamische perfekte Hashtabellen), bei denen die Worst-CaseLookup-Zeit für ein Element O (1) ist. Diese Hashtabellen funktionieren, indem sichergestellt wird, dass sich jedes Element nur in einer von wenigen festen Positionen befinden kann, wobei Einfügungen manchmal um Elemente herumlaufen, um zu versuchen, alles passend zu machen.

Hoffe das hilft!

32
templatetypedef

Der Schlüssel ist in dieser Anweisung in den Dokumenten:

Wenn viele Mappings in einer HashMap-Instanz gespeichert werden sollen, können durch das Erstellen einer ausreichend großen Kapazität die Mappings effizienter gespeichert werden, als wenn sie automatisch ein automatisches Aufwärmen durchführt, um die Tabelle zu vergrößern.

und

Der Lastfaktor ist ein Maß dafür, wie voll die Hashtabelle sein darf, bevor ihre Kapazität automatisch erhöht wird. Wenn die Anzahl der Einträge in der Hashtabelle das Produkt aus dem Lastfaktor und der aktuellen Kapazität überschreitet, wird die Hashtabelle erneut gewaschen (dh, interne Datenstrukturen werden neu erstellt), so dass die Hashtabelle ungefähr die doppelte Anzahl von Buckets hat.

http://docs.Oracle.com/javase/6/docs/api/Java/util/HashMap.html

Die interne Bucket-Struktur wird tatsächlich neu erstellt, wenn der load-Faktor überschritten wird, sodass die amortisierten Kosten von get und put 0 (1) sind.

Wenn die interne Struktur neu aufgebaut wird, führt dies zu einer Leistungsverschlechterung, die wahrscheinlich O (N) ist. Daher können einige get und put vor den amortized cost erforderlich sein. nähert sich wieder O(1). Planen Sie daher die anfängliche Kapazität und den Lastfaktor entsprechend, damit Sie weder Platz verschwenden noch einen vermeidbaren Neuaufbau der internen Struktur auslösen.

7
Eric J.

Um auch die Kommentare von templatetypedef zu verfolgen:

Die Implementierung einer Hashtabelle mit konstanter Zeit könnte eine Hashmap sein, mit der Sie eine boolesche Arrayliste implementieren können, die angibt, ob ein bestimmtes Element in einem Bucket vorhanden ist. Wenn Sie jedoch eine verknüpfte Liste für Ihre Hashmap implementieren, müssen Sie im schlimmsten Fall jeden Bucket durchlaufen und die Listenenden durchlaufen.

0
jim-zed-li