Czy Java hashmap to naprawdę O (1)?

159

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 O (1), a jeśli tak, to jak to osiągają?

paxdiablo
źródło
1
Wiem, że to może nie być odpowiedź, ale pamiętam, że Wikipedia ma bardzo dobry artykuł na ten temat. Nie przegap sekcji analizy wyników
zwycięzca Hugo
28
Notacja Big O określa górną granicę dla konkretnego typu analizy, którą wykonujesz. Nadal powinieneś określić, czy interesuje Cię najgorszy przypadek, średni przypadek itp.
Dan Homerick

Odpowiedzi:

127

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ść) 2

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

SingleNegationElimination
źródło
Nawet w przypadku HTML nadal nie jestem zadowolony z ułamków. Oczyść je, jeśli możesz wymyślić dobry sposób na zrobienie tego.
SingleNegationElimination
4
W rzeczywistości powyższe mówi, że efekty O (log N) są pogrzebane, dla nie ekstremalnych wartości N, przez stały narzut.
Hot Licks
Technicznie rzecz biorąc, ta liczba jest oczekiwaną wartością liczby kolizji, która może równać się prawdopodobieństwu pojedynczej kolizji.
Simon Kuang
1
Czy jest to podobne do amortyzowanej analizy?
lostsoul 29
1
@ OleV.V. dobra wydajność HashMap zawsze zależy od dobrego rozmieszczenia funkcji skrótu. Możesz wymienić lepszą jakość mieszania na szybkość mieszania, używając kryptograficznej funkcji mieszania na wejściu.
SingleNegationElimination
38

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.

Konrad Rudolph
źródło
6
Zawsze myślałem, że górna granica jest najgorszym przypadkiem, ale wygląda na to, że się pomyliłem - możesz mieć górną granicę dla przeciętnego przypadku. Wygląda więc na to, że ludzie twierdzący, że O (1) powinni byli wyjaśnić, że dotyczy to przeciętnego przypadku. Najgorszym przypadkiem jest zbiór danych, w którym występuje wiele kolizji, które powodują, że jest on O (n). To ma teraz sens.
paxdiablo
2
Prawdopodobnie powinieneś jasno powiedzieć, że kiedy używasz notacji dużego O dla przeciętnego przypadku, mówisz o górnej granicy oczekiwanej funkcji wykonawczej, która jest jasno zdefiniowaną funkcją matematyczną. W przeciwnym razie twoja odpowiedź nie ma sensu.
ldog
1
gmatt: Nie jestem pewien, czy rozumiem twój zarzut: notacja duże-O jest z definicji górną granicą funkcji . Co innego mogłem zatem mieć na myśli?
Konrad Rudolph
3
Cóż, zwykle w literaturze komputerowej widzisz dużą notację O reprezentującą górne ograniczenie funkcji algorytmu w czasie wykonywania lub złożoności przestrzeni. W tym przypadku górna granica jest faktycznie na oczekiwaniu, które samo w sobie nie jest funkcją, ale operatorem na funkcjach (zmienne losowe) i jest w rzeczywistości całką (lebesgue). za pewnik i nie jest trywialne.
ldog
31

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

FogleBird
źródło
11
Cóż, ponieważ duże-O ma określać granice, nie ma znaczenia, czy jest bliżej O (1), czy nie. Nawet O (n / 10 ^ 100) nadal jest O (n). Rozumiem, że wydajność obniża współczynnik, ale to wciąż stawia algorytm na O (n).
paxdiablo
4
Analiza map skrótów jest zwykle przeprowadzana na przeciętnym przypadku, który wynosi O (1) (z koluzjami). W najgorszym przypadku możesz mieć O (n), ale zwykle tak nie jest. ze względu na różnicę - O (1) oznacza, że ​​otrzymujesz ten sam czas dostępu niezależnie od ilości pozycji na wykresie i tak jest zwykle (o ile istnieje dobra proporcja między wielkością tabeli a 'n ')
Liran Orevi
4
Warto też zwrócić uwagę, że nadal jest to dokładnie O (1), nawet jeśli skanowanie wiadra trochę trwa, bo są w nim już jakieś elementy. Dopóki zasobniki mają ustalony maksymalny rozmiar, jest to po prostu stały czynnik nieistotny dla klasyfikacji O (). Ale oczywiście może być jeszcze więcej elementów z "podobnymi" kluczami, więc te wiadra przepełniają się i nie można już zagwarantować stałej.
sth
@sth Dlaczego łyżki miałyby kiedykolwiek mieć ustalony maksymalny rozmiar !?
Navin
31

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.

Daniel James
źródło
16

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

ajb
źródło
4

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 → ∞.

IJ Kennedy
źródło
4

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

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

Satyanarayana Kakollu
źródło
1
Co oznacza stała alfa ?
Prahalad Deshpande
2

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!

jtb
źródło
2

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.

Antti Huima
źródło
2

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

Ramprabhu
źródło
1

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

Tobias Svensson
źródło
1
Zakłada się, że czas wykonywania jest ograniczony czasem wyszukiwania. W praktyce znajdziesz wiele sytuacji, w których funkcja skrótu wyznacza granicę (ciąg)
Stephan Eggermont
1

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

Nizar Grira
źródł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).

Ryan Emerle
źródło
4
Nie w praktycznych zastosowaniach. Gdy tylko użyjesz łańcucha jako klucza, zauważysz, że nie wszystkie funkcje skrótu są idealne, a niektóre są naprawdę powolne.
Stephan Eggermont
1

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.

sn.anurag
źródło
0

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.

Szara Pantera
źródło
„tak jest w większości przypadków”. Dokładniej, całkowity czas będzie dążył do K razy N (gdzie K jest stałe), ponieważ N dąży do nieskończoności.
ChrisW
7
To jest źle. Indeks w tablicy skrótów zostanie określony, hashCode % tableSizeco oznacza, że ​​z pewnością mogą wystąpić kolizje. Nie możesz w pełni wykorzystać 32-bitowych. O to właśnie chodzi w tablicach skrótów ... redukujesz dużą przestrzeń indeksowania do małej.
FogleBird
1
„masz gwarancję, że nie będzie kolizji”. what the hash) jeśli / kiedy próbuję wstawić trzy elementy.
ChrisW
Ale jak przekonwertować klucz na adres pamięci w O (1)? Mam na myśli jak x = tablica ["klucz"]. Klucz nie jest adresem pamięci, więc nadal musiałby to być wyszukiwanie O (n).
paxdiablo
1
„Wierzę, że jeśli nie zaimplementujesz hashCode, użyje on adresu pamięci obiektu”. Mógłby tego użyć, ale domyślnym hashCode dla standardowej Oracle Java jest w rzeczywistości 25-bitowa losowa liczba przechowywana w nagłówku obiektu, więc 64/32-bitowy nie ma znaczenia.
Boann