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,

Odpowiedzi:

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