Waarom zie ik steeds verschillende runtime-complexiteiten voor deze functies in een hashtabel?
Op wiki zijn zoeken en verwijderen O(n) (ik dacht dat het punt van hashtabellen was om constant te zoeken, dus wat heeft het voor zin als zoeken O(n) is).
In sommige cursusnotities van een tijdje geleden zie ik een breed scala aan complexiteiten, afhankelijk van bepaalde details, waaronder een met alle O(1). Waarom zou een andere implementatie worden gebruikt als ik alle O(1) kan krijgen?
Als ik standaard hash-tabellen gebruik in een taal als C++ of Java, wat kan ik dan verwachten van de complexiteit van de tijd?
Antwoord 1, autoriteit 100%
Hashtabellenzijn O(1)gemiddeld en afgeschrevencomplexiteit van het geval, maar lijdt aan O(n)worst casetijdscomplexiteit. [En ik denk dat hier je verwarring zit]
Hash-tabellen hebben om twee redenen last van O(n)slechtste tijdscomplexiteit:
- Als er te veel elementen in dezelfde sleutel zijn gehasht: in deze sleutel kijken kan
O(n)tijd kosten. - Zodra een hashtabel zijn load balanceheeft gepasseerd, moet hij opnieuw hashen [maak een nieuwe grotere tabel, en plaats elk element opnieuw in de tabel].
Er wordt echter gezegd dat het O(1)gemiddeld en afgeschreven geval is omdat:
- Het komt zelden voor dat veel items naar dezelfde sleutel worden gehasht [als je een goede hash-functie hebt gekozen en je hebt geen al te grote load balance.
- De rehash-bewerking, die
O(n)is, kan hoogstens gebeuren nan/2bewerkingen, die allemaal worden verondersteldO(1): Dus als je de gemiddelde tijd per operatie optelt, krijg je:(n*O(1) + O(n)) / n) = O(1)
Opmerking vanwege het probleem met opnieuw hashen – een realtime-applicaties en applicaties die een lage latentienodig hebben – zouden dat niet moeten doen gebruik een hashtabel als hun gegevensstructuur.
EDIT:Nog een probleem met hashtabellen: cache
Een ander probleem waarbij u mogelijk prestatieverlies ziet in grote hashtabellen, is te wijten aan cacheprestaties. Hash-tabellen hebben last van slechte cacheprestaties, en dus voor grote verzamelingen – de toegangstijd kan langer duren, omdat u het relevante deel van de tabel uit het geheugen opnieuw in de cache moet laden.
Antwoord 2, autoriteit 12%
Idealiter is een hashtabel O(1). Het probleem is als twee sleutels niet gelijk zijn, maar ze resulteren in dezelfde hash.
Stel je bijvoorbeeld voor dat de strings “het was de beste tijd, het was de slechtste tijd”en “Green Eggs and Ham”beide resulteerden in een hash-waarde van 123.
Als de eerste string wordt ingevoegd, wordt deze in bucket 123 geplaatst. Als de tweede string wordt ingevoegd, ziet hij dat er al een waarde bestaat voor bucket 123. Het zou dan de nieuwe waarde vergelijken met de bestaande waarde en zien dat ze niet gelijk zijn. In dit geval wordt voor die sleutel een array of gekoppelde lijst gemaakt. Op dit punt wordt het ophalen van deze waarde O(n)omdat de hashtabel elke waarde in die bucket moet doorlopen om de gewenste te vinden.
Om deze reden, bij gebruik van een Hash-tabel, is het belangrijk om een sleutel te gebruiken met een echt goede hash-functie die zowel snel is en niet vaak resulteert in dubbele waarden voor verschillende objecten.
logisch?
Antwoord 3, Autoriteit 6%
Sommige hash-tabellen (cuckoo hashing ) hebben gegarandeerd o (1) lookup
Antwoord 4, Autoriteit 4%
Misschien keek je naar de ruimte-complexiteit? Dat is o (n). De andere complexiteiten zijn zoals verwacht op de hash tabel invoer. De zoekcomplexiteit nadert o (1) als het aantal emmers toeneemt. Als u in het ergste geval slechts één emmer in de hashtabel hebt, is de zoekcomplexiteit O (n).
Bewerken In reactie op commentaar Ik denk niet dat het correct is om te zeggen o (1) is het gemiddelde geval. Het is echt (zoals de Wikipedia-pagina zegt) O (1 + N / K) waar K de Hash-tabelgrootte is. Als K groot genoeg is, is het resultaat effectief o (1). Maar stel dat k 10 is en n 100 is. In dat geval heeft elke emmer gemiddeld 10 vermeldingen, dus de zoektijd is absoluut niet o (1); Het is een lineaire zoekopdracht tot 10 inzendingen.
Antwoord 5
hangt af van de hoe u hashing implementeert, in het ergste geval kan het naar o (n) gaan, in het beste geval is het 0 (1) (in het algemeen kunt u bereiken als uw DS niet gemakkelijk is)