Por que coleções Java diferentes têm capacidade padrão diferente?

11

Olhando para diferentes construtores de coleções, a pergunta vem à mente. Por que ArrayList () constrói uma lista vazia com capacidade inicial de dez e ArrayDeque () constrói um deque de matriz vazio com capacidade inicial suficiente para armazenar 16 elementos.

java collections Velho Badman Grey
fonte
Eu não sabia que tinha um limite de capacidade. Simplesmente adiciono novos elementos com add (). Isso sempre funciona.
Tulains Córdova
1
Eu acho que ele está falando sobre o tamanho inicial da matriz dentro da implementação ArrayList. Como o próprio nome indica, ArrayList é apenas uma matriz antiga simples sob as capas e cria matrizes maiores automaticamente quando você tenta adicionar mais elementos do que o tamanho atual da matriz.
dsw88
1
Eu acho que StringBuilder é outro que tem uma capacidade padrão, eram 10 ou 16?
Ingo
@Ingo Interesting. Eu nem sabia que coisas fora das coleções estavam confusas, mas acho que faz sentido. Na época, não havia etiqueta de capacidade, então eu não despertei muito interesse em outros usos.
Old Badman Grey

Respostas:

17

Resposta curta

Como a capacidade do ArrayDeque deve ser uma potência de dois e 16 é a menor potência de dois que é pelo menos 10.

O ArrayDeque precisa usar muitas% de operações em todos os lugares para envolver uma matriz linear que finge ser circular.

a % bpode ser expresso como a & (b - 1) se b fosse uma potência de dois. O AND bit a bit é massivamente mais rápido, portanto a capacidade do ArrayDeque é restrita a poder de dois. Todas as% operações são executadas com máscara de bits em vez de% real na implementação.

É também por isso que o HashMap mais recente não usa tamanhos de tabelas de números primos, mas sim dois , novamente porque a operação% precisa ser executada com tanta frequência e pouco a pouco e é muito mais rápida.

Portanto, se a linha de base for 10, as estruturas com potência de duas limitações devem usar 16, pois é a menor potência de duas que é pelo menos 10.

Esailija
fonte
3

Não exclua a possibilidade de que não haja motivo específico.

Pode ser que essas duas coleções tenham sido escritas por equipes diferentes. Ambos escolheram um número pequeno como capacidade padrão, mas o primeiro time pensou decimalmente e escolheu 10, enquanto o segundo time pensou em binário e escolheu 16.

rem
fonte
1

A resposta de @ Esailija é boa para este caso específico.

Mais geralmente, porém, é um trade-off que depende de muitos fatores. Vou dar alguns exemplos:

  • Como a estrutura de dados é normalmente usada ? As estruturas de dados usadas como buffers de dados normalmente preferem uma capacidade muito maior do que as estruturas de dados usadas para tuplas pequenas, por exemplo.
  • Qual tamanho padrão de dados se encaixa em uma linha de cache na plataforma de CPU de destino? Pode fazer uma grande diferença no desempenho se o padrão se encaixar na linha de cache. A escolha de 10 é como padrão em Java pode muito bem ser porque uma matriz de 10 palavras de 32 bits mais a sobrecarga da matriz / objeto se encaixa em uma linha de cache de 64 bytes.
  • Quanto você valoriza a eficiência de espaço versus tempo de execução ? Se você deseja um melhor desempenho em tempo de execução, geralmente é melhor pré-alocar mais espaço para evitar realocações extras posteriormente.

Como resultado dessas trocas, é compreensível que diferentes implementações de coleta possam ter uma capacidade padrão ideal diferente.

Mikera
fonte