Java: Cómo ArrayList gestiona la memoria

Question

En mi clase Data Structures, hemos estudiado la clase Java ArrayList y cómo crece la matriz subyacente cuando un usuario agrega más elementos. Eso se entiende. Sin embargo, no puedo entender cómo exactamente esta clase libera memoria cuando se eliminan muchos elementos de la lista. En cuanto a la fuente, hay tres métodos que eliminan elementos:

public E remove(int index) { 
RangeCheck(index); 

modCount++; 
E oldValue = (E) elementData[index]; 

int numMoved = size - index - 1; 
if (numMoved > 0) 
    System.arraycopy(elementData, index+1, elementData, index, 
     numMoved); 
elementData[--size] = null; // Let gc do its work 

return oldValue; 
} 

public boolean remove(Object o) { 
if (o == null) { 
      for (int index = 0; index < size; index++) 
    if (elementData[index] == null) { 
     fastRemove(index); 
     return true; 
    } 
} else { 
    for (int index = 0; index < size; index++) 
    if (o.equals(elementData[index])) { 
     fastRemove(index); 
     return true; 
    } 
     } 
return false; 
} 


private void fastRemove(int index) { 
     modCount++; 
     int numMoved = size - index - 1; 
     if (numMoved > 0) 
      System.arraycopy(elementData, index+1, elementData, index, 
          numMoved); 
     elementData[--size] = null; // Let gc do its work 
} 

Ninguno de ellos reducir el array almacén de datos. Incluso empecé a preguntarme si la memoria libre nunca ocurre, pero las pruebas empíricas demuestran que sí lo hace. Entonces debe haber alguna otra forma en que se haga, pero ¿dónde y cómo? Revisé las clases para padres también sin éxito.

Answer 1

No reducen la matriz subyacente. Simplemente disminuyen el tamaño. El razonamiento para esto es que si tiene 1000 elementos en una matriz y elimina 1, ¿por qué reasignar y copiar la matriz? Es un enorme desperdicio por muy poca ganancia.

Básicamente Java ArrayList s tienen dos propiedades importantes y es importante entender que son diferentes:

• tamaño: cuántos elementos son teóricamente en el List; y

• capacidad: cuántos elementos puede ajuste de la matriz subyacente.

Cuando un ArrayList expande, crece alrededor de un 50% en el tamaño, incluso si sólo va a añadir un elemento. Este es un principio similar en reversa. Básicamente se trata de esto: la reasignación de la matriz y la copia de los valores es (relativamente) costosa. Tanto es así que quiere minimizar que ocurra. Siempre que el tamaño teórico sea con una fábrica de aproximadamente 2 del tamaño de la matriz, simplemente no vale la pena preocuparse.

Answer 2

Tengo que echarle otro vistazo al código fuente de ArrayList, pero remove elimina el objeto de la matriz, y luego si el objeto no está referenciado por ningún otro objeto, el GC puede eliminar ese objeto. Pero el tamaño de la matriz no se reduce.

Answer 3

No hay mucha ganancia cambiando el tamaño de la matriz interna ArrayList, incluso si está utilizando ArrayList para contener un objeto grande.

List<LargeObject> list = new ArrayList<LargetObject>(); 

lista solo retendrá la referencia a la instancia de LargeObject y no contendrá la propia instancia de LargeObject.

La referencia no consume mucho espacio. (Piénselo como un puntero en C)

Answer 4

El tamaño de la matriz nunca se reduce automáticamente. Es muy raro tener una lista que primero se llena con una gran cantidad de elementos, luego se vacía, pero se mantiene. Y tenga en cuenta que debe haber memoria suficiente para mantener la lista (que consiste únicamente en referencias) y sus elementos; es poco probable que la memoria consumida por la lista vacía sea un problema.

Si realmente encuentra un algoritmo lo suficientemente extraño como para que esto se convierta en un problema, puede liberar la memoria llamando al trimToSize() manualmente.

Answer 5

Una ArrayList no retrocede automáticamente, hasta donde yo sé. Sin embargo, puede decir algo como:

ArrayList al = new ArrayList(); 

// fill the list for demo's sake 
for (int i = 0; i < 1000000; ++i) 
{ 
    al.add(i); 
} 

// now remove all but one element 
al.removeRange(1, al.size()); 

// this should shrink the array back to a decent size 
al.trimToSize(); 

Nota: la cantidad de memoria disponible probablemente no cambiará hasta que el GC vuelva a funcionar.