Dlaczego wyższy współczynnik obciążenia w HashMap zwiększy koszt wyszukiwania?

Question

Z JavaDoc z HashMap:

Zgodnie z ogólną zasadą, współczynnik domyślny obciążenie (0,75) oferuje dobry kompromis pomiędzy kosztami czasie i przestrzeni. Wyższe wartości powodują zmniejszenie nadwyżki przestrzeni na przestrzeni , ale zwiększają koszt wyszukiwania (odzwierciedlone w większości operacji klasy HashMap, w tym get i put).

Jeśli mamy wyższą wartość, dlaczego zwiększyłoby to koszt wyszukiwania?

Answer 1

Hash stołu Load Factor jest zdefiniowana jako

n/s, przy czym stosunek liczby zachowanych wpisów n i wielkość s tablicy stołu wiadra.

Wysoka wydajność tabeli skrótów jest utrzymywana, gdy liczba kolizji jest niska. Gdy współczynnik obciążenia jest wysoki, zwiększa się prawdopodobieństwo kolizji.

Answer 2

Ma to związek z tym, jak HashTable jest zaimplementowane pod maską, używa kodów skrótu, a ponieważ algorytm do obliczania kodu skrótu nie jest doskonały, możesz mieć pewne kolizje, zwiększenie współczynnika obciążenia zwiększa prawdopodobieństwo kolizji , a w konsekwencji zmniejszenie wydajności odnośników ...

Answer 3

domyślny współczynnik obciążenia (0,75).

If declare load factor as 
1 the restructuring process only happens when number of elements are exceeding the capacity of the HashMap. 

Answer 4

Tutaj musimy najpierw zrozumieć, co pojemność i współczynnik obciążenia oznacza:

pojemność: jest to ilość wiader w dowolnej tabeli mieszania w danym momencie.

współczynnik obciążenia: Współczynnik obciążenia jest miarą tego, jak pełna tabela hash może dostać przed jego pojemność jest automatycznie zwiększana

więc bardziej współczynnik obciążenia jest bardziej zajęty stolik hash mógł się przed pojemności zwiększa .

• teraz otrzymują najlepszą możliwą realizację hashCode() tylko jedna wartość pójdzie w jednym wiadrze tutaj odnośnika koszt będzie minimum
• w najgorszym przypadku wszystkie wartości pójdzie w tym samym segmencie i odnośnika koszt byłby maksymalna
• w przeciętnego przypadku Poza tym, ten na pewno zależy od hashCode() realizacji, ale jeszcze jeden czynnik, który będzie odgrywał tutaj jest współczynnik obciążenia, , gdy bardziej zajęty będzie zbiór, tym większe będą szanse kolizji, a tym samym wyższy współczynnik obciążenia zwiększy koszty wyszukiwania w nieidealnym scenariuszu.

Answer 5

Obciążenie czynnik 0,75 można interpretować w ten sposób, stosując wzór (n/s, przy czym stosunek liczby zachowanych wpisów n i wielkość s tablicy stołu wiadra.):

Załóżmy, że masz 75 wartości, które musisz przechowywać w tabeli haszowania i masz 100 pustych bloków tablicowych do ich przechowywania, tutaj szanse kolizji są zminimalizowane, a współczynnik obciążenia wynosi 0,75.

Załóżmy, że masz 75 wartości do zapisania, a tylko 10 pustych bloków tablicy (współczynnik obciążenia 7.5) oznacza, że ​​będziesz miał kolizję i zastosujesz dowolne techniki rozwiązywania kolizji, które wydłużą Twój czas wyszukiwania.

Teraz, w inny sposób, masz 75 wpisów i 1000 pustych bloków tablicowych (współczynnik obciążenia 0,075), co prowadzi do pustych bloków, które są dużo marnowane.

W związku z tym zasada kciuka polega na tym, że wartość współczynnika obciążenia rośnie wraz ze wzrostem czasu wyszukiwania, a gdy zbliża się do 0, marnuje się więcej miejsca na dane.

Jest to zatem handel w czasoprzestrzeni.