Wenn wir aus der Java-Perspektive schauen, können wir sagen, dass die Hashmapp-Suche konstante Zeit benötigt. Aber was ist mit interner Implementierung? Es müsste immer noch nach bestimmten Buckets (für die der Hashcode des Schlüssels übereinstimmt) nach verschiedenen übereinstimmenden Schlüsseln suchen. Warum sagen wir dann, dass das Hashmapp-Lookup konstante Zeit benötigt? Bitte erkläre.Warum Hashmapp-Lookup ist O (1), d. H. Konstante Zeit?
Unter den entsprechenden Annahmen über die Hash-Funktion, die verwendet wird, können wir sagen, dass Hash-Tabelle Lookups erwartet O (1) Zeit. Dies bedeutet, dass im Durchschnitt, die Menge der Arbeit, die eine Hash-Tabelle, um eine Suche durchzuführen ist höchstens eine Konstante ist.
Intuitiv, wenn Sie eine "gute" Hash-Funktion haben, würden Sie erwarten, dass Elemente würden mehr oder weniger gleichmäßig verteilt in der Hash-Tabelle, was bedeutet, dass die Anzahl der Elemente in jedem Eimer in der Nähe der Anzahl der Elemente wäre geteilt durch die Anzahl der Eimer. Wenn die Hashtabellenimplementierung diese Zahl niedrig hält (z. B. indem jedes Mal mehr Buckets hinzugefügt werden, wenn das Verhältnis von Elementen zu Buckets eine Konstante überschreitet), dann ist die erwartete Menge an Arbeit, die erledigt wird, eine Basisarbeitsmenge, um den Bucket auszuwählen Sie sollten gescannt werden und dann "nicht zu viel" daran arbeiten, die Elemente dort zu betrachten, denn nach Erwartung wird es nur eine konstante Anzahl von Elementen in diesem Bereich geben.
Dies bedeutet nicht, dass Hash-Tabellen garantiert O (1) Verhalten haben. Im schlimmsten Fall wird das Hashing-Schema tatsächlich degenerieren und alle Elemente werden in einem Bucket enden, was im schlimmsten Fall dazu führen kann, dass die Lookups Zeit benötigen (Θ (n)). Aus diesem Grund ist es wichtig, gute Hash-Funktionen zu entwickeln.
Für weitere Informationen möchten Sie vielleicht ein Algorithmik-Lehrbuch lesen, um die formale Herleitung zu sehen, warum Hashtabellen Suchvorgänge so effizient unterstützen. Dies ist normalerweise Teil eines typischen Universitätskurses über Algorithmen und Datenstrukturen und es gibt viele gute Ressourcen online.
Hoffe, das hilft!
Danke für die einfache und klare Antwort. Es beantwortet meine Frage sauber. – genonymous
Sie haben den Wert richtig beantwortet. Aber was ist mit Bucket Location? Wir wissen, dass für jeden Schlüssel (angenommen, die Hash-Funktion ist zu gut, die für jeden Schlüssel einen anderen Hash-Wert erzeugt) eine Tabelle erstellt wird, die den Bucket, d. H. Die verknüpfte Liste (bis Java 7), findet. Meine Frage ist, ob es 1000K verschiedene Schlüsselwerte mit 1000K Buckets gibt, wie hashmap sicherstellt, dass es o (1) gibt, um den Bucket-Standort zu ermitteln. Hoffe ich bin klar über die Frage. Vielen Dank. – Sam
@Sam Die Buckets werden normalerweise als Array gespeichert (entweder ein roher oder ein Wrapper wie 'ArrayList', der effizienten wahlfreien Zugriff unterstützt. Auf diese Weise können Sie nach der Berechnung der Hash-Funktion in die Zeit springen. O (1) (unabhängig von der Anzahl der Buckets) zum richtigen Bucket – templatetypedef
Der Schlüssel ist in dieser Aussage in der Dokumentation:
Wenn viele Zuordnungen in einer HashMap Instanz gespeichert werden, ist es mit einer ausreichend großen Kapazität zu schaffen wird die Zuordnungen erlaubt gespeichert, effizienter werden, als im Stich gelassen Es führt automatisches erneutes Laden durch, um die Tabelle zu vergrößern.
und
Der Lastfaktor ist ein Maß dafür, wie voll die Hash-Tabelle erlaubt ist, zu erhalten, bevor seine Kapazität automatisch erhöht wird. Wenn die Anzahl der Einträge in der Hash-Tabelle das Produkt aus dem Ladefaktor und der aktuellen Kapazität überschreitet, wird die Hash-Tabelle erneut erstellt (dh interne Datenstrukturen werden neu erstellt), sodass die Hash-Tabelle ungefähr die doppelte Anzahl an Buckets aufweist.
http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
Die interne Eimer Struktur tatsächlich, wenn der Faktor Last wieder aufgebaut werden überschritten wird, für die fortgeführten Anschaffungskosten von erhalten ermöglicht und setzen O (1) zu sein.
Beachten Sie, dass, wenn die interne Struktur neu aufgebaut wird, das bringt eine Leistungseinbuße, die O (N) wahrscheinlich sein, so ziemlich viele bekommen und setzen vor dem abgeschrieben erforderlich sein können Kosten O Ansätze (1) wieder. Planen Sie deshalb die Anfangskapazität und den Auslastungsfaktor entsprechend, damit Sie weder Platz verschwenden noch einen vermeidbaren Umbau der internen Struktur auslösen.
+1 für Hyperlink und entsprechend hervorgehobenen Text – genonymous
Um auch bis auf templatetypedef Kommentaren folgen:
Die konstante Zeit Implementierung einer Hash-Tabelle eine hashmap sein könnte, mit dem Sie eine boolean Array-Liste implementieren können, die ein bestimmtes Element besteht in einem Eimer zeigt an, ob. Wenn Sie jedoch eine verkettete Liste für Ihre Hashmappe implementieren, würde es im schlimmsten Fall erforderlich sein, dass Sie jeden Bucket durchlaufen und die Enden der Listen durchlaufen müssen.
möglich Duplikat von [Kann Hashtabellen wirklich sein O (1)] (http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o-o1) – Boann