Rehashing w Hashmap [zamknięte]
Początkowa pojemność i współczynnik obciążenia to dwa parametry, które wpływają naHashMap
wydajność. Domyślny współczynnik obciążenia (.75
) oferuje dobry kompromis między kosztami czasu i miejsca. Wyższe wartości zmniejszają obciążenie przestrzeni, ale zwiększają koszt wyszukiwania.
Gdy element zostanie dodany doHashMap
, jest przypisany do segmentów w oparciu o wartość wynikającą z jego wartościhashCode
i rozmiar wiadraHashMap
. Aby zidentyfikować wiadro dla dowolnego użycia mapy Hashkey.hashCode()
i wykonaj pewną operację:
Bucket (index) = HashMap.indexFor(HashMap.hash(key.hashCode()),
entryArray.length)
Gdy liczba wpisów na mapie mieszającej przekracza iloczyn współczynnika obciążenia i bieżącej pojemności, mapa mieszania jest ponownie modyfikowana (wewnętrzne struktury danych są odbudowywane), tak że mapa mieszająca ma w przybliżeniu dwukrotnie większą liczbę segmentów.
Po odświeżeniu i przeniesieniu wszystkiego do nowej lokalizacji (kubełka itp.) Starsze elementy są również ponownie maskowane i zapisywane w nowym wiadrze zgodnie z nowymi kodami skrótu. Stara przestrzeń, która została przydzielona do przechowywania elementów, jest gromadzona w śmieciach.
Jeśli dwa wątki w tym samym czasie znalazły to terazHashMap
potrzebuje zmiany rozmiaru i oboje próbują zmienić rozmiar, co może spowodować sytuację rasowąHashMap
.
W sprawie procesu zmiany rozmiaruHashMap
, element w wiadrze, który jest przechowywany w połączonej liście, jest odwracany w trakcie migracji do nowego wiadra, ponieważ javaHashMap
nie dołącza nowego elementu do ogona, lecz dołącza nowy element na głowie, aby uniknąć przemieszczania się ogona. Jeśli zdarzy się sytuacja wyścigu, skończysz z nieskończoną pętlą.
Mam następujące pytania:
Dlaczego połączona lista dla każdego kubła jest odwracana w celu migracji do nowego wiadra?Jak warunki wyścigu mogą prowadzić do nieskończonej pętli?W jaki sposób zwiększenie liczby segmentów może zmniejszyć czas oczekiwania na wyszukiwanie?Elementy, które znajdują się w tym samym wiaderku, nadal będą razem w tym samym wiaderku po ponownym myciu?