HashMap get / put złożoność

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?

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.

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.

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).

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.

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.

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.