Dokumentacja wyjaśnia to całkiem dobrze:
Wystąpienie HashMap ma dwa parametry, które wpływają na jego wydajność: pojemność początkową i współczynnik obciążenia. Pojemność to liczba segmentów w tabeli skrótów, a początkowa pojemność to po prostu pojemność w momencie tworzenia tabeli skrótów. Współczynnik obciążenia jest miarą tego, jak pełne jest wypełnienie tabeli mieszającej, zanim jej pojemność zostanie automatycznie zwiększona. Gdy liczba wpisów w tabeli skrótów przekracza iloczyn współczynnika obciążenia i bieżącej pojemności, tabela skrótów jest ponownie gromadzona (to znaczy, wewnętrzne struktury danych są przebudowywane), dzięki czemu tabela skrótów ma w przybliżeniu dwukrotność liczby segmentów.
Zasadniczo domyślny współczynnik obciążenia (.75) zapewnia dobry kompromis między kosztami czasu i przestrzeni. Wyższe wartości zmniejszają narzut miejsca, ale zwiększają koszt wyszukiwania (odzwierciedlony w większości operacji klasy HashMap, w tym get i put). Przy ustalaniu początkowej pojemności należy wziąć pod uwagę oczekiwaną liczbę wpisów na mapie i jej współczynnik obciążenia, aby zminimalizować liczbę operacji ponownego ładowania. Jeśli początkowa pojemność jest większa niż maksymalna liczba wpisów podzielona przez współczynnik obciążenia, nigdy nie wystąpią żadne operacje ponownego ładowania.
Podobnie jak w przypadku wszystkich optymalizacji wydajności, dobrym pomysłem jest unikanie przedwczesnej optymalizacji (tj. Bez twardych danych o tym, gdzie są wąskie gardła).
capacity = N/0.75
aby uniknąć powtórzenia, ale moja początkowa myśl właśnie się rozpoczęłaload factor = 1
. Czy takie podejście miałoby wady? Dlaczego by załadować czynnik wpływaget()
iput()
koszty eksploatacji?Domyślna początkowa pojemność
HashMap
ujęć wynosi 16, a współczynnik obciążenia wynosi 0,75 f (tj. 75% aktualnej wielkości mapy). Współczynnik obciążenia reprezentuje, na jakim poziomieHashMap
pojemność powinna zostać podwojona.Na przykład iloczyn pojemności i współczynnika obciążenia jak
16 * 0.75 = 12
. Oznacza to, że po zapisaniu 12. pary klucz-wartość wHashMap
jego pojemności staje się 32.źródło
W rzeczywistości z moich obliczeń „idealny” współczynnik obciążenia jest bliższy log 2 (~ 0,7). Chociaż każdy współczynnik obciążenia mniejszy niż ten da lepszą wydajność. Myślę, że 0,75 prawdopodobnie został wyciągnięty z kapelusza.
Dowód:
Łańcuchów można uniknąć, a przewidywania gałęzi wykorzystać, przewidując, czy wiadro jest puste, czy nie. Wiadro jest prawdopodobnie puste, jeśli prawdopodobieństwo, że będzie puste, przekroczy 0,5.
Niech s reprezentuje rozmiar, a n liczbę dodanych kluczy. Korzystając z twierdzenia dwumianowego, prawdopodobieństwo pustego segmentu wynosi:
Dlatego wiadro jest prawdopodobnie puste, jeśli jest mniej niż
Gdy s osiąga nieskończoność i jeśli liczba dodanych kluczy jest taka, że P (0) = .5, to n / s zbliża się szybko do log (2):
źródło
.75
została zaokrąglona do najbliższej łatwej do zrozumienia częścilog(2)
i wygląda na mniejszą liczbę magiczną. Chciałbym zobaczyć aktualizację wartości domyślnej JDK, z powyższym komentarzem nad jej implementacją: DCo to jest współczynnik obciążenia?
Jaka pojemność ma zostać wyczerpana, aby HashMap mógł zwiększyć swoją pojemność?
Dlaczego współczynnik obciążenia?
Współczynnik obciążenia wynosi domyślnie 0,75 początkowej pojemności (16), dlatego 25% koszyków będzie wolnych, zanim nastąpi wzrost pojemności, a to sprawia, że wiele nowych koszyków z nowymi kodami skrótu wskazuje na ich istnienie tuż po wzroście liczba wiader.
Dlaczego warto zachować wiele bezpłatnych koszy i jaki jest wpływ przechowywania bezpłatnych koszy na wydajność?
Jeśli ustawisz współczynnik ładowania na 1.0, może się zdarzyć coś bardzo interesującego.
Załóżmy, że dodajesz obiekt x do mapy hash, której hashCode ma wartość 888, a w tablicy skrótów reprezentujących kod skrótu jest wolny, więc obiekt x zostaje dodany do koszyka, ale teraz ponownie powiedz, jeśli dodajesz inny obiekt y, którego hashCode jest również 888 wtedy twój obiekt y zostanie na pewno dodany, ALE na końcu segmentu ( ponieważ segmenty są niczym innym jak implementacją LinkedList przechowującą klucz, wartość i następną ) teraz ma to wpływ na wydajność! Ponieważ twój obiekt y nie jest już obecny w wiadrze, jeśli wykonasz wyszukiwanie, nie zajmie to czasu O (1)tym razem zależy to od ilości przedmiotów w tym samym wiadrze. Nawiasem mówiąc, nazywa się to kolizją skrótu i dzieje się tak nawet wtedy, gdy współczynnik ładowania jest mniejszy niż 1.
Korelacja między wydajnością, kolizją skrótu i współczynnikiem ładowania?
Niższy współczynnik obciążenia = więcej wolnych łyżek = mniejsze ryzyko kolizji = wysoka wydajność = duże zapotrzebowanie na miejsce.
Popraw mnie, jeśli gdzieś się mylę.
źródło
LinkedList
jest określany jakoAmortized Constant Execution Time
i oznaczony+
jakoO(1)+
Z dokumentacji :
To naprawdę zależy od konkretnych wymagań, nie ma „ogólnej zasady” określania początkowego współczynnika obciążenia.
źródło
Dla HashMap DEFAULT_INITIAL_CAPACITY = 16 i DEFAULT_LOAD_FACTOR = 0,75f oznacza to, że MAKSYMALNA liczba WSZYSTKICH wpisów w HashMap = 16 * 0,75 = 12 . Po dodaniu trzynastego elementu pojemność (rozmiar tablicy) HashMap zostanie podwojona! Idealna ilustracja odpowiedziała na to pytanie: zdjęcie pochodzi stąd:
https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html
źródło
Jeśli wiadra się zapełniają, musimy przejrzeć
bardzo długa lista linków.
I to jest w pewnym sensie pokonanie sedna.
Oto przykład, w którym mam cztery wiadra.
Do tej pory mam słonia i borsuka.
To całkiem niezła sytuacja, prawda?
Każdy element ma zero lub jeden element.
Teraz dodajemy jeszcze dwa elementy do naszego zestawu HashSet.
To też nie jest takie złe.
Każde wiadro ma tylko jeden element. Więc jeśli chcę wiedzieć, czy to zawiera pandę?
Mogę bardzo szybko spojrzeć na wiadro nr 1, a nie jest
tam i
Wiedziałem, że nie ma go w naszej kolekcji.
Jeśli chcę wiedzieć, czy zawiera kota, patrzę na wiadro
numer 3,
Znajduję kota, bardzo szybko wiem, czy jest w naszym
kolekcja.
Co jeśli dodam koala, to nie jest takie złe.
Może teraz zamiast w wiadrze numer 1 tylko patrzę
jeden element
Muszę spojrzeć na dwa.
Ale przynajmniej nie muszę patrzeć na słonia, borsuka i
kot.
Jeśli znów szukam pandy, może być tylko w wiadrze
numer 1 i
Nie muszę patrzeć na nic innego niż wydrę i
koala.
Ale teraz umieszczam aligatora w wiadrze nr 1 i możesz
zobaczyć może dokąd to zmierza.
Że jeśli wiadro numer 1 staje się coraz większe i większe
większy, to w zasadzie muszę wszystko przejrzeć
te elementy do znalezienia
coś, co powinno znajdować się w wiadrze nr 1.
Jeśli zacznę dodawać ciągi do innych segmentów,
prawda, problem staje się coraz większy w każdym
pojedyncze wiadro.
Jak powstrzymać nasze wiadra przed zapełnieniem?
Rozwiązaniem jest tutaj
Jest HashSet zdaje sobie sprawę, że wiadra dostają
zbyt pełne.
Traci tę zaletę tego jednego wyszukiwania
elementy.
I po prostu stworzy więcej wiader (zwykle dwa razy tak jak poprzednio) i
następnie umieść elementy w odpowiednim wiadrze.
Oto nasza podstawowa implementacja HashSet z osobnym
łańcuchy. Teraz utworzę „samozmieniający się zestaw HashSet”.
Ten HashSet zorientuje się, że wiadra są
robi się zbyt pełny i
potrzebuje więcej wiader.
loadFactor to kolejne pole w naszej klasie HashSet.
loadFactor reprezentuje średnią liczbę elementów na
wiadro,
powyżej którego chcemy zmienić rozmiar.
loadFactor to równowaga między przestrzenią a czasem.
Jeśli wiadra się przepełnią, zmienimy rozmiar.
To oczywiście wymaga czasu, ale
może zaoszczędzić nam czasu na drodze, jeśli łyżki to
trochę bardziej pusty.
Zobaczmy przykład.
Oto HashSet, do tej pory dodaliśmy cztery elementy.
Słoń, pies, kot i ryba.
W tym momencie zdecydowałem, że loadFactor,
próg,
średnia liczba elementów na wiadro, które są w porządku
z wynosi 0,75.
Liczba segmentów to buckets.length, czyli 6, i
w tym momencie nasz HashSet ma cztery elementy, więc
obecny rozmiar to 4.
Zmienimy rozmiar naszego zestawu HashSet, czyli dodamy więcej wiader,
gdy średnia liczba elementów na wiadro przekracza
loadFactor.
To jest, gdy bieżący rozmiar podzielony przez segmenty. Długość wynosi
większy niż loadFactor.
W tym momencie średnia liczba elementów na wiadro
to 4 podzielone przez 6.
4 elementy, 6 wiader, czyli 0,67.
To mniej niż próg, który ustawiłem na 0,75, więc jesteśmy
w porządku.
Nie musimy zmieniać rozmiaru.
Ale teraz załóżmy, że dodajemy świstaka.
Świstak skończyłby w wiadrze nr 3.
W tym momencie currentSize to 5.
A teraz średnia liczba elementów na wiadro
to currentSize podzielony przez buckets.length.
To 5 elementów podzielonych przez 6 wiader to 0,83.
A to przekracza współczynnik obciążenia, który wynosił 0,75.
Aby rozwiązać ten problem, aby
wiadra może trochę
bardziej puste, aby operacje takie jak ustalenie, czy a
wiadro zawiera
element będzie trochę mniej skomplikowany, chcę zmienić rozmiar
mój zestaw Hash.
Zmiana rozmiaru zestawu HashSet wymaga dwóch kroków.
Najpierw podwoję liczbę wiader, miałem 6 wiader,
teraz mam 12 wiader.
Zauważ, że loadFactor, który ustawiłem na 0,75, pozostaje taki sam.
Ale liczba zmienionych wiader wynosi 12,
liczba elementów pozostała taka sama, wynosi 5.
5 podzielone przez 12 to około 0,42, czyli znacznie poniżej naszego
Współczynnik obciążenia,
więc teraz mamy się dobrze.
Ale nie skończyliśmy, ponieważ niektóre z tych elementów są w
niewłaściwe wiadro.
Na przykład słoń.
Słoń był w wiadrze numer 2, ponieważ liczba
postacie w słoniu
miał 8 lat
Mamy 6 wiader, 8 minus 6 to 2.
Właśnie dlatego znalazł się na drugim miejscu.
Ale teraz, gdy mamy 12 wiader, 8 mod 12 to 8, więc
słoń nie należy już do wiadra nr 2.
Słoń należy do wiadra nr 8.
A co z świstakiem?
Woodchuck był tym, który zaczął ten cały problem.
Świstak trafił do wiadra nr 3.
Ponieważ 9 mod 6 to 3.
Ale teraz robimy 9 mod 12.
9 mod 12 to 9, świstak trafia do wiadra nr 9.
I widzisz zaletę tego wszystkiego.
Teraz wiadro numer 3 ma tylko dwa elementy, podczas gdy wcześniej miało 3.
Oto nasz kod,
gdzie mieliśmy nasz zestaw HashSet z oddzielnym łańcuchem tym
nie zmieniłem rozmiaru.
Oto nowa implementacja, w której używamy zmiany rozmiaru.
Większość tego kodu jest taka sama,
nadal będziemy ustalać, czy zawiera
wartość już.
Jeśli nie, to ustalimy, które to wiadro
powinien wejść do i
następnie dodaj go do tego segmentu, dodaj do LinkedList.
Ale teraz zwiększamy pole currentSize.
currentSize było polem, które śledziło liczbę
elementów w naszym zestawie Hash.
Zwiększymy to, a potem spojrzymy
przy średnim obciążeniu
średnia liczba elementów na wiadro.
Zrobimy ten podział tutaj.
Żeby się upewnić, musimy trochę rzucić
że otrzymamy podwójne.
Następnie porównamy to średnie obciążenie z polem
które ustawiłem jako
Na przykład 0,75, kiedy utworzyłem ten zestaw HashSet
loadFactor.
Jeśli średnie obciążenie jest większe niż loadFactor,
oznacza to, że na wiadrze jest za dużo elementów
średnia i muszę ponownie wstawić.
Oto nasza implementacja metody ponownego wstawiania
wszystkie elementy.
Najpierw utworzę lokalną zmienną o nazwie oldBuckets.
Co odnosi się do wiader w ich obecnym stanie
zanim zacznę zmieniać rozmiar wszystkiego.
Uwaga: Nie tworzę jeszcze nowej tablicy połączonych list.
Po prostu zmieniam nazwę wiader na oldbuckets.
Pamiętajcie, że wiadra były polem w naszej klasie, idę
aby teraz utworzyć nową tablicę
połączonych list, ale będzie zawierało dwa razy więcej elementów
tak jak za pierwszym razem.
Teraz muszę ponownie wprowadzić,
Powtórzę wszystkie stare wiadra.
Każdy element w oldBuckets jest LinkedList ciągów
to jest wiadro.
Przejdę przez to wiadro i wezmę w to każdy element
wiadro.
A teraz włożę go ponownie do nowych koszyków.
Otrzymam jego hashCode.
Dowiem się, jaki to indeks.
A teraz dostaję nowy segment, nowy LinkedList z
ciągi i
Dodam to do tego nowego wiadra.
Podsumowując, HashSets, jak widzieliśmy, są tablicami Linked
Listy lub wiadra.
HashSet samozmieniający się może zrealizować używając pewnego współczynnika lub
źródło
Wybrałbym rozmiar tabeli n * 1,5 lub n + (n >> 1), dałoby to współczynnik obciążenia 0,66666 ~ bez podziału, co jest powolne w większości systemów, szczególnie w systemach przenośnych, w których nie ma podziału sprzęt.
źródło