Какая структура данных используется для реализации arraylist

Question

Какая структура данных используется для построения arraylist, поскольку мы можем динамически добавлять/удалять значения.

Я предполагал, что его использование связанного списка, но после выполнения некоторых google, я обнаружил, что его использование вектора .., но не более подробная информация об этом.

Answer 1

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

Доступ к памяти наиболее эффективен при последовательном доступе к ней. Вероятность того, что байт будет доступна в кеше, будет тогда наибольшей, она, скорее всего, будет присутствовать в одной строке кэша. Что делает массивы на сегодняшний день наиболее эффективным объектом коллекции, предполагая, что вы последовательно индексируете элементы массива.

Соответственно, все классы коллекции .NET, за исключением LinkedList, используют массивы для хранения данных. В том числе хешированные коллекции (Hashtable, Dictionary, Hashset), они используют массив массивов. Включая ArrayList. LinkedList следует избегать из-за очень плохого местоположения кеша, за исключением того, что основная проблема - дешевая вставка и удаление в случайно известных местах.

Проблема с массивами заключается в том, что их размер исправлен, что затрудняет реализацию коллекций авторазделения, таких как ArrayList. Это решается путем намеренного использования адресного пространства. Всякий раз, когда массив заполняется до емкости, массив перераспределяет и элементы копируются. Перераспределение вдвое превышает предыдущий размер, вы можете наблюдать это из свойства Capacity. В то время как это звучит дорого, алгоритм амортизируется O (1) и подсистема виртуальной памяти в операционной системе гарантирует, что вы фактически не платите за память, которую вы не используете.

Вы можете избежать не очень дешевого копирования, угадывая мощность в передней части. Подробнее об этом в this answer.

Answer 2

Arraylist внутренне использует массивы для хранения данных и изменения размера массива при необходимости.

Java-реализация Arraylist внутренне создает массив с начальным размером и изменяет размер массива.

Вы можете увидеть реализацию здесь: http://www.docjar.com/html/api/java/util/ArrayList.java.html

Это для Java, но концепции одинаковы для .NET.

Answer 3

От MSDN page:

Реализует IList интерфейс, используя массив, размер которого динамически увеличивать по мере необходимости.

Некоторые из преимуществ использования класса вместо массива напрямую:

• он может быть использован в любом месте в IList
• он обрабатывает изменение размера и копирование для вас при добавлении/удаляя элементы из середины массива
• отслеживает «последний» элемент в массиве
• он предоставляет методы для двоичного поиска f или элементы в массиве

Answer 4

В ArrayList хранит значения внутренне как массив объектов и предоставляет некоторые методы общественных помощников, чтобы сделать работу с массивом проще (экспонируется через интерфейс IList).

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

Поскольку значения хранятся внутри как массив, они обеспечивают преимущества массивов (например, эффективные поисковые запросы, если значения сортируются).

Answer 5

Смотрите здесь: ArrayList source

Как уже упоминалось, это массив внизу.

private object[] _items; 

Вот метод Add():

public virtual int Add(object value) 
{ 
    if (this._size == this._items.Length) 
    { 
     this.EnsureCapacity(this._size + 1); 
    } 
    this._items[this._size] = value; 
    ArrayList expr_2D = this; 
    ArrayList arg_2E_0 = expr_2D; 
    expr_2D._version = arg_2E_0._version + 1; 
    ArrayList expr_3B = this; 
    ArrayList arg_3C_0 = expr_3B; 
    ArrayList arg_45_0 = expr_3B; 
    int expr_41 = arg_3C_0._size; 
    int arg_42_0 = expr_41; 
    int arg_44_0 = expr_41; 
    int i = arg_42_0; 
    arg_45_0._size = arg_44_0 + 1; 
    return i; 
} 

Как вы можете видеть, EnsureCapacity называется ...который заканчивается призывом set_Capacity:

public virtual void set_Capacity(int value) 
{ 
    if (value < this._size) 
    { 
     throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity")); 
    } 
    if (value != this._items.Length) 
    { 
     if (value <= 0) 
     { 
      this._items = new object[4]; 
      goto IL_65; 
     } 
     object[] array = new object[value]; 
     if (this._size > 0) 
     { 
      Array.Copy(this._items, 0, array, 0, this._size); 
     } 
     this._items = array; 
     return; 
    } 
    IL_65: 
} 

Где весь массив копируется на больший массив, если необходимо увеличить емкость.