Java: come ArrayList gestisce la memoria

Question

Nella classe Data Structures abbiamo studiato la classe Java ArrayList e come cresce l'array sottostante quando un utente aggiunge più elementi. Questo è capito. Tuttavia, non riesco a capire come esattamente questa classe libera memoria quando molti elementi vengono rimossi dalla lista. Osservando la fonte, ci sono tre metodi che rimuovono gli elementi:

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 
} 

Nessuno di essi riduce la matrice del datastore. Ho persino iniziato a chiedermi se la memoria si è mai verificata, ma i test empirici dimostrano che è così. Quindi ci deve essere un altro modo in cui viene fatto, ma dove e come? Ho controllato anche le classi genitore senza successo.

Answer 1

Non riducono l'array sottostante. Semplicemente diminuiscono le dimensioni. Il ragionamento per questo è che se si dispone di 1000 elementi in un array e si elimina 1, perché riallocare e copiare l'array? È estremamente dispendioso per un guadagno molto piccolo.

Fondamentalmente Java ArrayList s avere due proprietà importanti ed è importante capire che sono diversi:

• dimensioni: quanti elementi sono fittiziamente nel List; e

• capacità: quanti elementi può forma nella matrice sottostante.

Quando un ArrayList espande, cresce di circa il 50% in termini di dimensioni, anche se si sta solo aggiungendo un elemento. Questo è un principio simile al contrario. Fondamentalmente si tratta di: riallocare l'array e copiare i valori è (relativamente) costoso. Tanto che vuoi minimizzarlo. Finché la dimensione teorica è con una fabbrica di circa 2 della dimensione dell'array, non vale la pena preoccuparsi.

Answer 2

Devo dare un'altra occhiata al codice sorgente di ArrayList, ma remove rimuove l'oggetto dall'array, e quindi se l'oggetto non fa riferimento a nessun altro oggetto, il GC può eliminare quell'oggetto. Ma la dimensione dell'array non è diminuita.

Answer 3

Non c'è molto guadagno ridimensionando l'array interno ArrayList, anche se si utilizza ArrayList per contenere un oggetto di grandi dimensioni.

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

elenco conterrà solo il riferimento all'istanza LargeObject e non mantenendo l'istanza di LargeObject stessa.

Riferimento non consuma molto spazio. (Pensalo come puntatore in C)

Answer 4

La dimensione dell'array non viene mai ridotta automaticamente. È molto raro avere in realtà una lista che viene prima riempita con un gran numero di elementi, quindi svuotarla ma conservarla ancora. E ricorda che deve esserci abbastanza memoria per contenere la lista (che consiste solo di riferimenti) e i suoi elementi - improbabile quindi che la memoria consumata dalla lista vuota sia un problema.

Se si incontra un algoritmo abbastanza bizzarro da rendere questo problema, è comunque possibile liberare la memoria chiamando lo trimToSize() manualmente.

Answer 5

Un ArrayList non si restringe automaticamente, per quanto ne so. Tuttavia, si può dire qualcosa di simile:

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 quantità di memoria disponibile, probabilmente non cambierà fino alla GC viene eseguito di nuovo.