Пользователь
0,0
рейтинг
12 сентября 2011 в 18:19

Разработка → Структуры данных в картинках. ArrayList

JAVA*
Приветствую вас, хабралюди!

Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.



Сегодня поговорим о ArrayList-ах

ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.



Создание объекта


ArrayList<String> list = new ArrayList<String>();

Только что созданный объект list, содержит свойства elementData и size.

Хранилище значений elementData есть ни что иное как массив определенного типа (указанного в generic), в нашем случае String[]. Если вызывается конструктор без параметров, то по умолчанию будет создан массив из 10-ти элементов типа Object (с приведением к типу, разумеется).

elementData = (E[]) new Object[10];



Вы можете использовать конструктор ArrayList(capacity) и указать свою начальную емкость списка.


Добавление элементов


list.add("0");




Внутри метода add(value) происходят следующие вещи:

1) проверяется, достаточно ли места в массиве для вставки нового элемента;

ensureCapacity(size + 1);

2) добавляется элемент в конец (согласно значению size) массива.

elementData[size++] = element;

Весь метод ensureCapacity(minCapacity) рассматривать не будем, остановимся только на паре интересных мест. Если места в массиве не достаточно, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1. Второй момент это копирование элементов. Оно осуществляется с помощью native метода System.arraycopy(), который написан не на Java.


// newCapacity - новое значение емкости
elementData = (E[])new Object[newCapacity];

// oldData - временное хранилище текущего массива с данными
System.arraycopy(oldData, 0, elementData, 0, size);


Ниже продемонстрирован цикл, поочередно добавляющий 15 элементов:
list.add("1");



...

list.add("9");




list.add("10");

При добавлении 11-го элемента, проверка показывает что места в массиве нет. Соответственно создается новый массив и вызывается System.arraycopy().



После этого добавление элементов продолжается



...

list.add("14");





Добавление в «середину» списка


list.add(5, "100");

Добавление элемента на позицию с определенным индексом происходит в три этапа:

1) проверяется, достаточно ли места в массиве для вставки нового элемента;


ensureCapacity(size+1);

2) подготавливается место для нового элемента с помощью System.arraycopy();


System.arraycopy(elementData, index, elementData, index + 1, size - index);



3) перезаписывается значение у элемента с указанным индексом.


elementData[index] = element;
size++;




Как можно догадаться, в случаях, когда происходит вставка элемента по индексу и при этом в вашем массиве нет свободных мест, то вызов System.arraycopy() случится дважды: первый в ensureCapacity(), второй в самом методе add(index, value), что явно скажется на скорости всей операции добавления.

В случаях, когда в исходный список необходимо добавить другую коллекцию, да еще и в «середину», стоит использовать метод addAll(index, Collection). И хотя, данный метод скорее всего вызовет System.arraycopy() три раза, в итоге это будет гораздо быстрее поэлементного добавления.


Удаление элементов


Удалять элементы можно двумя способами:
— по индексу remove(index)
— по значению remove(value)

С удалением элемента по индексу всё достаточно просто

list.remove(5);

Сначала определяется какое количество элементов надо скопировать


int numMoved = size - index - 1;

затем копируем элементы используя System.arraycopy()


System.arraycopy(elementData, index + 1, elementData, index, numMoved);

уменьшаем размер массива и забываем про последний элемент


elementData[--size] = null; // Let gc do its work


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

Дополнение 1: Как верно заметил MikeMirzayanov, при удалении элементов текущая величина capacity не уменьшается, что может привести к своеобразным утечкам памяти. Поэтому не стоит пренебрегать методом trimToSize().


Итоги


— Быстрый доступ к элементам по индексу за время O(1);
— Доступ к элементам по значению за линейное время O(n);
— Медленный, когда вставляются и удаляются элементы из «середины» списка;
— Позволяет хранить любые значения в том числе и null;
— Не синхронизирован.


Ссылки


Исходник ArrayList
Исходник ArrayList из JDK7
Исходники JDK OpenJDK & trade 6 Source Release — Build b23


Пишите в комментариях пожелания/замечания и есть ли смысл продолжать.
@tarzan82
карма
91,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (62)

  • +1
    Спасибо, было приятно убедится, что все происходит именно так, как и должно было :)

    P.S. Местами шаблоны Java накладывают свои ограничения, например нельзя массив типа шаблона создать…
    • 0
      Что вы имеете ввиду, говоря «массив типа шаблона»? Generic?
      • –2
        Я говорю массив типа E создать нельзя, написав new E[len], как собственно и просто объект.
        • +2
          Ну с объектом всё понятно — во время компиляции же неизвестно, какой конструктор необходимо вызвать
          • +1
            Какой конструктор? Если не изменяет память, то при создании списка все элементы инициализируются значением null. А список хранит в себе ссылки на объекты, причем все наследуются от object. Так что хранить в списке можно и пользовательские типы
            • –8
              Когда вы пишите
              MyClass[] arr = new MyClass[10];
              10 раз вызовется стандартный конструктор класса MyClass. Поэтому нельзя создать объект типа E, неясно что вызывать!
              • +7
                Видимо, Вы программируете на чём-то отличном от Java. В Java new MyClass[10] создает только массив, объектов класса MyClass он не создаёт.
              • 0
                Просто речь в статье шла об ArrayList, я позволил себе предположить, что вы в своем комментарии именно его сократили до «массив». В остальном же полностью с вами согласен
              • 0
                Нет, элементы массива в Java при создании не создаются, инициализируются в null. Здесь скорее проблема в том, что тип массива также не может быть определён во время компиляции. В отличие от дженериков, которые чисто языковая фича, типы Object[] и String[] различны
              • +3
                Вы правы, товарищи, к вечеру меня потянуло путать с С++, глубоко извиняюсь за то, что привел в заблуждение!
  • +1
    elementData = (E[]) new Object[10];

    Никакого приведения типа там нет и быть не может, массив так и остаётся Object[].
    • –1
      Там его нет, но быть может
      Например вот такой идиотский класс:
      public class Holder {
      private T[] array;

      public Holder() {
      //noinspection unchecked
      this.array = (T[]) new Object[1];
      }

      public void set(T element) {
      array[0] = element;
      }

      public T get() {
      return array[0];
      }

      public static void main(String[] args) {
      Holder holder = new Holder();
      holder.set("Hi");
      System.out.println(holder.get());
      }
      }

      вполне себе работает и выдает что нужно
      • 0
        Ваш //noinspection unchecked как раз и намекает на то, что в реальности никакого приведения типов не происходит. А если бы оно происходило то как раз бы ничего не работало:
        String[] d = (String[]) new Object[1];
        --> java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
        • –1
          В реальности — не происходит, конечно. Однако жить и работать с получившимся T[] гораздо проще, чем с Object[] — потому не совсем понятно, почему этого не сделали в ArrayList и прочих Collection
          • 0
            Наверное потому, что они появились раньше, чем дженерики, а потом переписывать уже никто не хотел.
            • 0
              Очевидно, что с появлением generic'ов они переписывали этот код. Соответственно, либо приведение каждый раз при создании массива, либо каждый раз при обращении. По-моему первый путь экономнее
              • +1
                Соответственно, либо приведение каждый раз при создании массива, либо каждый раз при обращении. По-моему первый путь экономнее
                Какое ещё приведение? Ни в первом ни во втором случае нет никакого приведения. И вообще никакого приведения не бывает с дженериками. В реальности array останется массивом Object и в том числе в байткоде. Вы как-то превратно понимаете что такое java-дженерики.
                • 0
                  Я все прекрасно понимаю. Есть такая вещь — простота редактирования кода. Я имею ввиду «виртуальное» приведение — то, которое нужно компилятору
                  • +1
                    А, ок. Да, в случае исходников тут всё понятно — вроде как можно и правда переписать Object[] на T[], но резона, видимо, не было) Да и разницы было бы не много — в некоторых геттерах убралось бы «виртуальное приведение» (T[]). С точки зрения внешнего интерфейса и производительности всё останется идентичным.
          • 0
            Наверное потому, что в Sun старались писать хороший код? По-моему, код, в котором без особой на то нужды игнорируются предупреждения компилятора о типобезопасности generic-ов, не слишком хорош.
            • 0
              А return (T)elementData[index]; по вашему его не генерирует? Невозможно на Java написать генерик коллекцию на основе массива без type-safe warning'а к сожалению
              • 0
                Да, сглупил. Но всё же я остаюсь при своём мнении о «хорошести» кода. Альтернативный аргумент: операция (T) elementData[index] осталась бы корректна, если бы вместо T был реальный тип, а операция (T[]) new Object[capacity] возможна только для generic-типов. По-сути, когда мы пишем приводение к T[], мы на самом деле рассчитываем на то что эта операция не сработает, что несколько странно. В чуть-более сложной ситуации типа class MyCollection<T extends Number> это допущение сразу перестаёт работать:

                class A<T extends Number>:
                    (T[]) new Object[1];
                    --> java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Number;

                Кстати, написать коллекцию без warning-ов можно, достаточно передать в конструктор Class<T>. Только это никому не нужно.
  • 0
    Проще говоря, ArrayList ведёт себя как обычный массив. Единственно стоит учитывать, что при переполнении массив удваивается в размере.

    Чуть интереснее с TreeMap/TreeSet (красно-чёрные деревья) и HashMap/HashSet (хэш-таблица в виде массива списков).
    • 0
      поправка: не в два раза, а в полтора: int newCapacity = (oldCapacity * 3)/2 + 1
      • +2
        Дада. Поэтому, если вы заранее знаете сколько будете хранить в контейнере — лучше сразу указать его размер в конструкторе, тем самым избежать копирование (arraycopy), которое как известно хоть и вылизано до последней строчки, но всеравно жутко дорогое.
  • +6
    Вам бы книги писать по программированию «для чайников»
    Очень все красиво и наглядно.
    • +4
      Спасибо, рад что понравилось
  • +4
    Мне кажется надо продолжать. Особенно мне понравились итоги — краткие выводы: стоимость операций. Добавить еще и мотивацию, вроде: «Используй ArrayList везде, где невозможно обойтись массивом», вообще бы цены не было.
    • +1
      Спасибо, постараюсь учесть в будущих статьях
    • +2
      «Используй ArrayList везде, где невозможно обойтись массивом»
      По-моему, это не совсем верно. Поправьте, если ошибаюсь, но часто бывают ситуации, когда предпочтительней к примеру LinkedList.
      И еще, мне кажется, говоря о коллекциях, стоит упомянуть итераторы.
      • 0
        Судя по недавнему обзору Сравнение потребления памяти у разных структур хранения данных LinkedList уж больно прожорлив по памяти
        • –1
          У LinkedList есть преимущество по скорости при наполнении элементами. При этом проход итератором по списку, подозреваю, будет одинаков.

          Не ожидал, что LinkedList так много жрет памяти. Но при относительно больших по размеру объектах разница нивелируется, а учитывая, что ArrayList может выделить под новый элемент в полтора раза больше памяти, тогда он и «пожирней» может оказаться.
          • +3
            У LinkedList есть преимущество по скорости при наполнении элементами.
            В большинстве типичных ситуаций это неверно. Тесты показывают, что LinkedList действительно эффективен становится только когда вам нужны операции вставки в середину/удаления из середины (что вполне ожидаемо). Если же вам это не нужно, то лучше использовать ArrayList. Даже если в конкретной ситауции они будет не лучше LL, то будет отставать совсем незначительно.
    • 0
      Добавить еще и мотивацию, вроде: «Используй ArrayList везде, где невозможно обойтись массивом», вообще бы цены не было.

      Скорее так — «Если не требуется вставка/удаление в середину коллекции — всегда использовать ArrayList. А если вставка/удаление в середину необходимы — нужно профилировать и сравнивать производительность с LinkedList.»
  • +7
    Prefer interfaces to abstract classes [1]:

    List list = new ArrayList();

    Ибо:
    1. Existing classes can be easily retrofitted to implement a new interface.
    2. Interfaces are ideal for defining mixins.
    3. Interfaces allow the construction of nonhierarchical type frameworks.
    4. Interfaces enable safe, powerful functionality enhancements via the wrapper class idiom.

    Это справедливо для любого ООП-языка в-принципе.

    ___________________________________________________________
    1. Effective Java: Programming Language Guide. Joshua Bloch. Publisher: Addison Wesley. First Edition June 01, 2001. ISBN: 0-201-31005-8, 272 pages, Item 16: Prefer interfaces to abstract classes
  • +8
    Вы же просто общедоступный исходник прочли по строкам.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Хороших материалов по расходам памяти пока не встречал. Если что-то накопаю, обязательно укажу в след. статьях.
    • 0
      Было уже про память тут
  • +4
    Наверное, стоит добавить, что при удалении элемента (remove) текущая величина capacity не уменьшается. То есть если натолкать в ArrayList методами add() 100500 чисел, то его capacity после этого будет не меньше 100500 и останется таким даже если для всех элементов сделать remove(). Это может привести к своеобразным утечкам памяти. Иногда может оказаться полезным метод trimToSize() или запись вида «a = new ArrayList<T>()» для освобождения старого буфера для ссылок в «a».

    Еще можно отметить, что если вы создаете ArrayList и знаете, что положите в него не менее n элементов, то немного эффективнее будет создать его как a = new ArraysList<Integer>(n), чтобы буфер не перераспределялся log n раз.
    • +2
      Спасибо, добавил ваше замечание в топик
  • +2
    А как же Navigable*(Set|Map) в иерархии классов на первой картинке?
    • –2
      Разве карты относятся к коллекциям?
    • +2
      NavigableSet — да, упущен. А вот NavigableMap (как и SortedMap и, собственно, Map) — не являются Collection-ами.
      • +1
        Не являются коллекциями — значит их реализации в стандартной библиотеке Java не имплементируют Collection<E>? Ну тогда да, но это странное определение. Конечно же, все Map являются коллекциями. Просто их ветка на этом рисунке располагалась бы рядом. Просто почему-то их проигнорировали :(
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Наследование коллекций в Java, то что я всегда не понимал…
  • 0
    Недостаток ArrayList в том, что он оперирует объектами, и для примитивов его использовать очень неэффективно, хотя в реальной жизни это часто требуется. Вот пара библиотек, которые оперируют коллекциями из примитивов:

    trove.starlight-systems.com/
    pcj.sourceforge.net/
    • 0
      это принципиальный недостаток generic'ов в яве
  • +1
    Если уж приводите ссылку на сорцы, почему бы не ссылаться на свежую версию и в нормальном месте:
    hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/ArrayList.java
    • +1
      Я указал исходник по которому делал описание
      За ссылку спасибо, добавил в топик
  • 0
    >Элементы ArrayList могут быть абсолютно любых типов в том числе и null.
    И Unboxed-типы тоже? int, например?
    • 0
      Чуть выше Throwable написал — ArrayList оперирует объектами.
      Добавлять вы можете любой тип, другой вопрос как он их хранит.
  • 0
    Есть желание сериализировать и десериализировать ArrayList.
    Можно ли его тупо сбрасывать в поток путем
    out.writeObject(massiv);
    и восстанавливать как
    massiv=(ArrayList)in.readObject()?
    • 0
      Можно, если ваши объекты в списке Serializable, т.е. если мы можете сериализовать ваш объект YourObоject, то можете спокойно кидать в out.writeObject(ArrayList), а потом List massiv = (List)in.readObject().

      Другой вопрос в производительности. Я сам не специалист, но есть ощущение что она очень даже хромает. Т.е. у меня большая коллекция таким образом грузится как — то уж очень долго… Думаю переписывать, чтобы вытягивать объекты по очереди и склыдвать уже в новую коллекцию, надеюсь будет быстрее, а будет ли и стоит ли не знаю… Я это, на хлеб этим не зарабатываю если что, тапками не кидайтесь :)
      • 0
        парсер съел скобки с генериками с YourObject
      • 0
        У меня Array небольшой — штук 20 обьектов и картинок. Производительность посмотрю. Cпасибо, подумаю над альтернативой.
  • 0
    Большое спасибо! Пишите ещё! Это как раз тот случай, когда знать хочется и надо и полезно, но не настолько чтобы самому копаться в исходниках, а Ваша статья как раз то что нужно и по объёму и по уровню детализации :)
  • 0
    Великолепная статья. Ваш подход к изложению материала удобен.
    (Зачем нужен, плюсы, минусы и т.д.) Кратко, лаконично.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.