Dlaczego ArrayList rośnie w tempie 1,5, a dla Hashmap jest to 2? - java, arraylist, hashmap

Zgodnie z implementacją Sun Java, podczas rozbudowy ArrayList rośnie do początkowej pojemności 3/2, podczas gdy dla HashMap szybkość ekspansji jest podwójna. Z czego to wynika?

Zgodnie z implementacją, dla HashMap,pojemność powinna zawsze wynosić dwa. To może być powód zachowania HashMap. Ale w takim przypadku pytanie brzmi: dla HashMap, dlaczego pojemność zawsze powinna wynosić dwa.

Odpowiedzi:

Kosztowną częścią zwiększania pojemności ArrayList jest kopiowanie zawartości tablicy podkładowej nowej (większej).

Dla HashMap tworzy nową tablicę podkładową i oddanie wszystkie wpisy map w nowej tablicy. Im wyższa pojemność, tym mniejsze ryzyko kolizji. Jest to droższe i wyjaśnia, dlaczego współczynnik ekspansji jest wyższy. Powód dla wersji 1.5 vs. 2.0? Uważam to za „najlepszą praktykę” lub „dobrą kompromis”.

dla HashMap dlaczego pojemność zawsze powinna wynosić dwa?

Mogę wymyślić dwa powody.

1. Możesz szybko określić wiadro, do którego trafia kod skrótu. Potrzebujesz tylko bitowego AND i bez drogiego modulo. int bucket = hashcode & (size-1);

2. Powiedzmy, że mamy współczynnik wzrostu 1,7. Jeśli zaczniemy od rozmiaru 11, następny rozmiar to 18, a następnie 31. Nie ma problemu. Dobrze? Ale hashcodes napisów w Javie są obliczane ze współczynnikiem podstawowym 31. Wiadro, w które wchodzi napis,hashcode%31, jest następnie określany tylko przez ostatni znak ciągu. PA pa O(1) jeśli przechowujesz foldery, w których wszystkie kończą się /. Jeśli użyjesz na przykład rozmiaru 3^n, dystrybucja nie pogorszy się, jeśli zwiększysz n. Zaczynam od rozmiaru 3 do 9, każdy element w wiadrze 2, teraz przejdzie do koszyka 2,5 lub 7, w zależności od wyższej cyfry. To tak, jakby podzielić każde wiadro na trzy części. Dlatego preferowany byłby współczynnik liczby całkowitej. (Oczywiście to wszystko zależy od sposobu obliczania kodów skrótu, ale arbitralny czynnik wzrostu nie wydaje się „stabilny”).

Sposób, w jaki HashMap jest zaprojektowany / wdrożonypodstawowa liczba segmentów musi być potęgą 2 (nawet jeśli nadasz jej inny rozmiar, to będzie potęgą 2), więc rośnie za każdym razem dwa razy. ArrayList może mieć dowolny rozmiar i może być bardziej konserwatywny pod względem wzrostu.

Hashing wykorzystuje równomierne rozłożenie danych do segmentów. Algorytm próbuje zapobiec wielokrotnym wprowadzeniom do segmentów („kolizje skrótów”), ponieważ zmniejszają one wydajność.

Teraz, gdy pojemność HashMap zostanie osiągnięta,rozmiar jest zwiększany, a istniejące dane są ponownie dystrybuowane za pomocą nowych segmentów. Jeśli przyrost wielkości byłby zbyt mały, to ponowne przydzielanie miejsca i ponowna dystrybucja następowałyby zbyt często.

Nie mogę podać powodu, dla którego tak się dzieje (należy poprosić programistów Sun), ale aby zobaczyć, jak to się dzieje, zajrzyj do źródła:

1. HashMap: zobacz, jak zmienia się rozmiar HashMap do nowego rozmiaru (źródło linia 799)

        resize(2 * table.length);
   

2. ArrayList: źródło, linia 183:

   int newCapacity = (oldCapacity * 3)/2 + 1;
   

Aktualizacja: Przez pomyłkę podłączyłem źródła JDK Apache Harmony - zmieniłem je na JDK firmy Sun.

Ogólną zasadą unikania kolizji w Mapach jest utrzymywanie maksymalnego współczynnika obciążenia około 0,75 Aby zmniejszyć możliwość kolizji i uniknąć kosztownego procesu kopiowania, HashMap rośnie w większym tempie.

Również, jak mówi @Peter, musi to być potęga 2.