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

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?

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

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.

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

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

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.

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

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

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.