Jakie jest znaczenie współczynnika obciążenia w HashMap?

232

HashMapma dwie ważne właściwości: sizei load factor. Przejrzałem dokumentację Java, która mówi, że 0.75fjest to początkowy współczynnik obciążenia. Ale nie mogę znaleźć faktycznego wykorzystania tego.

Czy ktoś może opisać, jakie są różne scenariusze, w których musimy ustawić współczynnik obciążenia i jakie są przykładowe idealne wartości dla różnych przypadków?

Priyank Doshi
źródło

Odpowiedzi:

266

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

NPE
źródło
14
Inne odpowiedzi sugerują sprecyzowanie, capacity = N/0.75aby uniknąć powtórzenia, ale moja początkowa myśl właśnie się rozpoczęła load factor = 1. Czy takie podejście miałoby wady? Dlaczego by załadować czynnik wpływa get()i put()koszty eksploatacji?
supermitch
19
Współczynnik obciążenia = 1 skrót mapy z liczbą wpisów = pojemność będzie mieć statystycznie znaczącą liczbę kolizji (= gdy wiele kluczy generuje ten sam skrót). Gdy dojdzie do kolizji, czas wyszukiwania wydłuża się, ponieważ w jednym segmencie znajdzie się> 1 pasujących wpisów, dla których klucz musi być indywidualnie sprawdzany pod kątem równości. Szczegółowa matematyka: preshing.com/20110504/hash-collision-probabilities
atimb
8
Nie śledzę cię @atimb; Właściwość loadset służy tylko do określenia, kiedy należy zwiększyć rozmiar pamięci, prawda? - W jaki sposób zestaw obciążeń o wartości 1 zwiększyłby prawdopodobieństwo kolizji mieszających? - Algorytm mieszania nie wie, ile przedmiotów jest na mapie ani jak często zdobywa nowe „wiadra” pamięci itp. W przypadku dowolnego zestawu obiektów o tym samym rozmiarze, niezależnie od tego, jak są przechowywane, należy mieć takie samo prawdopodobieństwo powtarzających się wartości skrótu ...
BrainSlugs83
19
Prawdopodobieństwo kolizji skrótu jest mniejsze, jeśli rozmiar mapy jest większy. Na przykład elementy z kodami skrótu 4, 8, 16 i 32 zostaną umieszczone w tym samym segmencie, jeśli rozmiar mapy to 4, ale każdy element otrzyma własny segment, jeśli rozmiar mapy jest większy niż 32. Mapa o początkowym rozmiarze 4 i współczynniku obciążenia 1.0 (4 wiadra, ale wszystkie 4 elementy w jednym wiadrze) będzie w tym przykładzie średnio dwa razy wolniejsza niż inna ze współczynnikiem obciążenia 0,75 (8 wiader, dwa wiadra wypełnione - z elementem „4” i elementami „8”, „16”, „32”).
30
1
@Adelin Koszt wyszukiwania jest zwiększony dla wyższych współczynników obciążenia, ponieważ będzie więcej kolizji dla wyższych wartości, a sposób, w jaki Java obsługuje kolizje, polega na umieszczeniu elementów o tym samym haszu w tym samym segmencie przy użyciu struktury danych. Począwszy od Java 8, ta struktura danych jest drzewem wyszukiwania binarnego. To sprawia, że ​​czas wyszukiwania w najgorszym przypadku O (lg (n)) z najgorszym przypadkiem występuje, jeśli wszystkie dodane elementy mają ten sam kod skrótu.
Gigi Bayte 2
141

Domyślna początkowa pojemność HashMapujęć wynosi 16, a współczynnik obciążenia wynosi 0,75 f (tj. 75% aktualnej wielkości mapy). Współczynnik obciążenia reprezentuje, na jakim poziomie HashMappojemność 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ść w HashMapjego pojemności staje się 32.

użytkownik2791282
źródło
3
Chociaż twoja odpowiedź jest jasna, czy możesz powiedzieć, czy tuż po zapisaniu 12 par klucz-wartość pojemność wynosi 32, czy jest tak, że po dodaniu 13. wpisu pojemność w tym czasie zmienia się, a następnie wpis jest wstawiany.
userab
czy to oznacza, że ​​liczba wiader wzrosła o 2?
LoveMeow,
39

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:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

Dlatego wiadro jest prawdopodobnie puste, jeśli jest mniej niż

log(2)/log(s/(s - 1)) keys

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

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
Witaj świecie
źródło
4
Matematyki frajerzy FTW! Prawdopodobnie liczba .75została zaokrąglona do najbliższej łatwej do zrozumienia części log(2)i wygląda na mniejszą liczbę magiczną. Chciałbym zobaczyć aktualizację wartości domyślnej JDK, z powyższym komentarzem nad jej implementacją: D
Dekodowano
2
Naprawdę chcę polubić tę odpowiedź, ale jestem programistą JavaEE, co oznacza, że ​​matematyka nigdy nie była moją mocną stroną, więc bardzo niewiele rozumiem z tego, co napisałeś lol
searchengine27
28

Co 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ę.

Sujal Mandal
źródło
2
Możesz dodać trochę o tym, w jaki sposób hashCode jest redukowany do liczby z zakresu 1- {count bucket}, a więc nie jest on sam w sobie liczbą segmentów, ale ten wynik końcowy algorytmu hash obejmuje większy zasięg. HashCode nie jest algorytmem pełnego skrótu, jest wystarczająco mały, aby można go było łatwo przetworzyć. Więc nie ma pojęcia „darmowych wiader”, ale „minimalna liczba darmowych wiader”, ponieważ można przechowywać wszystkie elementy w tym samym wiaderku. Jest to raczej przestrzeń kluczowa kodu skrótu, która jest równa pojemności * (1 / współczynnik_obciążenia). 40 elementów, współczynnik obciążenia 0,25 = 160 łyżek.
user1122069,
Myślę, że czas wyszukiwania obiektu z LinkedListjest określany jako Amortized Constant Execution Timei oznaczony +jakoO(1)+
Raf
19

Z dokumentacji :

Współczynnik obciążenia jest miarą tego, jak pełne jest wypełnienie tabeli mieszającej, zanim jej pojemność zostanie automatycznie zwiększona

To naprawdę zależy od konkretnych wymagań, nie ma „ogólnej zasady” określania początkowego współczynnika obciążenia.

Óscar López
źródło
Dokumentacja mówi również; „Zasadniczo domyślny współczynnik obciążenia (.75) zapewnia dobry kompromis między kosztami czasu i przestrzeni.”. Więc dla każdego, kto nie jest pewien, domyślną zasadą jest dobra zasada.
ferekdoley
2

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.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

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.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

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.

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

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

          "the HashSet can automatically

        resize the number of buckets."

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.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

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.

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

Ś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

Ganesh Chowdhary Sadanala
źródło
1

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.

Brett Greenfield
źródło