Was ist der worst-case-Laufzeit von Hashing mit Verkettung?

Nehme an, dass die Anzahl der hash-Tabelle slots(sagen wir n) sind proportional zu der Anzahl der Elemente in der Tabelle(sagen wir m). Wir haben n = O(m),
load-Faktor l = O(m)/m = O(1)
Also Unter der Annahme von Simple Uniform Hashing, Suche in konstanter Zeit auf einen Durchschnitt. Das bedeutet für eine Durchschnittliche Suche dauert Zeit proportional zu der Länge der verketteten Liste, die ist die gleiche für alle slots und somit Konstante Zeit. Aber was ist mit dem worst-case-Laufzeit unter der Annahme der Simple Uniform Hashing. Ist es auch konstant sein oder es werden O(1 + l). Bitte erklären, ich bin verwirrt. [Referenz CLRS Seite 260]

Tut worst-case Zeit für die Un-erfolgreiche Suche unter der Annahme der Einfachen uniform hashing wird derselbe sein wie der Durchschnittliche Fall Zeit. Und worst-case Zeit für eine erfolgreiche Suche unter der Annahme der Einfachen uniform hashing wird anders sein als der Durchschnitt Fall Zeit.

  • Uniform-hashing ist nicht genug, um Ihnen einen guten worst-case bounds. Eine hash-Familie einheitlich ist, während eine bestimmte Funktion noch hashes jede Taste den gleichen Eimer. Wenn Sie bekommen können, die eine Universelle hash-Funktion, die Sie bekommen können O(logn) Grenzen mit hoher Wahrscheinlichkeit: stackoverflow.com/questions/4553624/hashmap-get-put-complexity/...
InformationsquelleAutor Sonali | 2013-11-27
  1. 3

    Unter der Annahme der Einfachen Uniform Hashing (d.h., dass eine hypothetische Hash-Funktion verteilt Gegenstände in die slots der hash-Tabelle), ich glaube, das worst-case-performance für eine lookup-operation würde die gleiche wie die average-case (bei einer erfolglosen lookup) - Θ(n/m + 1) (durchschnittlichen Fall als pro Wikipedia).

    Warum? Nun, betrachten, dass unter der obigen Annahme, jeder Steckplatz in der Tabelle die gleiche Anzahl von Elementen in der Kette. Weil dieses, beide den durchschnittlichen Fall und den schlechtesten Fall zu involvieren, suchen durch alle Elemente in einer der Ketten.

    Dies ist natürlich eine ziemlich optimistische Annahme - die it-Praxis, können wir selten /nie vorgeben, eine hash-Funktion, die gleichmäßig zu verteilen, einige unbekannte Menge von Daten (und wir selten bauen hash-Funktionen, die speziell für Daten-sets), aber zur gleichen Zeit, sind wir kaum zu bekommen, um die wahre worst-case.

    Im Allgemeinen, die worst-case-Laufzeit einer lookup-oder remove-operation für eine hash-Tabelle mit Verkettung ist Θ(n).

    In beiden Fällen legen Sie können immer noch umgesetzt werden, wie Θ(1), da können Sie einfach legen Sie Sie an der Vorderseite der Kette. Das heißt, wenn wir zulassen, dass Duplikate (wie Jim erwähnt), weil, wenn nicht, müssen wir zunächst zu prüfen, ob es das schon gibt (also z.B. eine Suche).

    Schlimmsten Fall passiert, wenn alle hash-Elemente auf den gleichen Wert, so müsstest du eine wirklich lange Kette, im wesentlichen drehen Sie Ihren Daten-Struktur in einer verketteten Liste.

    |--------|
|element1| -> element2 -> element3 -> element4 -> element5
|--------|
|  null  |
|--------|
|  null  |
|--------|
|  null  |
|--------|
|  null  |
|--------|
    • Legen Sie umgesetzt werden können, wie O(1)? Nur wenn Sie zulassen, dass Duplikate.
    • Ach ja, richtig. Danke. Ich vergaß, dass. Es wurde ein Hinweis Hinzugefügt.
    • "unter der obigen Annahme, jeder Steckplatz in der Tabelle die gleiche Anzahl von Elementen in der Kette" - völlig falsch. das ist nicht das, was Simple Uniform Hashing bedeutet. Nur weil die hash-Funktion verteilt die ganzen - Reihe von Elementen, es nicht bedeutet wird, dass Sie für eine bestimmte Teilmenge. Schlimmste Zeit, wie Sie sagten, ist O(n).
    InformationsquelleAutor Dukeling
Schreibe einen Kommentar