Ponieważ pracuję nad złożonością czasową, przeszukałem bibliotekę klasy Oracle w języku Java, aby uzyskać złożoność czasową niektórych standardowych metod używanych na listach, mapach i klasach. (Dokładniej, ArrayList, HashMap i HashSet)Złożoność czasowa metod HashMap
Teraz, kiedy patrząc na HashMap javadoc page, tylko naprawdę mówić o metodach get()
i put()
.
Metody nadal muszę wiedzieć to:
remove(Object o)
size()
values()
myślę że remove()
będzie taka sama złożoność jako get()
, O(1)
, zakładając, że nie mają olbrzymi HashMap z równych hashCodes, itp itd ..
Dla size()
ja też założyć O(1)
, ponieważ HashSet, który również nie ma porządku, ma size()
metodę ze złożoności O(1)
.
Jeden mam pojęcia, jest values()
- Nie jestem pewien, czy ta metoda będzie po prostu jakoś „kopia” HashMap, dając złożoność czasową O(1)
, lub jeśli będzie musiał iteracyjne nad HashMap, czyniąc złożoność równa ilości elementów przechowywanych w HashMap.
Dzięki.
Btw jaki sposób 'values ()' może dać 'O (1)', nawet jeśli to w jakiś sposób " skopiuj "HashMap? – Pacerier
przy okazji, twój link jest zepsuty – Hengameh
Czy możesz podać dokładną złożoność (średnią lub najgorszą), której szukasz w swoim pytaniu? Złożoność metody remove() będzie się odpowiednio różnić, jak słusznie zauważyłem: @JavaGuy – Dinesh