Различие между емкостью списка массивов и размером массива

Я прочитал ниже фрагмент в книге Core Java I.

Выделение списка массивов как новый ArrayList < 'Employee > (100)//емкость 100

не совпадает с распределением нового массива как новый сотрудник [100]//размер 100

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

Когда я увидел список массива исходного кода, конструктор создает массив Object заданной емкости, который готов удерживать элементы заданной емкости (ниже - фрагмент кода).

public ArrayList(int initialCapacity) {
     super();
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     this.elementData = new Object[initialCapacity];
 }

Я не могу понять фактическую разницу, о которой автор упомянул в приведенном выше тексте.

Ответ 1

Если вы выделяете новый массив с arr = new Employee[100], размер этого массива (arr.length) будет равным 100. Он имеет 100 элементов. Все элементы изначально нулевые (поскольку это массив ссылок на объекты), но все же существует 100 элементов.

Если вы делаете что-то вроде list = new ArrayList <Employee>(100) и пытаетесь проверить list.size(), вы получите 0. В списке нет элементов.

Внутри, правда, что ArrayList выделяет достаточно места, чтобы поставить 100 элементов, прежде чем потребуется расширить его емкость, но что внутренняя деталь реализации, а список представляет свой контент для вас как "не сохраненных элементов". Только если вы действительно делаете list.add(something), у вас будут элементы в списке.

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

Ответ 2

ArrayList - это всего лишь один из способов представления абстрактного списка, а способность ArrayList представляет собой деталь реализации того, как система реализует логический список.

ArrayList хранит элементы списка, используя фактический массив "под обложками". Фактическая реализация массива в памяти компьютера имеет определенный размер при его распределении; этот размер является пропускной способностью ArrayList. ArrayList эмулирует список переменных размеров, сохраняя логическую длину списка в дополнение к массиву фиксированной длины. Таким образом, если у вас есть ArrayList с емкостью 10, который содержит 4 логических элемента, ArrayList может быть представлен как длина и массив

(4) | e1 | e2 | e3 | e4 | __ | __ | __ | __ | __ | __ |

где (4) - логическая длина списка, а "__" представляют данные, которые игнорируются, потому что они не являются частью логического списка. Если вы попытаетесь получить доступ к 5-му элементу этого массива ArrayList, он выкинет исключение, потому что он знает, что пятый элемент не был инициализирован. Если мы добавим дополнительный элемент e5 в список, ArrayList станет

(5) | e1 | e2 | e3 | e4 | e5 | __ | __ | __ | __ | __ |

Обратите внимание, что емкость не изменилась, а логическая длина - потому, что базовый массив все еще способен обрабатывать все данные в логическом списке.

Если вам удастся добавить в этот список более десяти элементов, ArrayList не сломается. ArrayList - это абстракция, предназначенная для совместимости со всеми операциями массива. Скорее, ArrayList изменяет свою емкость, когда его логическая длина превышает ее первоначальную емкость. Если бы мы добавили элементы (a1, a2,..., a7) в вышеуказанный список, получившийся ArrayList мог бы выглядеть как

(12) | e1 | e2 | e3 | e4 | e5 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | __ | __ | __ | __ | __ | __ | __ | __ |

с емкостью 20.

Как только вы создали ArrayList, вы можете игнорировать возможности во всех последующих программах; логика не затронута. Однако это может повлиять на производительность системы при определенных видах операций. Например, увеличение емкости могло бы включать выделение большего массива, копирование первого массива во второе и последующее выполнение операций. Это может быть довольно медленным по сравнению с, например, та же операция в связанном списке. Таким образом, разумно выбрать емкость массива ArrayList, которая будет больше или, по крайней мере, сопоставима с фактическим количеством элементов, ожидаемых в реальной среде выполнения.

Ответ 3

Если вы создаете новый массив myArray = new Object[100], вы можете читать и писать с myArray[0] до myArray[99] (и вы найдете его полным null).

Если вы создаете ArrayList myList = new ArrayList(100), тогда вы пытаетесь и get или set какие-либо элементы, вы получите IndexOutOfBoundsException, потому что List пуст, пока вы add что-то к нему.

В итоге массив размером 100 изначально будет содержать 100 null s, но List будет пустым.

Ответ 4

Это просто кажется плохо сформулированным и потенциально неправильным, если я не понимаю его правильно.

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

List<Employee> employees = new ArrayList<>(100);
int size = employes.size();

размер будет равен 0, а начальная емкость - 100.

Вы правильно знаете, как вы читаете исходный код.

Ответ 5

Разница между контейнером фиксированного размера (структурой данных) и контейнером с переменным размером.

Массив - это контейнер с фиксированным размером, количество элементов, которое он хранит, устанавливается при создании массива и никогда не изменяется. (Когда массив будет создан, все эти элементы будут иметь какое-то значение по умолчанию, например, null для ссылочных типов или 0 для int, но все они будут в массиве: вы можете индексировать каждый из них.)

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

Но концепция Java List на самом деле является интерфейсом, и ее можно реализовать по-разному. Таким образом, ArrayList, LinkedList и т.д. Существует структура данных "позади" списка, чтобы фактически удерживать элементы. И сама структура данных может быть фиксированным размером или переменным размером и в любой момент времени может иметь точный размер количества элементов в списке или может иметь некоторый пробел extra.

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

Для ArrayList в любой момент времени количество элементов в списке может отличаться от количества элементов, которые может удерживать массив позади него. Эти "лишние" места для элементов просто содержат нули или 0 или что-то еще, но ArrayList никогда не дает вам доступ к этим местам. По мере добавления элементов в ArrayList они занимают больше мест в базовом массиве, пока, наконец, основной массив не будет заполнен. Следующий элемент, добавляемый в ArrayList, заставляет полностью новый массив фиксированного размера - несколько больше, чем выделенный массив, и все элементы списка, скопированные на него (исходный массив отбрасывается). Чтобы предотвратить слишком дорогостоящую операцию (распределение и копирование), новый массив больше, чем текущий массив (с некоторым коэффициентом) и, следовательно, имеет элементы, которые в то время не будут содержать элементы списка - они пусты (null или 0).

Итак, поскольку существует (потенциально) разница между количеством элементов в представленном списке и количеством элементов, которые может содержать структура реализации данных, существуют две концепции.

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

(BTW, для контейнеров фиксированного размера размер часто называют длиной, поэтому массивы имеют длину свойства, а строки имеют метод length(). Различные языки - иногда даже на одном языке - используйте "размер" и "длина" непоследовательно, но они всегда означают размер, а термин "емкость" всегда используется для размера/длины базовой структуры данных.)

Ответ 6

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

В ArrayList емкость имеет что-то общее с уровнем нашей шины, поскольку она определяет количество элементов, которые могут вписаться. В отличие от нашей шины, емкость расширяется, чтобы разместить количество элементов до Integer.MAX_VALUE.

То же самое касается размера, как и наша шина, размер элементов в списке не может превышать емкость. Только представьте, когда 50 пассажиров едут на восемнадцатиместном автобусе! Вы не хотите быть в этой шине.