Czy Java hashmap to naprawdę O (1)?

Widziałem kilka interesujących twierdzeń dotyczących haszmap SO re Java i ich O(1)czasu wyszukiwania. Czy ktoś może wyjaśnić, dlaczego tak jest? O ile te hashmapy nie różnią się znacznie od któregokolwiek z algorytmów haszujących, na których zostałem zakupiony, zawsze musi istnieć zbiór danych zawierający kolizje.

W takim przypadku wyszukiwanie będzie O(n)raczej niż O(1).

Czy ktoś może wyjaśnić, czy są O (1), a jeśli tak, to jak to osiągają?

Szczególną cechą HashMap jest to, że w przeciwieństwie do, powiedzmy, zrównoważonych drzew, jej zachowanie jest probabilistyczne. W takich przypadkach zwykle najbardziej pomocne jest mówienie o złożoności w kategoriach prawdopodobieństwa wystąpienia najgorszego przypadku. W przypadku mapy skrótów jest to oczywiście przypadek kolizji w odniesieniu do tego, jak pełna jest mapa. Zderzenie jest dość łatwe do oszacowania.

p _kolizja = n / pojemność

Tak więc mapa skrótów z nawet niewielką liczbą elementów prawdopodobnie doświadczy przynajmniej jednej kolizji. Notacja Big O pozwala nam zrobić coś bardziej fascynującego. Zauważ, że dla dowolnej, ustalonej stałej k.

O (n) = O (k * n)

Możemy użyć tej funkcji, aby poprawić wydajność mapy skrótów. Zamiast tego moglibyśmy pomyśleć o prawdopodobieństwie maksymalnie 2 kolizji.

p _{kolizja x 2} = (n / pojemność) ²

To jest dużo niższe. Ponieważ koszt obsługi jednej dodatkowej kolizji nie ma znaczenia dla wydajności Big O, znaleźliśmy sposób na poprawę wydajności bez faktycznej zmiany algorytmu! Możemy to uogólnić

p _{kolizja xk} = (n / pojemność) ^k

A teraz możemy zignorować dowolną liczbę kolizji i otrzymać znikome prawdopodobieństwo wystąpienia większej liczby kolizji, niż uwzględnimy. Prawdopodobieństwo można uzyskać do arbitralnie małego poziomu, wybierając właściwe k, a wszystko to bez zmiany rzeczywistej implementacji algorytmu.

Mówimy o tym, mówiąc, że mapa hash ma dostęp O (1) z dużym prawdopodobieństwem

Wydaje się, że mieszasz zachowanie w najgorszym przypadku ze średnim (oczekiwanym) czasem wykonywania. Pierwsza z nich jest rzeczywiście O (n) dla tabel skrótów w ogóle (tj. Nie używa idealnego haszowania), ale rzadko ma to znaczenie w praktyce.

Każda niezawodna implementacja tablicy mieszania, w połączeniu z przyzwoitym hashem, ma wydajność pobierania O (1) z bardzo małym współczynnikiem (w rzeczywistości 2) w oczekiwanym przypadku, z bardzo wąskim marginesem wariancji.

W Javie HashMap działa, używając hashCode do zlokalizowania zasobnika. Każdy zasobnik to lista elementów znajdujących się w tym zasobniku. Elementy są skanowane przy użyciu równych dla porównania. Podczas dodawania elementów rozmiar HashMap jest zmieniany po osiągnięciu określonego procentu obciążenia.

Tak więc czasami będzie musiał porównać z kilkoma przedmiotami, ale generalnie jest znacznie bliżej O (1) niż O (n). Ze względów praktycznych to wszystko, co powinieneś wiedzieć.

Pamiętaj, że o (1) nie oznacza, że ​​każde wyszukiwanie bada tylko jedną pozycję - oznacza to, że średnia liczba sprawdzonych pozycji pozostaje stała względem liczby pozycji w kontenerze. Jeśli więc potrzeba średnio 4 porównań, aby znaleźć przedmiot w kontenerze zawierającym 100 elementów, znalezienie przedmiotu w kontenerze zawierającym 10000 elementów powinno zająć również średnio 4 porównania, a dla dowolnej innej liczby elementów (zawsze jest trochę rozbieżności, szczególnie w punktach, w których tabela skrótów jest ponownie mieszana i gdy jest bardzo mała liczba elementów).

Więc kolizje nie uniemożliwiają kontenerowi wykonywania operacji o (1), o ile średnia liczba kluczy na zasobnik pozostaje w ustalonym zakresie.

Wiem, że to stare pytanie, ale w rzeczywistości jest na nie nowa odpowiedź.

Masz rację, że mapa skrótów nie jest tak naprawdę O(1), ściśle mówiąc, ponieważ liczba elementów staje się dowolnie duża, ostatecznie nie będziesz w stanie wyszukiwać w stałym czasie (a notacja O jest definiowana w kategoriach liczb, które mogą stać się arbitralnie duże).

Ale to nie znaczy, że złożoność czasu rzeczywistego jest O(n) - ponieważ nie ma reguły, która mówi, że segmenty muszą być implementowane jako lista liniowa.

W rzeczywistości Java 8 implementuje zasobniki, TreeMapsgdy przekraczają one próg, co stanowi rzeczywisty czas O(log n).

Jeśli liczba segmentów (nazwij to b) jest utrzymywana na stałym poziomie (typowy przypadek), to wyszukiwanie wynosi w rzeczywistości O (n).
Gdy n staje się duże, liczba elementów w każdym segmencie wynosi średnio n / b. Jeśli rozwiązywanie kolizji odbywa się w jeden ze zwykłych sposobów (na przykład lista połączona), wyszukiwanie ma postać O (n / b) = O (n).

Notacja O dotyczy tego, co się dzieje, gdy n staje się coraz większe. Może być mylące, gdy zostanie zastosowane do niektórych algorytmów, a tego przykładem są tabele skrótów. Wybieramy liczbę wiader w oparciu o liczbę elementów, z którymi mamy do czynienia. Kiedy n jest mniej więcej tego samego rozmiaru co b, to wyszukiwanie jest w przybliżeniu stałe w czasie, ale nie możemy tego nazwać O (1), ponieważ O jest zdefiniowane w kategoriach granicy jako n → ∞.

O(1+n/k)gdzie kjest liczba wiader.

Jeśli implementacja jest ustawiona, k = n/alphato O(1+alpha) = O(1)ponieważ alphajest stałą.

Ustaliliśmy, że standardowy opis wyszukiwania w tablicy skrótów jako O (1) odnosi się do oczekiwanego czasu średniego przypadku, a nie ścisłej wydajności w najgorszym przypadku. W przypadku rozwiązywania kolizji z tablicą mieszającą z łączeniem łańcuchowym (takim jak hashmap Javy) jest to technicznie O (1 + α) z dobrą funkcją skrótu , gdzie α jest współczynnikiem obciążenia tabeli. Nadal jest stała, o ile liczba przechowywanych obiektów nie jest większa niż stały współczynnik większy niż rozmiar tabeli.

Wyjaśniono również, że ściśle mówiąc, możliwe jest skonstruowanie danych wejściowych, które wymagają wyszukiwań O ( n ) dla dowolnej deterministycznej funkcji skrótu. Ale warto też wziąć pod uwagę najgorszy oczekiwany czas, który jest inny niż średni czas wyszukiwania. Używając łańcuchów, jest to O (1 + długość najdłuższego łańcucha), na przykład Θ (log n / log log n ), gdy α = 1.

Jeśli interesują Cię teoretyczne sposoby osiągania wyników wyszukiwania najgorszego przypadku w oczekiwanym czasie, możesz przeczytać o dynamicznym doskonałym haszowaniu, które rozwiązuje kolizje rekurencyjnie z inną tabelą skrótów!

Jest to O (1) tylko wtedy, gdy funkcja haszująca jest bardzo dobra. Implementacja tablicy mieszającej języka Java nie chroni przed złymi funkcjami mieszającymi.

To, czy musisz powiększać tabelę podczas dodawania elementów, czy nie, nie ma znaczenia dla pytania, ponieważ dotyczy czasu wyszukiwania.

Elementy wewnątrz HashMap są przechowywane jako tablica połączonych list (węzłów), każda połączona lista w tablicy reprezentuje zasobnik dla unikalnej wartości skrótu jednego lub więcej kluczy.
Podczas dodawania wpisu w HashMap, hashcode klucza służy do określenia położenia zasobnika w tablicy, na przykład:

location = (arraylength - 1) & keyhashcode

Tutaj & reprezentuje bitowy operator AND.

Na przykład: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Podczas operacji get używa tego samego sposobu do określenia położenia zasobnika dla klucza. W najlepszym przypadku każdy klucz ma unikalny kod skrótu i ​​daje w wyniku unikalny przedział dla każdego klucza, w tym przypadku metoda get poświęca czas tylko na określenie lokalizacji zasobnika i pobranie wartości, która jest stała O (1).

W najgorszym przypadku wszystkie klucze mają ten sam kod skrótu i ​​są przechowywane w tym samym zasobniku, co powoduje przejście przez całą listę, która prowadzi do O (n).

W przypadku java 8 zasobnik listy połączonej jest zastępowany mapą drzewa, jeśli rozmiar wzrośnie do więcej niż 8, zmniejsza to wydajność wyszukiwania w najgorszym przypadku do O (log n).

Zasadniczo dotyczy to większości implementacji tablic mieszania w większości języków programowania, ponieważ sam algorytm tak naprawdę się nie zmienia.

Jeśli w tabeli nie ma kolizji, wystarczy wykonać jedno wyszukiwanie, dlatego czas wykonywania wynosi O (1). Jeśli występują kolizje, musisz wykonać więcej niż jedno wyszukiwanie, co obniża wydajność w kierunku O (n).

To zależy od algorytmu, który wybierzesz, aby uniknąć kolizji. Jeśli Twoja implementacja używa oddzielnych łańcuchów, najgorszy scenariusz ma miejsce, w którym każdy element danych jest haszowany do tej samej wartości (na przykład zły wybór funkcji skrótu). W takim przypadku wyszukiwanie danych nie różni się od wyszukiwania liniowego na połączonej liście, tj. O (n). Jednak prawdopodobieństwo takiego zdarzenia jest znikome, a wyszukiwania najlepszych i średnich przypadków pozostają stałe, tj. O (1).

Pomijając naukowców, z praktycznego punktu widzenia, HashMaps powinny być akceptowane jako mające nieistotny wpływ na wydajność (chyba że Twój profiler mówi ci inaczej).

Tylko w teoretycznym przypadku, gdy hashcodes są zawsze różne, a przedział dla każdego skrótu jest inny, będzie istnieć O (1). W przeciwnym razie ma stałą kolejność, tj. Przy zwiększaniu wartości hashmap jej kolejność poszukiwań pozostaje stała.

Oczywiście wykonanie funkcji hashmap będzie zależało od jakości funkcji hashCode () dla danego obiektu. Jeśli jednak funkcja jest zaimplementowana w taki sposób, że prawdopodobieństwo kolizji jest bardzo niskie, będzie miała bardzo dobre wyniki (nie jest to ściśle O (1) w każdym możliwym przypadku, ale w większości przypadków).

Na przykład domyślną implementacją w Oracle JRE jest użycie losowej liczby (która jest przechowywana w instancji obiektu, aby się nie zmieniała - ale również wyłącza stronnicze blokowanie, ale to inna dyskusja), więc prawdopodobieństwo kolizji jest bardzo niski.