ArrayList: ¿cómo aumenta el tamaño?

Tengo una pregunta básica sobre Java ArrayList .

Cuando ArrayList se declara e inicializa utilizando el constructor predeterminado, se crea espacio de memoria para 10 elementos. Ahora, cuando agrego un 11º elemento, ¿qué ocurre? ¿Se creará un nuevo espacio de memoria con 20 (o más) elementos de capacidad (esto requiere copiar elementos desde la ubicación de la 1ª memoria a la nueva ubicación) O algo más?

Revisé aquí . Pero no encontré una respuesta.

Por favor comparte el conocimiento. Gracias.

Se crea una nueva matriz y se copia el contenido de la anterior. Eso es todo lo que sabes en el nivel de API. Citando de los documentos (mi énfasis):

Cada instancia de ArrayList tiene una capacidad. La capacidad es el tamaño de la matriz utilizada para almacenar los elementos en la lista. Siempre es al menos tan grande como el tamaño de la lista. A medida que se agregan elementos a ArrayList, su capacidad crece automáticamente. Los detalles de la política de crecimiento no se especifican más allá del hecho de que agregar un elemento tiene un costo de tiempo amortizado constante.

En términos de cómo sucede realmente con una implementación específica de ArrayList (como la de Sun), en su caso puede ver los detalles sangrientos en la fuente. Pero, por supuesto, confiar en los detalles de una implementación específica no suele ser una buena idea …

Dependerá de la implementación, pero del código fuente de Sun Java 6:

 int newCapacity = (oldCapacity * 3)/2 + 1; 

Eso está en el método de ensureCapacity . Otras implementaciones de JDK pueden variar.

JDK6 de Sun:

Creo que crece a 15 elementos. Sin codificarlo, pero mirando el código grow () en el jdk.

int newCapacity then = 10 + (10 >> 1) = 15.

 /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } 

Desde Javadoc, dice que esto es de Java 2 en adelante, por lo que es una apuesta segura en Sun JDK.

EDITAR : para aquellos que no obtuvieron cuál es la conexión entre multiplicar el factor 1.5 e int newCapacity = oldCapacity + (oldCapacity >> 1);

>> es el operador de desplazamiento a la derecha que reduce un número a su mitad. Así,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;

Cuando tratamos de agregar un objeto a la lista de arrays,

Java comprueba que haya suficiente capacidad en la matriz existente para contener el nuevo objeto. De lo contrario, se crea una nueva matriz de mayor tamaño , la matriz anterior se copia a la nueva matriz usando Arrays.copyOf y la nueva matriz se asigna a la matriz existente.

Mire el siguiente código (tomado de Java ArrayList Code en GrepCode.com).

Mira este ejemplo

enter image description here

Editar:

public ArrayList () Construye una lista vacía con una capacidad inicial de diez.

public ArrayList (int initialCapacity) podemos especificar la capacidad inicial.

public ArrayList (Collection c) Construye una lista que contiene los elementos de la colección especificada, en el orden en que son devueltos por el iterador de la colección.

Ahora, cuando usamos ArrayList () constructore, obtenemos ArrayList con Size = 10 Al agregar el undécimo elemento en la lista, se crea un nuevo Arraylist dentro del método ensureCapacity ().

Usando la siguiente fórmula:

  int newCapacity= (oldCapacity * 3)/2 +1; 

cuando una ArrayList se declara e inicializa utilizando el constructor predeterminado, se creará un espacio de memoria para 10 elementos. ahora, cuando agrego el 11 ° elemento, lo que sucede es

ArrayList crea un nuevo objeto con el siguiente tamaño

es decir, OldCapacity * 3/2 + 1 = 10 * 3/2 + 1 = 16

Por lo general, la memoria para los contenedores de tipo ArrayList aumenta al duplicarla. Por lo tanto, si inicialmente tenía espacio para 10 elementos y agregó 10, el undécimo elemento se agregará a una nueva matriz (interna) de 20 elementos. La razón de esto es que el costo incremental de agregar elementos se reduce desde O (n ^ 2) si la matriz se ha incrementado en incrementos de tamaño fijo a un agradable O (n) al duplicar el tamaño cada vez que la matriz interna está llena.

Contexto java 8

Doy mi respuesta aquí en el contexto de la implementación Oracle java 8, ya que después de leer todas las respuestas, encontré que gmgmiller me dio una respuesta en el contexto de java 6, y otra respuesta en el contexto de java 7. Pero cómo java 8 implementa el aumento de tamaño no se ha dado.

En java 8, el comportamiento de aumento de tamaño es el mismo que el de java 6, consulte el método de grow de ArrayList:

  private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } 

el código clave es esta línea:

 int newCapacity = oldCapacity + (oldCapacity >> 1); 

Entonces, claramente, el factor de crecimiento también es 1.5, lo mismo que java 6.

Cuando ArrayList se declara e inicializa utilizando el constructor predeterminado, se crea espacio de memoria para 10 elementos.

NO. Cuando ArrayList se inicializa, la asignación de memoria se realiza para una matriz vacía. La asignación de memoria para la capacidad predeterminada (10) se realiza solo al agregar el primer elemento a ArrayList.

  /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to * DEFAULT_CAPACITY when the first element is added. */ private transient Object[] elementData; 

PD: No tengo suficiente reputación para comentar sobre una pregunta, así que lo estoy poniendo como una respuesta ya que nadie señaló esta suposición incorrecta antes.

Lo que sucede es que se crea una nueva matriz con n * 2 espacios, luego se copian todos los elementos en la matriz anterior y se inserta el nuevo elemento en el primer espacio libre. Con todo, esto da como resultado O (N) agregar tiempo para ArrayList.

Si está utilizando Eclipse, instale Jad y Jadclipse para descomstackr los archivos JAR almacenados en la biblioteca. Hice esto para leer el código fuente original.

El tamaño de ArrayList aumenta siempre con n+n/2+1 .

La capacidad predeterminada de ArrayList es 10. Una vez que la capacidad alcanza su capacidad máxima, el tamaño de ArrayList será 16, una vez que la capacidad scope su capacidad máxima de 16, el tamaño de ArrayList será 25 y seguirá aumentando según el tamaño de datos. …

¿Cómo? Aquí está la respuesta y la fórmula

 New capacity = (Current Capacity * 3/2) + 1 

Entonces, si la capacidad predeterminada es 10, entonces

 Current Capacity = 10 New capacity = (10 * 3/2) + 1 Output is 16 
 static int getCapacity(ArrayList list) throws Exception { Field dataField = ArrayList.class.getDeclaredField("elementData"); dataField.setAccessible(true); return ((Object[]) dataField.get(list)).length; } 

utilice el método anterior para verificar el tamaño cuando se está modificando el arraylist.

En Jdk 1.6: Nueva capacidad = (Capacidad actual * 3/2) + 1;

En Jdk 1.7:

int j = i + (i >> 1); esto es lo mismo que Nueva capacidad = (Capacidad actual * 1/2) + Capacidad actual;

ej .: el tamaño boostá como: 10 -> 15 -> 22 -> 33

ArrayList aumenta el tamaño del factor de carga en los siguientes casos:

  • Capacidad inicial: 10
  • Factor de carga: 1 (es decir, cuando la lista está llena)
  • Tasa de crecimiento: tamaño_actual + tamaño_actual / 2

Contexto: JDK 7

Al agregar un elemento a ArrayList , las siguientes llamadas public ensureCapacityInternal y las otras llamadas a métodos privados suceden internamente para boost el tamaño. Esto es lo que aumenta dinámicamente el tamaño de ArrayList . Mientras veo el código, puedes entender la lógica nombrando convenciones, por esta razón no agrego una descripción explícita

 public boolean add(E paramE) { ensureCapacityInternal(this.size + 1); this.elementData[(this.size++)] = paramE; return true; } private void ensureCapacityInternal(int paramInt) { if (this.elementData == EMPTY_ELEMENTDATA) paramInt = Math.max(10, paramInt); ensureExplicitCapacity(paramInt); } private void ensureExplicitCapacity(int paramInt) { this.modCount += 1; if (paramInt - this.elementData.length <= 0) return; grow(paramInt); } private void grow(int paramInt) { int i = this.elementData.length; int j = i + (i >> 1); if (j - paramInt < 0) j = paramInt; if (j - 2147483639 > 0) j = hugeCapacity(paramInt); this.elementData = Arrays.copyOf(this.elementData, j); } 

Veamos este código (jdk1.8)

 @Test public void testArraySize() throws Exception { List list = new ArrayList<>(); list.add("ds"); list.add("cx"); list.add("cx"); list.add("ww"); list.add("ds"); list.add("cx"); list.add("cx"); list.add("ww"); list.add("ds"); list.add("cx"); list.add("last"); } 

1) Ponga punto de ruptura en la línea cuando se inserta “último”

2) Ir al método add de ArrayList Verás

 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; 

3) Vaya a asegurar el método deCapacityInternal este método llamado ensureExplicitCapacity

4)

 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } return true; 

En nuestro ejemplo minCapacity es igual a 11 11-10 > 0 por lo tanto, necesita grow método de grow

5)

 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } 

Vamos a describir cada paso:

1) oldCapacity = 10 porque no pusimos este parámetro cuando ArrayList era init, por lo tanto, usará la capacidad predeterminada (10)

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Aquí newCapacity es igual a oldCapacity más oldCapacity con right shift en uno ( oldCapacity is 10 esta es la representación binaria 00001010 moviendo un bit a la derecha obtendremos 00000101 que es 5 en decimal por newCapacity tanto newCapacity es 10 + 5 = 15 )

3)

 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 

Por ejemplo, su capacidad de inicio es 1, cuando agrega el segundo elemento a arrayList newCapacity será igual a 1(oldCapacity) + 0 (moved to right by one bit) = 1 En este caso newCapacity es menor que minCapacity y elementData (objeto array inside arrayList) no puede contener un elemento nuevo, por lo tanto, newCapacity es igual a minCapacity

4)

 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); 

Comprueba si el tamaño de la matriz alcanza MAX_ARRAY_SIZE (que es Integer.MAX - 8) ¿Por qué el tamaño máximo de matriz de ArrayList es Integer.MAX_VALUE - 8?

5) Por último, copie los valores antiguos a newArray con longitud 15

El tamaño predeterminado de la lista de arrays es 10. Cuando agregamos la 11ª … la lista de arrays aumenta el tamaño (n * 2). Los valores almacenados en el arraylist antiguo se copian en el nuevo arraylist cuyo tamaño es 20.