Pourquoi différentes collections Java ont-elles une capacité par défaut différente?

11

En regardant différents constructeurs de collections, la question vient à l'esprit. Pourquoi ArrayList () construit-il une liste vide avec une capacité initiale de dix et ArrayDeque () construit un tableau vide deque avec une capacité initiale suffisante pour contenir 16 éléments.

java collections Old Badman Grey
la source
Je n'avais pas de nouveau thet avait une limite de capacité. J'ajoute simplement de nouveaux éléments avec add (). Ça marche toujours.
Tulains Córdova
1
Je pense qu'il parle de la taille de tableau initiale du tableau à l'intérieur de la mise en œuvre ArrayList. Comme son nom l'indique, ArrayList est juste un tableau ancien sous les couvertures, et il crée automatiquement des tableaux plus grands lorsque vous essayez d'ajouter plus d'éléments que sa taille de tableau actuelle ne contient.
dsw88
1
Je pense que StringBuilder est un autre qui a une capacité par défaut, était-ce 10 ou 16?
Ingo
@Ingo Intéressant. Je n'étais même pas au courant des choses en dehors des collections gâchées par la capacité mais je suppose que cela a du sens. À l'époque, il n'y avait pas d'étiquette de capacité, donc cela n'a pas suscité beaucoup d'intérêt pour d'autres utilisations.
Old Badman Gray

Réponses:

17

Réponse courte

Parce que la capacité d'ArrayDeque doit être une puissance de deux, et 16 est la plus petite puissance de deux qui est d'au moins 10.

ArrayDeque doit utiliser un grand nombre d'opérations% partout pour boucler autour d'un tableau linéaire qui prétend être circulaire.

a % bpeut être exprimé comme a & (b - 1) si b est une puissance de deux. L'ET au niveau du bit est massivement plus rapide, la capacité d'ArrayDeque est donc limitée à deux. Toutes les opérations% sont effectuées avec du masquage de bits au lieu du% réel dans l'implémentation.

C'est également la raison pour laquelle le nouveau HashMap n'utilise pas des tailles de table de nombres premiers mais une puissance de deux , encore une fois parce que l'opération% doit être effectuée si souvent et au niveau du bit et est beaucoup plus rapide.

Donc, si la ligne de base est 10, les structures qui ont une puissance de deux limitations devraient utiliser 16, car c'est la plus petite puissance de deux qui est d'au moins 10.

Esailija
la source
3

N'excluez pas la possibilité qu'il n'y ait pas de raison spécifique.

Il se pourrait que ces deux collections aient été écrites par des équipes différentes. Les deux ont choisi un petit nombre comme capacité par défaut, mais la première équipe a pensé décimalement et a choisi 10, tandis que la deuxième équipe a pensé binaire et a choisi 16.

rem
la source
1

@ La réponse d'Esailija est bonne pour ce cas spécifique.

Plus généralement cependant, c'est un compromis qui dépend de nombreux facteurs. Je donnerai quelques exemples:

  • Comment la structure de données est-elle généralement utilisée ? Les structures de données utilisées comme tampons de données préfèrent généralement une capacité beaucoup plus élevée que les structures de données utilisées pour les petits tuples, par exemple.
  • Quelle taille de données par défaut tient dans une ligne de cache sur votre plate-forme CPU cible? Cela peut faire une grande différence dans les performances si la valeur par défaut tient dans la ligne de cache. Le choix de 10 est par défaut en Java peut-être parce qu'un tableau de 10 mots 32 bits plus la surcharge tableau / objet tient dans une ligne de cache de 64 octets.
  • Combien appréciez-vous l' espace par rapport à l'efficacité d'exécution ? Si vous souhaitez de meilleures performances d'exécution, il est généralement préférable de préallouer plus d'espace afin d'éviter des réallocations supplémentaires ultérieurement.

À la suite de ces compromis, il est tout à fait compréhensible que différentes implémentations de collecte puissent avoir une capacité par défaut optimale différente.

mikera
la source