Worst-case-Zeitkomplexität put/get HashMap

Was ist das worst-case Zeitkomplexität einer Hashmap, wenn der hashcode der Tasten sind immer gleich.

In meinem Verständnis: so Wie jeder Schlüssel hat die gleiche hashcode wird es immer wieder die gleichen Eimer und eine Schleife durch, um zu prüfen, für die equals-Methode, also für beide bekommen und setzen Sie die Zeit-Komplexität O(n), Bin ich Recht?

Ich mich mit diesem HashMap get/put-Komplexität aber es beantwortet nicht meine Frage.

Auch hier Wiki-Hash-Tabelle geben Sie die Worst-case-Zeit-Komplexität für einfügen ist O(1) und erhalten O(n), warum ist es so?

InformationsquelleAutor Vishal | 2011-11-17

  1. 9

    Ja, im schlimmsten Fall Ihren hash-map wird ausarten in eine verknüpfte Liste und Sie erleiden eine O(N) Strafe für Suchvorgänge, sowie Einfügungen und Löschungen, und beide erfordern eine lookup-operation (danke an die Kommentare für den Hinweis auf den Fehler in meiner früheren Antwort).

    Gibt es einige Möglichkeiten der Minderung der worst-case-Verhalten, wie durch die Verwendung einer self-balancing tree anstelle einer verlinkten Liste für den Eimer überlaufen - dies reduziert die worst-case-Verhalten von O(logn) anstelle von O(n).

    So setzen Sie nicht brauchen, um eine Schleife durch die Eimer, um zu überprüfen gleich, und wenn es true zurückgibt, dann ersetzen Sie andernfalls fügen Sie einfach? führende Komplexität auf O(n)?
    Diese Aussage ist falsch "O(1) einfügen können erreicht werden, wenn das neue Objekt Hinzugefügt wird Leiter der Eimer". Der Grund dafür ist, Sie haben zu Durchlaufen verknüpften Liste, um festzustellen, ob dieser Schlüssel bereits vorhanden ist, in der Karte oder nicht. Sagen, ich bin einfügen 1,3,4,3 .Wenn ich jetzt einfügen element an index 3 in meiner Karte, es würde fallen in den gleichen Eimer wie die anderen, und jetzt ist meine Karte schon 3(element mit dem index 1), so dass 3 soll nicht mehr eingesteckt.Und für die Prüfung, die 3 ist schon da ich muss die Iteration über die Liste.
    Für gute hash-Funktionen, der Schlimmste Fall ist immer logn siehe meine Antwort an stackoverflow.com/questions/4553624/hashmap-get-put-complexity/...

    InformationsquelleAutor sk.

  2. 1

    In Java 8 die HashMap-Implementierung:

    Griff Häufig HashMap Kollisionen mit Ausgeglichenen Bäumen: Im Falle von hohen hash-Kollisionen, dadurch verbessert sich die worst-case performance von O(n) O(log n).

    Vom hier.

    Richtig, aber nur, wenn Schlüssel-Typ implementiert Vergleichbar.

    InformationsquelleAutor Abdul

  3. 0

    in offenen hashing, haben Sie eine verknüpfte Liste, um Objekte zu speichern, die den gleichen hashcode. also:
    zum Beispiel, Sie haben eine Hash-Tabelle mit der Größe 4.
    1) angenommen, Sie speichern wollen, ein Objekt mit hashcode = 0. das Objekt wird dann zugeordnet werden, in index - (0 mod 4 = ) 0.
    2) dann wird Sie wieder wollen, setzen Sie ein anderes Objekt mit hashcode = 8. dieses Objekt wird zugeordnet-index (8 mod 4 = ) 0, so erinnern wir uns, dass der index 0 ist schon gefüllt mit unserem ersten Objekt, so haben wir die zweite neben der ersten.

    [0]=>linkedList{object1, object2}
[1]=>null
[2]=>null
[3]=>null

    3) was sind die Schritte für die Suche? 1. Sie haben hash des Schlüssel-Objekts und davon ausgehen, dass es hashcode ist 8, so werden Sie weitergeleitet auf index (8 mod 4 = ) 0, und dann, weil es mehr als ein Objekt gespeichert, die im gleichen index befinden, wir haben auf der Suche nach one-by-one alle gespeicherten Objekte in der Liste, bis Sie finden, die gepasst haben, oder bis das Ende der Liste. als Beispiel hat 2 Objekte, die gespeichert werden in der gleichen Hash-index 0, und die gesuchte Objekt liegt direkt in der Ende der linkedlist, so müssen Sie gehen Sie durch alle gespeicherten Objekte. das ist, warum es ist O(n) worst case.
    worst case ist aufgetreten, wenn alle gespeicherten Objekts in dem gleichen index in der hashtable. so werden Sie gespeichert werden, in einer linkedlist, in der wir (können) müssen gehen durch alle von Ihnen finden Sie unsere gesuchte Objekt.

    hoffe, dies hilft,.

    InformationsquelleAutor simaremare

  4. -6

    Beim einlegen, es spielt keine Rolle wo in den Eimer, setzen Sie es, so können Sie einfach legen Sie es irgendwo, so einfügen O(1).

    Lookup ist O(n) da haben Sie, um eine Schleife durch jedes Objekt und stellen Sie sicher, dass es der ist, den Sie gesucht haben (wie du schon angemerkt).

    Warum dies O(n) ? Wir sind immer Eimer index der HashMap, bevor Sie sich in ein Element, so brauchen wir nicht zu suchen in den gesamten Eimer, statt der angegebenen Eimer und seine Elemente (Entry-Objekt).
    Wenn alles hat einen hashcode, der 1, dann wird der angegebene bucket und seine Elemente" ist alles in der Karte.
    Sie tun müssen, um eine Suche zu tun, ein insert. ergo O(n)

    InformationsquelleAutor Jon Newmuis

Schreibe einen Kommentar