Java: W jaki sposób program ArrayList zarządza pamięcią

Question

W mojej klasie Data Structures badamy klasę Java ArrayList oraz sposób, w jaki rośnie ona w podstawowej tablicy, gdy użytkownik dodaje więcej elementów. To jest zrozumiałe. Nie mogę jednak dowiedzieć się, jak dokładnie ta klasa zwalnia pamięć, gdy wiele elementów zostanie usuniętych z listy. Patrząc na źródło, istnieją trzy metody usuwania elementów:

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 
} 

Żadna z nich nie zmniejsza tablicy Datastore. Zacząłem nawet zastanawiać się, czy kiedykolwiek nastąpi wolna pamięć, ale testy empiryczne pokazują, że tak. Musi więc istnieć jakiś inny sposób, w jaki jest to zrobione, ale gdzie i jak? Sprawdziłem także klasy rodziców, ale bez powodzenia.

Answer 1

Nie zmniejszają podstawowej tablicy. Po prostu zmniejszają rozmiar. Rozumowanie tego jest takie, że jeśli masz 1000 elementów w tablicy i usuń 1, po co przydzielasz i kopiujesz tablicę? To ogromnie marnotrawstwo, z niewielkim zyskiem.

Zasadniczo Java ArrayList s mają dwie ważne właściwości i ważne jest, aby zrozumieć, że są różne:

• rozmiar: jak wiele elementów są hipotetycznie w List; i

• pojemność: ile elementy może zmieścić się w podstawowej tablicy.

Gdy ArrayList rozwija, rośnie o około 50% w wielkości nawet jeśli dodajesz tylko jeden element. Jest to podobna zasada w odwrotnej kolejności. Zasadniczo sprowadza się do tego: ponowne przydzielenie tablicy i skopiowanie wartości jest (relatywnie) drogie. Tak bardzo, że chcesz go zminimalizować. Dopóki nominalny rozmiar jest z fabryką około 2 rozmiaru tablicy, to po prostu nie warto się martwić.

Answer 2

Muszę jeszcze raz spojrzeć na kod źródłowy ArrayList, ale remove usuwa obiekt z tablicy, a następnie, jeśli obiekt nie odwołuje się do żadnych innych obiektów, GC może usunąć ten obiekt. Ale rozmiar tablicy nie jest zmniejszony.

Answer 3

Nie ma zbyt wiele korzyści przez zmianę rozmiaru wewnętrznej tablicy ArrayList, nawet jeśli używasz ArrayList do przechowywania dużego obiektu.

lista będzie zawierać odwołanie do instancji LargeObject i nie będzie zawierała samej instancji LargeObject.

Odniesienie nie zajmuje dużo miejsca. (Myśl jak wskaźnik w C)

Answer 4

Rozmiar tablicy nigdy nie jest automatycznie zmniejszany. Bardzo rzadko zdarza się, aby lista była najpierw wypełniona dużą liczbą elementów, a następnie opróżniona, ale nadal przechowywana. I pamiętaj, że musi być wystarczająco dużo pamięci, aby pomieścić listę (która składa się tylko z referencji) i jej elementów - jest mało prawdopodobne, że pamięć zużywana przez pustą listę byłaby problemem.

Jeśli naprawdę napotkasz na tyle dziwaczny algorytm, że stanie się to problemem, możesz zwolnić pamięć ręcznie, dzwoniąc pod numer trimToSize().

Answer 5

ArrayList nie cofa się automatycznie, o ile wiem. Możesz jednak powiedzieć coś w rodzaju:

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(); 

Uwaga, ilość dostępnej pamięci prawdopodobnie nie zmieni się, dopóki GC nie zostanie ponownie uruchomiony.