HashMap get / put złożoność

136

Przywykliśmy do mówienia, że HashMap get/putoperacje to O (1). Jednak zależy to od implementacji skrótu. Domyślnym skrótem obiektu jest w rzeczywistości adres wewnętrzny w stercie maszyny JVM. Czy na pewno wystarczy stwierdzić, że get/putsą O (1)?

Dostępna pamięć to inny problem. Jak rozumiem z javadoców, HashMap load factorpowinno to być 0.75. Co jeśli nie mamy wystarczającej ilości pamięci w JVM i load factorprzekroczymy limit?

Więc wygląda na to, że O (1) nie jest gwarantowane. Czy to ma sens, czy czegoś mi brakuje?

Michał
źródło
1
Warto przyjrzeć się pojęciu zamortyzowanej złożoności. Zobacz na przykład tutaj: stackoverflow.com/questions/3949217/time-complexity-of-hash-table Złożoność najgorszego przypadku nie jest najważniejszą miarą dla tabeli haszowania
Dr G
3
Prawidłowo - jest amortyzowane O (1) - nigdy nie zapomnij o tej pierwszej części, a nie będziesz mieć takich pytań :)
Inżynier
Najgorszym przypadkiem złożoności czasowej jest O (logN) od czasu Java 1.8, jeśli się nie mylę.
Tarun Kolla

Odpowiedzi:

230

To zależy od wielu rzeczy. Zwykle jest to O (1), z przyzwoitym hashem, który sam w sobie jest stały ... ale możesz mieć skrót, którego obliczenie zajmuje dużo czasu, a jeśli na mapie skrótów jest wiele elementów, które zwracają ten sam kod skrótu, getbędzie musiał je powtórzyć, wzywając equalskażdego z nich do znalezienia dopasowania.

W najgorszym przypadku a HashMapma wyszukiwanie O (n) z powodu przechodzenia przez wszystkie wpisy w tym samym zasobniku mieszania (np. Jeśli wszystkie mają ten sam kod skrótu). Na szczęście ten najgorszy scenariusz nie pojawia się zbyt często w prawdziwym życiu, z mojego doświadczenia. Więc nie, O (1) z pewnością nie jest gwarantowane - ale zazwyczaj należy to założyć, rozważając, jakich algorytmów i struktur danych użyć.

W JDK 8 HashMapzostał zmodyfikowany tak, że jeśli klucze można porównywać w celu uporządkowania, to każdy gęsto zapełniony zasobnik jest implementowany jako drzewo, więc nawet jeśli istnieje wiele wpisów z tym samym kodem skrótu, złożoność wynosi O (log n). Może to powodować problemy, jeśli masz typ klucza, w którym równość i kolejność są oczywiście różne.

I tak, jeśli nie masz wystarczającej ilości pamięci na mapę skrótów, będziesz miał kłopoty ... ale to będzie prawdą niezależnie od używanej struktury danych.

Jon Skeet
źródło
@marcog: Zakładasz O (n log n) dla pojedynczego wyszukiwania ? To brzmi dla mnie głupio. Będzie to oczywiście zależeć od złożoności funkcji skrótu i ​​równości, ale jest mało prawdopodobne, aby zależało to od rozmiaru mapy.
Jon Skeet
1
@marcog: Więc co zakładasz, że jest O (n log n)? Wstawienie n elementów?
Jon Skeet
1
+1 za dobrą odpowiedź. Czy możesz podać w swojej odpowiedzi linki takie jak ten wpis Wikipedii dotyczący tabeli skrótów ? W ten sposób bardziej zainteresowany czytelnik może dostać się do szczegółów zrozumienia, dlaczego udzieliłeś odpowiedzi.
David Weiser
2
@SleimanJneidi: Nadal jest, jeśli klucz nie implementuje porównywalnego <T> `- ale zaktualizuję odpowiedź, gdy będę miał więcej czasu.
Jon Skeet
1
@ ip696: Tak, putjest „amortyzowane O (1)” - zwykle O (1), czasami O (n) - ale rzadko na tyle, aby się zrównoważyć.
Jon Skeet
9

Nie jestem pewien, czy domyślnym hashcode jest adres - jakiś czas temu przeczytałem źródło OpenJDK do generowania hashcode i pamiętam, że było to coś nieco bardziej skomplikowanego. Wciąż nie jest to coś, co gwarantuje dobrą dystrybucję. Jest to jednak do pewnego stopnia dyskusyjne, ponieważ niewiele klas, których używałbyś jako kluczy w hashmap, używa domyślnego hashcode - dostarczają własne implementacje, które powinny być dobre.

Co więcej, to, czego możesz nie wiedzieć (znowu opiera się to na czytaniu źródła - nie jest to gwarantowane), to to, że HashMap miesza hash przed jego użyciem, aby mieszać entropię z całego słowa do dolnych bitów, czyli tam, gdzie jest potrzebne dla wszystkich oprócz największych haszów. To pomaga radzić sobie z hashami, które same tego nie robią, chociaż nie przychodzą mi do głowy żadne typowe przypadki, w których byś to zobaczył.

Wreszcie, gdy tabela jest przeciążona, degeneruje się w zestaw równolegle połączonych list - wydajność staje się O (n). W szczególności liczba pokonanych łączy będzie średnio o połowę mniejsza niż współczynnik obciążenia.

Tom Anderson
źródło
6
Cholera. Zdecydowałem się wierzyć, że gdybym nie musiał tego wpisywać na ekranie dotykowym telefonu komórkowego, mógłbym pokonać Jona Arkusza do uderzenia. Jest za to odznaka, prawda?
Tom Anderson
9

Wspomniano już, że hasmapy są O(n/m)przeciętne, jeśli njest to liczba przedmiotów i mrozmiar. Wspomniano również, że w zasadzie cała sprawa może ułożyć się w pojedynczo połączoną listę zO(n) czasem zapytania. (To wszystko zakłada, że ​​obliczenie skrótu jest stałe).

Jednak często nie wspomina się, że przynajmniej z prawdopodobieństwem 1-1/n(więc dla 1000 przedmiotów jest to 99,9% szansy), największe wiadro nie zostanie wypełnione bardziej niż O(logn)! Stąd dopasowanie średniej złożoności drzew wyszukiwania binarnego. (A stała jest dobra, ściślejsza granica jest (log n)*(m/n) + O(1)).

Wszystko, co jest wymagane do tego teoretycznego ograniczenia, to użycie dość dobrej funkcji skrótu (patrz Wikipedia: Universal Hashing . Może być tak proste jak a*x>>m). I oczywiście osoba, która podaje wartości do haszowania, nie wie, w jaki sposób wybrałeś swoje losowe stałe.

TL; DR: Z bardzo dużym prawdopodobieństwem najgorszym przypadkiem jest złożoność metody get / put O(logn).

Thomas Ahle
źródło
(I zauważ, że nic z tego nie zakłada losowych danych. Prawdopodobieństwo wynika wyłącznie z wyboru funkcji skrótu)
Thomas Ahle,
Mam również to samo pytanie dotyczące złożoności wykonywania wyszukiwania na mapie skrótów. Wydawałoby się, że jest to O (n), ponieważ współczynniki stałe powinny zostać usunięte. 1 / m jest współczynnikiem stałym i dlatego spada pozostawiając O (n).
nickdu,
8

Działanie HashMap jest zależne od czynnika implementacji hashCode. Dla idealnego scenariusza powiedzmy, że dobra implementacja skrótu, która zapewnia unikalny kod skrótu dla każdego obiektu (bez kolizji hash), wtedy najlepszym, najgorszym i średnim scenariuszem byłby scenariusz O (1). Rozważmy scenariusz, w którym zła implementacja hashCode zawsze zwraca 1 lub taki skrót, który ma kolizję. W tym przypadku złożoność czasowa wynosiłaby O (n).

Przechodząc teraz do drugiej części pytania o pamięć, to tak, ograniczenie pamięci zajmie się JVM.

Pranav
źródło
6

Zgadzam się z:

  • ogólna zamortyzowana złożoność O (1)
  • zła hashCode()implementacja może spowodować wiele kolizji, co oznacza, że ​​w najgorszym przypadku każdy obiekt trafia do tego samego zasobnika, a zatem O ( N ), jeśli każdy zasobnik jest popartyList .
  • od wersji Java 8 HashMapdynamicznie zastępuje węzły (lista połączona) używane w każdym zasobniku przez TreeNodes (czerwono-czarne drzewo, gdy lista jest większa niż 8 elementów), co skutkuje najgorszą wydajnością O ( logN ).

Ale to NIE jest do końca prawdą, jeśli chcemy być w 100% dokładni. Implementacja hashCode()i typ klucza Object(niezmienny / buforowany lub będący kolekcją) może również wpływać na rzeczywistą złożoność w ściśle określonych warunkach.

Przyjmijmy następujące trzy przypadki:

  1. HashMap<Integer, V>
  2. HashMap<String, V>
  3. HashMap<List<E>, V>

Czy mają taką samą złożoność? Cóż, zamortyzowana złożoność pierwszego wynosi, zgodnie z oczekiwaniami, O (1). Ale co do reszty, musimy również obliczyćhashCode() element wyszukiwania, co oznacza, że ​​być może będziemy musieli przejść przez tablice i listy w naszym algorytmie.

Załóżmy, że rozmiar wszystkich powyższych tablic / list wynosi k . Wtedy HashMap<String, V>i HashMap<List<E>, V>będzie miał O (k) zamortyzowaną złożoność i podobnie O ( k + logN ) w najgorszym przypadku w Javie8.

* Zauważ, że użycie Stringklucza jest bardziej złożonym przypadkiem, ponieważ jest niezmienny, a Java buforuje wynik hashCode()w zmiennej prywatnej hash, więc jest obliczany tylko raz.

/** Cache the hash code for the string */
    private int hash; // Default to 0

Ale powyższe ma również swój własny najgorszy przypadek, ponieważ String.hashCode()implementacja Javy sprawdza, czy hash == 0przed obliczeniem hashCode. Ale hej, istnieją niepuste Ciągi, które generują a hashcoderówne zero, takie jak „f5a5a608”, zobacz tutaj , w takim przypadku zapamiętywanie może nie być pomocne.

Kostas Chalkias
źródło
2

W praktyce jest to O (1), ale w rzeczywistości jest to straszne i matematycznie bezsensowne uproszczenie. Notacja O () mówi, jak zachowuje się algorytm, gdy rozmiar problemu dąży do nieskończoności. Hashmap get / put działa jak algorytm O (1) dla ograniczonego rozmiaru. Z punktu widzenia pamięci komputera i adresowania limit jest dość duży, ale daleki od nieskończoności.

Kiedy ktoś mówi, że hashmap get / put to O (1), to naprawdę należy powiedzieć, że czas potrzebny na get / put jest mniej więcej stały i nie zależy od liczby elementów w hashmap, o ile może to być hashmap przedstawione w rzeczywistym systemie komputerowym. Jeśli problem wykracza poza ten rozmiar i potrzebujemy większych haszmapów, to po pewnym czasie z pewnością liczba bitów opisujących jeden element również wzrośnie, gdy zabraknie nam możliwych do opisania różnych elementów. Na przykład, jeśli użyliśmy hashmap do przechowywania 32-bitowych liczb, a później zwiększymy rozmiar problemu, abyśmy mieli więcej niż 2 ^ 32-bitowe elementy w hasmapie, to poszczególne elementy zostaną opisane z więcej niż 32 bitami.

Liczba bitów potrzebnych do opisania poszczególnych elementów to log (N), gdzie N to maksymalna liczba elementów, więc get i put to naprawdę O (log N).

Jeśli porównasz to z zestawem drzew, którym jest O (log n), to zestaw hash to O (long (max (n)) i po prostu czujemy, że to jest O (1), ponieważ w pewnej implementacji max (n) jest stała, nie zmienia się (wielkość przechowywanych przez nas obiektów mierzona jest w bitach), a algorytm obliczający kod skrótu jest szybki.

Wreszcie, gdyby znaleźć element w dowolnej strukturze danych O (1), stworzylibyśmy informacje z powietrza. Mając strukturę danych zawierającą n elementów, mogę wybrać jeden element na n różnych sposobów. Dzięki temu mogę zakodować informacje o bitach dziennika (n). Jeśli mogę to zakodować w bicie zerowym (to oznacza O (1)), to stworzyłem nieskończenie kompresujący algorytm ZIP.

Peter Verhas
źródło
Czy zatem nie powinno być złożoności zestawu drzew O(log(n) * log(max(n)))? Chociaż porównanie w każdym węźle może być sprytniejsze, w najgorszym przypadku musi sprawdzić wszystkie O(log(max(n))bity, prawda?
maaartinus