Złożoność czasowa metod HashMap

Question

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)

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.

Answer 1

źródło jest często jako: http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O (1)
• size: O (1)
• values: O (n) (na przechodzenie przez iteracyjnej)

Answer 2

Zawsze możesz rzucić okiem na kod źródłowy i sprawdzić go samodzielnie.
W każdym razie ... Raz sprawdziłem kod źródłowy i pamiętam, że istnieje zmienna o nazwie size, która zawsze zawiera liczbę elementów w HashMap, więc size() jest O(1).

Answer 3

Kod do usunięcia (jak w rt.jar dla HashMap) to:

/** 
* Removes and returns the entry associated with the specified key 
* in the HashMap. Returns null if the HashMap contains no mapping 
* for this key. 
*/ 
final Entry<K,V> removeEntryForKey(Object key) { 
    int hash = (key == null) ? 0 : hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    Entry<K,V> prev = table[i]; 
    Entry<K,V> e = prev; 

    while (e != null) { 
     Entry<K,V> next = e.next; 
     Object k; 
     if (e.hash == hash && 
      ((k = e.key) == key || (key != null && key.equals(k)))) { 
      modCount++; 
      size--; 
      if (prev == e) 
       table[i] = next; 
      else 
       prev.next = next; 
      e.recordRemoval(this); 
      return e; 
     } 
     prev = e; 
     e = next; 
    } 

    return e; 
} 

Najwyraźniej najgorszym przypadkiem jest O (n).

Answer 4

wyszukiwania: O (1 + k/n)
Płytka: O (1)
Usuń: O (1 + k/n) gdzie k jest nie. elementów kolizji dodanych do tej samej listy wyników (elementy k miały taki sam kod haszowania)

Wstawienie to O (1), ponieważ element ten jest wstawiany bezpośrednio na początku listy odnośników.

Amortyzowane złożoności czasowe są bliskie wartości O (1) podanej w dobrym haśle. Jeśli jesteś zbyt zaniepokojony czasem szukania, spróbuj rozwiązać kolizje za pomocą BinarySearchTree zamiast domyślnej implementacji java tj. LinkedList