Использование метода ArrayList # trimToSize()?

Question

От a recently posted question Я наткнулся на ArrayList#trimToSize(), который уменьшает размер поддерживающей матрицы до текущего размера коллекции.

Цитирование JavaDoc

вырезания емкости этого ArrayList, например, чтобы быть текущий размером списка. Приложение может использовать эту операцию для минимизации хранения экземпляра ArrayList.

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

Но из-за алгоритм, используемого Список_массивами int newCapacity = (oldCapacity * 3)/2 + 1; в 1,6 и int newCapacity = oldCapacity + (oldCapacity >> 1); в 1.7, при добавлении нового элемента, если oldcapacity велико, то это создаст новый массив подкладочного с вышеприведенным алгоритмом и может выделять много ненужного пространства, если только один элемент добавляется после динамического расширения.

Является ли мое обоснование методом правильным или есть некоторые другие приложения к нему?

Answer 1

Да, массив поддержки увеличивается на ~ 50%, когда он заполнен. Например, программа ниже добавляет 1 миллион записей, вызывает trimToSize, затем добавляет одну запись. Длина базы поддержки составляет 1,2 м после добавления записей, 1 м после обрезки и 1,5 м после добавления одного элемента.

Поэтому, если вы не знаете, что больше не будете добавлять в список, звонок trimToSize может быть контрпродуктивным.

ArrayList<Integer> list = new ArrayList<>(); 
Field e = list.getClass().getDeclaredField("elementData"); 
e.setAccessible(true); 
for (int i = 0; i < 1_000_000; i++) { 
    list.add(i); 
} 
System.out.println(((Object[]) e.get(list)).length); //1215487 
list.trimToSize(); 
System.out.println(((Object[]) e.get(list)).length); //1000000 
list.add(0); 
System.out.println(((Object[]) e.get(list)).length); //1500000 

Answer 2

Другая ситуация, когда мы добавляем элементы, а затем удаляем многие из них. Когда мы удаляем элементы, внутренний арай остается неизменным.

Answer 3

Ваша формула приводит к наихудшим издержкам только 50% пустых слотов. Обратите внимание, что минимальный размер Object составляет 24 байта по сравнению с 4 байтами для сжатого ООП в массиве. Накладные составляет всего

(0.5*4)/(24+4) == 1/14 == 7% 

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

Таким образом, единственный раз, когда было бы целесообразно позвонить trimToSize после массивного удаления из ранее огромного массива. Другими словами, почти никогда.