Tidskompleksitet af HashMap, HashTable, HashSet, TreeMap

Time Complexity Hashmap



HashSet, hashtable og hashMap er alle baseret på hash-funktionen, tidskompleksiteten O (1), men hvis den er for dårlig, er den O (n)

TreeSet ==> O (log (n)) ==> Træbaseret søgning behøver kun at søge halvt



The reason for O(1) is that after the discrete, the subscript corresponding keyword

Hash er en hash eller endda en hash. Men jeg har altid haft et spørgsmål om hash-bordets tidskompleksitet. En streng, der skal gemmes, hashes til et relativt kort indeks af hash-funktionen, hvilket gør adgangshastigheden hurtigere. Men hvorfor når adgangskomplekset ved adgang det konstante niveau O (1)? ? Det tager ikke tid at søge efter et indeks, når du søger? Hvorfor ikke O (n)? n er længden af ​​hashbordet,



Hvis du har en dyb forståelse af konstruktionen af ​​Hashtable, ved du, Hashtable er en kombination af fordelene ved arrays og sammenkædede lister. Når Hashtable søger efter værdier, skal du først bruge værdien og længden af ​​Hashtable til at udføre modulo-operationen. Det opnåede nummer bruges direkte som indeks for indgangsarray i hashtable, fordi hashtable er sammensat af entry array, så det kan placeres direkte til den angivne position, der er ikke behov for at søge, selvfølgelig er der et problem her er hver post faktisk en sammenkædet liste. Hvis posten har mange værdier, skal den stadig gennemgås, så det kan siges, at tidskompleksiteten af ​​Hashtable fortrinsvis er O (1), men den værste er O (n). Når det er værst, er det alle værdierne i hashtabellen. Hashværdierne er de samme og tildeles alle i en post. Selvfølgelig er denne sandsynlighed ikke meget forskellig fra sandsynligheden for 100 millioner lotteri-billetter.



Det ser ud til at have den største indvirkning på tidskompleksiteten af ​​sløjfen på indgangslisten, og tidskompleksiteten af ​​den sammenkædede listeopslag er O (n), der er relateret til længden på den sammenkædede liste. Vi skal sikre, at længden af ​​den sammenkædede liste er 1, vi kan sige, at tidskompleksiteten kan tilfredsstille O (1). Men i dette tilfælde minimerer kun hash-algoritmen konflikten, så længden af ​​den linkede liste er så kort som muligt, og den ideelle tilstand er 1. Derfor kan det konkluderes, at søgetidskompleksiteten af ​​HashMap kun er O (1) og det værste er O (n) i det mest ideelle tilfælde, og det er garanteret, at denne ideelle tilstand ikke kontrolleres af vores udviklere.

Tidskompleksitet af fælles datastrukturer


http://www.cnblogs.com/aspirant/p/8902285.html
http://www.cnblogs.com/aspirant/p/8908399.html
http://www.cnblogs.com/aspirant/p/8906018.html