¿Por qué las diferentes colecciones de Java tienen una capacidad predeterminada diferente?

11

Mirando a diferentes constructores de colecciones, me viene a la mente la pregunta. ¿Por qué ArrayList () construye una lista vacía con una capacidad inicial de diez y ArrayDeque () construye una matriz de vacío vacía con una capacidad inicial suficiente para contener 16 elementos?

java collections Viejo badman gris
fuente
No sabía que tenía un límite de capacidad. Simplemente agrego nuevos elementos con add (). Siempre funciona
Tulains Córdova
1
Creo que está hablando del tamaño de matriz inicial de la matriz dentro de la implementación de ArrayList. Como su nombre lo indica, ArrayList es simplemente una matriz antigua debajo de las cubiertas, y crea matrices más grandes automáticamente cuando intenta agregar más elementos de los que contiene su tamaño de matriz actual.
dsw88
1
Creo que StringBuilder es otro que tiene una capacidad predeterminada, ¿era 10 o 16?
Ingo
@Ingo Interesante. Ni siquiera era consciente de que las cosas fuera de las colecciones estropeaban la capacidad, pero supongo que tiene sentido. En ese momento no había una etiqueta de capacidad, así que eso no despertó mucho interés en otros usos.
Old Badman Gray

Respuestas:

17

Respuesta corta

Debido a que la capacidad de ArrayDeque debe ser una potencia de dos, y 16 es la potencia más pequeña de dos que es al menos 10.

ArrayDeque necesita usar muchas operaciones% en todas partes para envolver una matriz lineal que pretende ser circular.

a % bse puede expresar como a & (b - 1) si fuera b una potencia de dos. El AND a nivel de bits es masivamente más rápido, por lo que la capacidad de ArrayDeque se limita a la potencia de dos. Todas las operaciones% se realizan con máscara de bits en lugar de% real en la implementación.

Esta es también la razón por la cual el HashMap más nuevo no usa tamaños de tabla de números primos sino potencia de dos , nuevamente porque el% de operación debe realizarse con tanta frecuencia y a nivel de bits y es mucho más rápido.

Entonces, si la línea de base es 10, entonces las estructuras que tienen una potencia de dos limitaciones deben usar 16 porque es la potencia más pequeña de dos que es al menos 10.

Esailija
fuente
3

No excluya la posibilidad de que no haya una razón específica.

Podría ser que estas dos colecciones hayan sido escritas por diferentes equipos. Ambos eligieron un número pequeño como capacidad predeterminada, pero el primer equipo pensó decimadamente y eligió 10, mientras que el segundo equipo pensó binario y eligió 16.

movimiento rápido del ojo
fuente
1

La respuesta de @ Esailija es buena para este caso específico.

Sin embargo, de manera más general, es una compensación que depende de muchos factores. Daré algunos ejemplos:

  • ¿Cómo se usa típicamente la estructura de datos ? Las estructuras de datos que se usan como memorias intermedias de datos generalmente preferirían una capacidad mucho mayor que las estructuras de datos usadas para tuplas pequeñas, por ejemplo.
  • ¿Qué tamaño de datos predeterminado cabe en una línea de caché en su plataforma de CPU de destino? Puede hacer una gran diferencia en el rendimiento si el valor predeterminado se ajusta en la línea de caché. La elección de 10 es por defecto en Java, bien puede deberse a que una matriz de 10 palabras de 32 bits más la sobrecarga de matriz / objeto cabe en una línea de caché de 64 bytes.
  • ¿Cuánto valoras la eficiencia del espacio frente al tiempo de ejecución ? Si desea un mejor rendimiento en tiempo de ejecución, generalmente es mejor preasignar más espacio para evitar reasignaciones adicionales más adelante.

Como resultado de estas compensaciones, es bastante comprensible que diferentes implementaciones de recolección puedan tener una capacidad predeterminada óptima diferente.

mikera
fuente