Distinción entre la capacidad de una lista de matriz y el tamaño de una matriz

Leí el siguiente fragmento en el libro Core Java I.

Asignación de una lista de arreglos como nueva capacidad de ArrayList (100) // es 100

no es lo mismo que asignar una nueva matriz como nuevo Empleado [100] // el tamaño es 100

Existe una distinción importante entre la capacidad de una lista de matriz y el tamaño de una matriz. Si asigna una matriz con 100 entradas, entonces la matriz tiene 100 ranuras, lista para usar. Una lista de matriz con una capacidad de 100 elementos tiene el potencial de contener 100 elementos (y, de hecho, más de 100, a costa de reasignaciones adicionales); pero al principio, incluso después de su construcción inicial, una lista de matriz no contiene ningún elemento.

Cuando vi la lista de matriz de códigos fuente, el constructor crea una matriz de Objetos de una determinada capacidad que está lista para contener elementos de la capacidad dada (a continuación se muestra el fragmento de código).

public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } 

No soy capaz de descubrir la diferencia real que el autor ha mencionado en el texto anterior.

Si asigna una nueva matriz con arr = new Employee[100] , el tamaño de esa matriz ( arr.length ) será 100. Tiene 100 elementos. Todos los elementos son inicialmente nulos (ya que esta es una matriz de referencias a objetos), pero aún así, hay 100 elementos.

Si haces algo como list = new ArrayList (100) , e intentas marcar list.size() , obtendrás 0. No hay elementos en la lista.

Internamente, es cierto que ArrayList asigna suficiente lugar para colocar 100 elementos antes de que necesite ampliar su capacidad, pero ese es un detalle interno de la implementación, y la lista presenta su contenido como “sin elementos almacenados”. Solo si realmente list.add(something) , tendrá elementos en la lista.

Entonces, aunque la lista asigna almacenamiento por adelantado, la API con la que se comunica con el progtwig le dice que no hay elementos en ella. Los elementos nulos en su matriz interna no están disponibles para usted; no puede recuperarlos ni cambiarlos.

Una ArrayList es solo una forma de representar una lista abstracta, y la capacidad de una ArrayList es un detalle de implementación de cómo el sistema implementa la lista lógica.

Una ArrayList almacena los elementos de una lista mediante el uso de una matriz real “debajo de las cubiertas”. La realización real de la matriz en la memoria de la computadora tiene un cierto tamaño cuando se asigna; este tamaño es la capacidad de ArrayList. ArrayList emula una lista de tamaño variable al almacenar la longitud lógica de la lista, además de la matriz de longitud fija. Por lo tanto, si tiene una ArrayList con una capacidad 10 que contiene 4 elementos lógicos, la ArrayList se puede representar como una longitud y una matriz

(4) | e1 | e2 | e3 | e4 | __ | __ | __ | __ | __ | __ |

donde (4) es la longitud lógica de la lista y ‘__’ representa datos que se ignoran porque no forman parte de la lista lógica. Si intenta acceder al quinto elemento de este ArrayList, emitirá una excepción porque sabe que el quinto elemento no se ha inicializado. Si luego agregamos un elemento adicional e5 a la lista, ArrayList se convierte

(5) | e1 | e2 | e3 | e4 | e5 | __ | __ | __ | __ | __ |

Tenga en cuenta que la capacidad no ha cambiado, mientras que la longitud lógica lo tiene, porque la matriz subyacente todavía puede manejar todos los datos en la lista lógica.

Si logra agregar más de diez elementos a esta lista, ArrayList no se romperá. ArrayList es una abstracción destinada a ser compatible con todas las operaciones de matriz. Por el contrario, ArrayList cambia su capacidad cuando su longitud lógica excede su capacidad original. Si tuviéramos que agregar los elementos (a1, a2, …, a7) a la lista anterior, la ArrayList resultante podría verse como

(12) | e1 | e2 | e3 | e4 | e5 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | __ | __ | __ | __ | __ | __ | __ | __ |

con una capacidad de 20.

Una vez que haya creado una ArrayList, puede ignorar la capacidad en toda la progtwigción que sigue; la lógica no se ve afectada. Sin embargo, el rendimiento del sistema bajo ciertos tipos de operaciones puede verse afectado. Aumentar la capacidad, por ejemplo, bien podría implicar asignar una matriz más grande, copiar la primera matriz en la segunda y luego realizar las operaciones. Esto puede ser bastante lento en comparación con, por ejemplo, la misma operación en una lista vinculada. Por lo tanto, es sensato elegir la capacidad de un ArrayList para ser más grande que, o al menos comparable a, la cantidad real de elementos esperados en el entorno de tiempo de ejecución real.

Si crea una nueva matriz myArray = new Object[100] entonces puede leer y escribir desde myArray[0] a myArray[99] (y la encontrará llena de null ).

Si crea un ArrayList myList = new ArrayList(100) luego intenta get o set cualquier elemento, obtendrá IndexOutOfBoundsException , porque la List está vacía hasta que add algo.

En resumen, la matriz de tamaño 100 inicialmente contendrá 100 null s, pero la List estará vacía.

Esto simplemente parece pobremente redactado y potencialmente incorrecto si no lo estoy entendiendo correctamente.

Creo que lo que está tratando de decir es que hay una diferencia entre la capacidad inicial de ArrayList y el tamaño inicial de ArrayList.

 List employees = new ArrayList<>(100); int size = employes.size(); 

el tamaño será 0 mientras que la capacidad inicial es 100.

Estás en lo correcto con la forma en que estás leyendo el código fuente.

La diferencia es entre un contenedor de tamaño fijo (estructura de datos) y un contenedor de tamaño variable .

Una matriz es un contenedor de tamaño fijo , la cantidad de elementos que contiene se establece cuando la matriz se crea y nunca cambia. (Cuando se crea la matriz, todos esos elementos tendrán algún valor predeterminado, por ejemplo, nulo para los tipos de referencia o 0 para las entradas, pero todos estarán allí en la matriz: puede indexar todos y cada uno).

Una lista es un contenedor de tamaño variable , la cantidad de elementos que puede cambiar varía entre 0 y tantos como desee (sujeto a los límites de implementación). Después de la creación, la cantidad de elementos puede crecer o reducirse. En todo momento puede recuperar cualquier elemento por su índice.

Pero la List conceptos de Java es en realidad una interfaz y puede implementarse de muchas maneras diferentes. Por lo tanto, ArrayList , LinkedList , etc. Hay una estructura de datos “detrás” de la lista para contener los elementos. Y esa estructura de datos en sí misma podría ser de tamaño fijo o tamaño variable, y en cualquier momento dado podría tener el tamaño exacto de la cantidad de elementos en la lista, o podría tener algún espacio “de memoria intermedia” extra .

La LinkedList , por ejemplo, siempre tiene en su estructura de datos subyacente exactamente el mismo número de “lugares para elementos” que están en la lista que representa. Pero ArrayList usa una matriz de longitud fija como su tienda de respaldo.

Para ArrayList , en un momento dado, la cantidad de elementos en la lista puede ser diferente a la cantidad de elementos que la matriz detrás de ella puede contener. Esos lugares “extra” para los elementos solo contienen nulos o ceros o lo que sea, pero ArrayList nunca le da acceso a esos lugares. A medida que agrega elementos a ArrayList ocupan más lugares en la matriz subyacente, hasta que finalmente la matriz subyacente está llena. El siguiente elemento que agrega a ArrayList hace que se asigne una matriz de tamaño fijo completamente nueva, algo más grande que la matriz “actual”, y todos los elementos de la lista copiados (la matriz original se descarta). Para evitar que esta costosa operación (asignación y copia) suceda demasiado a menudo, la nueva matriz es más grande que la matriz actual (por algún factor) y tiene elementos que en ese momento no contendrán elementos de la lista: están vacíos (nulo o 0).

Entonces, debido a que hay (potencialmente) una diferencia entre la cantidad de elementos en la lista que se está representando, y la cantidad de elementos que puede contener la estructura de datos de implementación, existen dos conceptos en vigor.

El tamaño de la lista es la cantidad de elementos que contiene. La capacidad de la lista es la cantidad de elementos que la estructura de datos de respaldo puede contener en este momento . El tamaño cambiará a medida que se agreguen o eliminen elementos de la lista. La capacidad cambiará cuando la implementación de la lista que está utilizando lo necesite. (El tamaño, por supuesto, nunca será mayor que la capacidad).

(Por cierto, para contenedores de tamaño fijo, el tamaño se denomina longitud , por lo que las matrices tienen una longitud de propiedad y las cadenas tienen una longitud de método () . Diferentes idiomas – a veces incluso el mismo idioma – usan “tamaño” y “longitud” de forma inconsistente, pero siempre significa tamaño , y el término “capacidad” siempre se usa para el tamaño / longitud de la estructura de datos subyacente).

Usemos un ejemplo de la vida real. Considere un autobús de dieciocho plazas, la capacidad es de dieciocho pasajeros. El tamaño de los pasajeros en cualquier momento dado puede ser menor a dieciocho pero no más que. Cuando la cantidad de pasajeros es de dieciocho años, no se puede acomodar a otro pasajero.

En una ArrayList, la capacidad tiene algo en común con la de nuestro autobús, ya que define la cantidad de elementos que pueden caber. Sin embargo, a diferencia de nuestro bus, la capacidad se expande para acomodar la cantidad de elementos hasta Integer.MAX_VALUE.

Lo mismo ocurre con el tamaño, al igual que nuestro autobús, el tamaño de los elementos en la lista no puede exceder la capacidad. ¡Imagínese cuando 50 pasajeros viajan en un autobús de dieciocho plazas! Seguro que no quieres estar en ese autobús.