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

arrays arraylist

Question

Leí el fragmento a continuación en el libro Core Java I.

Asignación de una lista de matriz como nueva ArrayList <''Empleado> (100) // la capacidad es 100

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

Hay 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, la matriz tiene 100 ranuras, listas 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 elementos en absoluto.

Cuando vi la lista de la matriz de código fuente, el constructor crea una matriz de objetos de capacidad dada que está lista para contener elementos de 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 puedo entender la diferencia real que el autor ha mencionado en el texto anterior.

Answer 1

Esto parece mal redactado y potencialmente incorrecto si no lo entiendo 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<Employee> 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.

Answer 2

La diferencia está 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 , el número de elementos que contiene se establece cuando se crea la matriz y nunca cambia. (Cuando se crea la matriz, todos esos elementos tendrán algún valor predeterminado, por ejemplo, nulo para tipos de referencia o 0 para 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 contiene puede cambiar, desde 0 hasta tantos como desee (sujeto a 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 se puede implementar 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 puede ser de tamaño fijo o de tamaño variable, y en cualquier momento puede tener el tamaño exacto del número de elementos en la lista, o puede tener un espacio extra "buffer".

LinkedList , por ejemplo, siempre tiene en su estructura de datos subyacente exactamente el mismo número de "lugares para elementos" que en la lista que representa. Pero ArrayList usa una matriz de longitud fija como su almacén de respaldo.

Para ArrayList , en cualquier momento dado, la cantidad de elementos en la lista puede ser diferente a la cantidad de elementos que puede contener la matriz detrás de ella. Esos lugares "extra" para elementos solo contienen nulos o 0 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 agregue 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 se copien (la matriz original se descarta). Para evitar que esta operación costosa (asignación y copia) suceda con demasiada frecuencia, la nueva matriz es más grande que la matriz actual (por algún factor) y, por lo tanto, tiene elementos que en ese momento no contendrán elementos de la lista: están vacíos (nulo o 0).

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

El tamaño de la lista es el número 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 los contenedores de tamaño fijo, el tamaño se denomina con frecuencia 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 manera 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).

Answer 3

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 de objetos), pero aún así, hay 100 elementos.

Si hace algo como list = new ArrayList <Employee>(100) e intenta verificar list.size() , obtendrá 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 de implementación interna, y la lista le presenta su contenido como "sin elementos almacenados". Solo si realmente hace list.add(something) , tendrá elementos en la lista.

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

Answer 4

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

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

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

Answer 5

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 utilizando 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 almacenando 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 de 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 es parte de la lista lógica. Si intenta acceder al quinto elemento de esta ArrayList, arrojará una excepción porque sabe que el quinto elemento no se ha inicializado. Si luego agregamos un elemento extra e5 a la lista, ArrayList se convierte en

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

Tenga en cuenta que la capacidad no ha cambiado, mientras que la longitud lógica sí, 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 así

(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 programación que sigue; La lógica no se ve afectada. Sin embargo, el rendimiento del sistema bajo ciertos tipos de operaciones puede verse afectado. El aumento de la capacidad, por ejemplo, podría implicar la asignación de 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 una ArrayList para que sea mayor que, o al menos comparable, al número real de elementos esperados en el entorno de tiempo de ejecución real.

Answer 6

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 un momento dado puede ser inferior a dieciocho pero no superior. Cuando el número de pasajeros es dieciocho, no se puede acomodar a otro pasajero.

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

Lo mismo ocurre con el tamaño, al igual que nuestro bus, 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.