В этой статье анализируется исходный код ArrayList. Позвольте мне поговорить о массивах, прежде чем их анализировать. Массивы могут быть одной из первых структур данных, с которыми мы вступили в контакт. Они делят непрерывное адресное пространство в памяти для хранения элементов. Поскольку он непосредственно управляет памятью, производительность массивов лучше, чем у классов сбора, что является основным преимуществом использования массивов. Но мы знаем, что массив имеет смертельный недостаток, то есть размер массива должен быть указан во время инициализации, а размер массива не может быть изменен в последующих операциях. В реальных ситуациях мы сталкиваемся с большим количеством вещей, которые мы не знаем, сколько элементов хранить в начале, но вместо этого надеемся, что контейнер сможет автоматически расширять свои собственные емкости, чтобы он мог хранить больше элементов. ArrayList может удовлетворить такие потребности очень хорошо, и он может автоматически расширить размер, чтобы адаптироваться к непрерывному увеличению элементов хранения. Его базовый уровень реализован на основе массивов, поэтому он имеет некоторые функции массивов, такие как поиск модификаций, и вставка и удаление являются медленными. В этой статье мы углубимся в исходный код, чтобы увидеть, как он инкапсулирует массивы. Сначала посмотрите на его переменные элемента и три основных конструктора.
// емкость инициализации по умолчанию частное статическое окончательное окончательное значение int default_capacity = 10; // массив пустых объектов Частный статический конечный объект [] empty_elementData = {}; // Массив объектов Частный переходной объект [] elementData; // Количество элементов сбора частного размера; // Сконструктивный метод для прохождения в начальном емкости Public SublicList (int initialCapacity) {super ();); if (initialCapacity <0) {бросить новый allosalargumentException («Незаконная емкость:»+ initialCapacity); } // Создать новую массив типа объекта указанной емкости this.elementData = new Object [initialCapacity];} // Конструктор без параметров public arraylist () {super (); // пройти пустой экземпляр массива в elementData this.elementData = empty_elementData;} // Метод конструктора для перехода во внешнюю коллекцию Public ArrayList (Collection <? Extends e> C) {// Удерживает эталонный элемент внутренней массивы, переданный в Collection ElementData = C.ToArray (); // Обновление количества элементов размера коллекции = elementData.length; // Судить тип массива ссылки и преобразовать ссылку на ссылку на массив объектов if (elementdata.getClass ()! = Object []. Class) {elementData = Arrays.copyof (elementData, size, object []. Class); }}Вы можете видеть, что внутренняя структура хранения ArrayList является массивом типа объекта, поэтому она может хранить элементы любого типа. При построении ArrayList, если начальный размер передается, он создаст новый массив объектов указанной емкости. Если начальный размер не установлен, он не будет распределять пространство памяти, а использовать пустой массив объектов, а затем выделять память, когда элемент фактически должен быть размещен. Давайте посмотрим на его методы добавления, удаления, изменения и поиска.
// увеличение (добавить) public boolean add (e e) {// Проверьте, необходимо ли расширить массив перед добавлением, минимальная длина массива равен размеру + 1 espurecapacity (размер + 1); // Добавить элемент в конце массива elementData [size ++] = e; return true;} // увеличить (вставить) public void add (int index, e element) {// вставить диапазон позиций проверить rangecheckforadd (index); // Проверьте, должна ли емкость быть расширенной EnceRecapacityInternal (размер + 1); // Перемещение элемента за системой положения вставки. Arraycopy (ElementData, Index, ElementData, Index + 1, Size - Index); // назначить новое значение elementData [index] = element; size ++;} // Удалить public e удалить (int index) {// Индекс не может быть больше, чем размер RangeCheck (index); modcount ++; E oldValue = elementData (индекс); int nummoved = size - index - 1; if (Nummoved> 0) {// Перемещение элемента за индекс вперед по одной системе. Arraycopy (elementData, index+1, elementData, index, Nummoved); } // пустое эталонное элементы elementdata [-size] = null; return oldvalue;} // Изменение public e set (int index, e element) {// Индекс не может быть больше, чем размер Rangecheck (Index); E oldValue = elementData (индекс); // заменить новым элементом elementData [index] = element; return oldvalue;} // проверьте public e get (int index) {// Индекс не может быть больше, чем размер RangeCeck (Index); // возвращать указанный элемент позиции return elementData (index);} Каждый раз, когда элемент добавляется в коллекцию, он сначала проверяет, является ли емкость достаточной, в противном случае емкость будет расширена. Подробная информация о расширении пропускной способности будет обсуждаться ниже. Давайте сначала рассмотрим конкретные моменты, на которые можно обратить внимание при добавлении, удалении, изменении и проверке.
Добавить (добавить): просто добавьте этот элемент к концу. Быстрая операция.
Добавить (вставьте): операция медленнее, потому что элемент за позицией вставки должен быть перемещен, а копирование массива задействовано.
Удалить: Поскольку элементы, стоящие за позицией удаления, должны быть перемещены вперед, также будет разработана копия массива, поэтому операция медленная.
Изменение: непосредственно измените элементы в указанном месте, без включения движения элементов или копирования массива, и операция быстро.
Проверьте: непосредственно вернуть элемент массива указанного индекса, и операция быстро.
Из исходного кода видно, что, поскольку поиск и модификация находятся непосредственно для подписания массива, он не включает в себя движение элементов и копирование массива, так что это быстрее. Однако, поскольку элементы необходимо перемещать, они включают копирование массива, поэтому операция медленнее. Кроме того, каждая операция добавления может также выполнять расширение массива, что также повлияет на производительность. Давайте посмотрим на то, как ArrayList динамически расширяет свою емкость.
private void evureCapacityInternal (int mincapacity) {// Если массив все еще пуст в это время, если (elementData == empty_elementData) {// Сравнение с емкостью по умолчанию, возьмите большее значение mincapacity = math.max (default_capacity, mincapacity); } // Если массив был инициализирован, выполните этот шаг убедитесь, что ExplicitCapacity (mincapacity);} private void uareexplicitcapacity (int mincapacity) {modcount ++; // Если минимальная емкость больше длины массива, усилите массив if (mincapacity - elementdata.length> 0) {Grow (mincapacity); }} // максимальная емкость коллекции частная статическая окончательная окончательная финальная int max_array_size = integer.max_value - 8; // Увеличение длины массива Private void Grow (int mincapacity) {// Получить исходную емкость Array int oldCapacity = elementData.length; // емкость нового массива, добавьте половину на исходной основе int newcapacity = oldCapacity + (OldCapacity >> 1); // Проверьте, меньше ли новая емкость, чем минимальная емкость, если (newcapacity - mincapacity <0) {newcapacity = mincapacity; } // Проверьте, превышает ли новая емкость максимальную емкость массива if (newcapacity - max_array_size> 0) {newcapacity = Hugecapacity (mincapacity); } // Скопируйте исходный массив в новый массив elementData = arrays.copyof (elementdata, newcapacity);} Перед добавлением элементов EnceRecapacityEnternal будет вызвана для проверки емкости сбора. Внутри этого метода он проверит, является ли внутренний массив текущей коллекции все еще пустым массивом. Если это так, создайте новый массив объектов с размером по умолчанию 10. Если нет, то это доказывает, что текущая коллекция была инициализирована. Затем вызовите метод explicitcapacity, чтобы проверить, соответствует ли емкость текущего массива минимальной требуемой емкости. Если это не удовлетворено, вызовите метод выращивания для расширения. В методе выращивания вы можете видеть, что каждое расширение состоит в том, чтобы увеличить половину исходной длины массива. Расширение на самом деле для создания нового массива с большей емкостью, скопировать все элементы оригинального массива в новый массив, а затем отбросить оригинальный массив и использовать новый массив. Пока что мы проанализировали более часто используемые методы в ArrayList, и некоторые из ключевых моментов, которые стоит отметить:
1. Основная реализация ArrayList основана на массивах, поэтому поиск и модификация указанных подписок быстрее, но операции удаления и вставки медленнее.
2. При построении ArrayList попробуйте как можно больше указать емкость, чтобы уменьшить операции копирования массива, вызванные расширением. Если вы не знаете размер, вы можете назначить емкость по умолчанию 10.
3. Перед добавлением элементов проверьте, требуется ли расширение емкости. Каждое расширение пропускной способности - половина исходной мощности.
4. Каждый раз, когда выполняется операция индекса, будет выполняться проверка безопасности. Если массив выходит за пределы, исключение будет немедленно брошено.
5. Все методы ArrayList не синхронизированы, поэтому он не безопасен.
6. Приведенный выше анализ основан на JDK1.7, а другие версии будут иметь некоторые различия, поэтому он не может быть обобщен.
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.