Иерархия коллекций в Java

На собеседовании это вопрос может звучать по разному:

1) Какие коллекции в Java вы знаете?

2) Какая иерархия коллекций в Java?

3) Какие структуры данных в Java вы знаете?

4) Какие стандартные коллекции в Java вы знаете?

Тут дано уточнить, что их не интересует thread safe коллекции такие как ConcurrentHashMap, CopyOnWriteArrayList и т.д. Их я буду разбирать отдельно.

Ниже я отобразил ключевые интерфейсы и коллекции Java:

Зеленым я отметил ключевые интерфейсы, синим ключевые коллекции.

Рутовым интерфейсом является интерфейс Iterable. Он позволяет использовать коллекции в for-each циклах. У него есть 3 метода: iterator(), и два default метода: splitetator(), forEach(Consumer<? super T> action).

Его расширяет интерфейс Collection. В нем достаточно много методов, таких как add(), remove(), isEmpty(), size() и т.д.

Интерфейс Collection расширяют интерфейсы: List (список), Queue (очередь), Set (множество).

Интерфейс List реализуют следующие коллекции:

1) ArrayList (под капотом это изменяющий размеры массив)

2) LinkedList (двусвязный список)

3) Vector (вектор, все его методы synchronized. Если не нужна потокобезопасность - используйте ArrayList или LinkedList. Более того, из-за того, что он использует лок на всей коллекции - не очень эффективный в многопоточной среде)

4) Stack - стек. Такую же функциональность предоставляют коллекции, которые реализуют интерфейс Deque. Например, LinkedList, ArrayDeque.

Интерфейс Queue(очередь) реализуют:

5) PriorityQueue - приоритетная очередь (под капотом - это приоритетная куча). Можно указать свой компаратор (по default будет использовать natural ordering), чтобы в голове очереди был самый приоритетный элемент.

6) ArrayDeque - реализация Deque на основе массива с изменяемым размером.

Интерфейс Set(множество) реализуют:

7) HashSet - множество. Позволяет выполнять операции add, remove, contains за O(1) при хорошей функции hashcode.

8) LinkedHashSet - множество, но позволяет итерироваться по элементам в порядке добавления.

9) TreeSet - под капотом красно-чёрное дерево. Позволяет выполнять add(), remove(), contains() за log(n). Элементы хранятся упорядоченно в соответствии с компаратором (или natural-ordering если он не указан). При итерировании элементы будут упорядоченными. Есть множество полезных методов: first(), floor(E e) - возвращает наибольший элемент, который меньше или равен заданному, headSet(E e), higher(E e), last(), lower(E e), tailSet(E e), pollFirst(), pollLast() и другие. Документацию можно посмотреть тут: TreeSet.

Продолжение следует. В следующей статье разберу интерфейс Map и классы, которые его реализуют.