Java: как ArrayList управляет памятью

Question

В моем классе Data Structures мы изучили класс Java ArrayList и то, как он расширяет базовый массив, когда пользователь добавляет больше элементов.Это понятно.Тем не менее, я не могу понять, как именно этот класс освобождает память, когда множество элементов удаляется из списка.Если посмотреть на источник, есть три метода, которые удаляют элементы:

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
}

Ни один из них не уменьшает массив хранилища данных.Я даже начал задаваться вопросом, случается ли когда-нибудь освобождение памяти, но эмпирические тесты показывают, что это происходит.Так что должно быть как-то иначе, но где и как?Я также проверил родительские классы, но безуспешно.

Answer 1

Они не уменьшают базовый массив. Они просто уменьшают размер. Это объясняется тем, что если у вас есть 1000 элементов в массиве и вы удалите 1, зачем перераспределять и копировать массив? Это очень расточительно для очень маленькой выгоды.

В основном Java ArrayList имеет два важных свойства, и важно понимать, что они разные:

• размер: сколько элементов условно в List; и

• емкость: сколько элементов может вписаться в базовый массив.

Когда ArrayList увеличивается, его размер увеличивается примерно на 50%, даже если вы добавляете только один элемент. Это аналогичный принцип в обратном порядке. В основном это сводится к следующему: перераспределение массива и копирование значений (относительно) дорого. Настолько, что вы хотите свести к минимуму это. Пока условный размер составляет около 2 от размера массива, беспокоиться не о чем.

Answer 2

ArrayList не сжимается автоматически, насколько я знаю. Тем не менее, вы можете сказать что-то вроде:

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

Обратите внимание, что объем доступной памяти, вероятно, не изменится, пока GC не запустится снова.

Answer 3

Мне нужно еще раз взглянуть на исходный код ArrayList, но remove удаляет объект из массива, а затем, если на объект не ссылаются никакие другие объекты, GC может удалить этот объект.Но размер массива не уменьшается.

Answer 4

Размер массива никогда не уменьшается автоматически. На самом деле очень редко иметь список, который сначала заполнен большим количеством элементов, а затем очищен, но все еще хранится. И имейте в виду, что должно быть достаточно памяти для хранения списка (который состоит только из ссылок) и его элементов - маловероятно, что память, используемая пустым списком, будет проблемой.

Если вы действительно столкнулись с достаточно странным алгоритмом, что это становится проблемой, вы все равно можете освободить память, вызвав trimToSize() вручную.

Answer 5

Изменение размера внутреннего массива ArrayList не дает большого эффекта, даже если вы используете ArrayList для хранения большого объекта.

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

список будет содержать только ссылку на экземпляр LargeObject, но не будет содержать сам экземпляр LargeObject.

Ссылка не занимает много места. (Думайте как указатель в C)