Dlaczego różne kolekcje Java mają różną domyślną pojemność?

11

Przyglądając się różnym konstruktorom kolekcji, pojawia się pytanie. Dlaczego ArrayList () konstruuje pustą listę o początkowej pojemności dziesięciu, a ArrayDeque () konstruuje pustą tablicę deque o początkowej pojemności wystarczającej do przechowywania 16 elementów.

java collections

— Stary Badman Gray
źródło

Nie wiedziałem, że ma limit pojemności. Po prostu dodaję nowe elementy za pomocą add (). To zawsze działa.

— Tulains Córdova

1

Myślę, że mówi o początkowym rozmiarze tablicy wewnątrz implementacji ArrayList. Jak sama nazwa wskazuje, ArrayList jest po prostu zwykłą tablicą pod okładkami i automatycznie tworzy większe tablice, gdy próbujesz dodać więcej elementów niż zawiera obecny rozmiar tablicy.

— dsw88

1

Myślę, że StringBuilder to kolejny, który ma domyślną pojemność, czy to było 10 czy 16?

— Ingo

@Ingo Interesujące. Nie wiedziałem nawet, że rzeczy poza kolekcjami są pomieszane z pojemnością, ale chyba ma to sens. W tym czasie nie było znacznika pojemności, więc nie wzbudziłem dużego zainteresowania innymi zastosowaniami.

— Old Badman Gray,

17

Krótka odpowiedź

Ponieważ pojemność ArrayDeque musi być potęgą dwóch, a 16 to najmniejsza potęga dwóch, czyli co najmniej 10.

ArrayDeque musi używać wszędzie wielu operacji%, aby owinąć tablicę liniową, która udaje, że jest okrągła.

a % bmożna wyrazić tak, a & (b - 1) jakby b była potęgą dwóch. Bitowe AND jest znacznie szybsze, więc pojemność ArrayDeque jest ograniczona do potęgi dwóch. Wszystkie operacje% są wykonywane z maskowaniem bitów zamiast rzeczywistego% w implementacji.

Z tego też powodu nowszy HashMap nie używa rozmiarów tabeli liczb pierwszych, lecz potęgę dwóch , ponieważ operacja% musi być wykonywana tak często i bitowo i jest o wiele szybsza.

Więc jeśli linia bazowa to 10, to struktury, które mają moc dwóch ograniczeń, powinny użyć 16, ponieważ jest to najmniejsza potęga dwóch, co najmniej 10.

— Esailija
źródło

3

Nie wykluczaj możliwości, że nie ma konkretnego powodu.

Możliwe, że te dwie kolekcje zostały napisane przez różne zespoły. Obaj wybrali niewielką liczbę jako domyślną pojemność, ale pierwsza drużyna pomyślała dziesiętnie i wybiera 10, podczas gdy druga drużyna myślała binarnie i wybiera 16.

— rem
źródło

1

Odpowiedź @ Esailija jest dobra w tym konkretnym przypadku.

Mówiąc bardziej ogólnie, jest to kompromis, który zależy od wielu czynników. Podam kilka przykładów:

Jak zwykle używana jest struktura danych ? Struktury danych, które są używane jako bufory danych, zazwyczaj wolałyby znacznie większą pojemność niż na przykład struktury danych używane dla małych krotek.
Jaki domyślny rozmiar danych mieści się w linii pamięci podręcznej na docelowej platformie procesora? Może mieć to duży wpływ na wydajność, jeśli domyślnie mieści się w linii pamięci podręcznej. Wybór 10 jest domyślnie w Javie, ponieważ tablica 10 32-bitowych słów plus obciążenie tablicy / obiektu mieści się w 64-bajtowej linii pamięci podręcznej.
Ile cenisz przestrzeń zamiast wydajności środowiska wykonawczego ? Jeśli chcesz uzyskać lepszą wydajność środowiska wykonawczego, zwykle lepiej wstępnie przydzielić więcej miejsca, aby uniknąć późniejszych dodatkowych alokacji.

W wyniku tych kompromisów zrozumiałe jest, że różne implementacje kolekcji mogą mieć inną optymalną domyślną pojemność.

— mikera
źródło