Collections в Java

Заметки по теме Collections в Java 8. Это задумывалось как большая продуманная статья, но обстоятельства заставляют срочно и полностью переключиться на другой проект, так что выкладываю в формате заметок. Пара последних классов остались без русскоязычного описания, вникайте сами.

Структурная схема Collections в Java 8

 

Кроме приведённых интерфейсов все классы также реализуют Cloneable и Serializable. (Своеобразное исключение составляет LinkedHashMap, но он является расширением HashMap, который реализует.). В спойлерах даны отдельные выдержки из TutorialsPoint.com и из описания класса, приведённого в начале его кода, которое соотверствует документации, выложенной на сайте Oracle.

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess
TutorialsPoint.com, docs.oracle.com, Guru99.com

Выдержки из описаний (Eng)

ArrayList - почти как обычный массив, но позволяет дополнительно изменять размер. Внутренняя структура ArrayList представляет из себя обычный массив. Его начальный размер по умолчанию составляет 10 элементов, пользователь может задать свой. Когда этот массив заполнится, то создаётся новый с ёмкостью в полтора раза больше, и старые данные туда перепивываются.

Операции size, isEmpty, get, set, iterator и listIterator происходят за постоянное время, не зависящее от размера массива, O(1). Операция add происходит за амортизированное постоянное время (amortized constant time). Т.е. в большинстве случаев происходит за линейное время, но при некоторых пороговых величинах массива могут быть небольшие задержки, связанные с тем, что Java перестраивает внутренний массив. Подробнее об амортизированном времени можно прочитать на stackoverflow.com и bambielli.com. Все другие операции, грубо говоря, протекают за линейное время, O(n). Быстрее, чем в случае с LinkedList.

 

 

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)

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

 

 

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)


ArrayDeque является более упрощённым воплощением Deque-интерфейса по сравнению с LinkedList. Структура динамически расширяется. Вставка элемента null невозможна. Большинство ArrayDeque-операций происходят в амортизированное постоянное время (amortized constant time), O(1). Исключение составляют  remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove() и bulk-операций, которые имеют линейную зависимость от количества элементов, O(n).

Если необходимо реализовать только queue-операции (такие как вставка новых элементов, удаление существующих, последовательный перебор), а доступ по индексу не важен, то эта структура быстрее LinkedList. На больших очередях элементов разница в скорости может быть трёхкратной. Где возможно, следует предпочитать ArrayDeque.

Главные отличия от ArrayDeque от LinkedList: не поддерживает List-операции (такие как доступ по индексу) и не позволяет использовать null.

 

 

public class HashSet<E> extends AbstractSet<E> implements Set<E>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)

HashSet - набор уникальных данных. Каждое значение может присутствовать только в одном экземпляре. Включая null. В HashSet порядок ввода данных не сохраняется и не имеет значения, взаимное расположение элементов внутри структуры может измениться. Время поиска, вставки и удаления элементов постоянно, O(1). Внутренне использует HashMap, где значение key генерируется hash-функцией и обеспечивает более-менее равномерное распределение элементов.

 

 

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)

LinkedHashSet расширяет HashSet, накладывая поверх него Doubly Linked List. Благодаря этому сохраняется порядок вставки элементов и с ними можно проделывать операции, характерные для Doubly Linked List. Операции поиска, вставки и удаления элементов имеют постоянное время, O(1). Перебор элементов происходит быстрее, чем в HashSet. Добавления элемента со значением, уже имеющимся в наборе, порядок элементов не изменяет - такой элемент игнорируется. Внутренне используется LinkedHashMap.

 

 

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)

TreeSet является набором данных, в которой элементы сразу располагаются в отсортированном порядке. Некоторые конструкторы позволяют пользователю задать Comparator, который определяет правило сортировки элементов. Время поиска, добавления и удаления элементов зависит от величины набора логарифмически, O(log(n)). Внутренне использует TreeMap.

 

 

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>
TutorialsPoint.com, docs.oracle.com, Guru99.com

Выдержки из описаний (Eng)

HashMap каждый элемент имеет сохраняемое значение и уникальный ключ, по которому это значение отыскивается. В том числе разрешается один null-ключ. Порядок ввода данных не сохраняется и не имеет значения, взаимное расположение элементов внутри структуры может измениться.  Время выполнения базовых операций (get, put, remove) постоянно, O(1).

 

 

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)

 

 

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>
TutorialsPoint.com, docs.oracle.com

Выдержки из описаний (Eng)

 

 

Add new comment

Plain text

  • No HTML tags allowed.
  • Lines and paragraphs break automatically.
  • Web page addresses and email addresses turn into links automatically.