Какие знаешь реализации интерфейса Collection?

Реализации интерфейса Collection в Java

В Java интерфейс Collection является корневым для большинства коллекций в стандартной библиотеке (Java Collections Framework - JCF). Он определяет базовые операции для работы с группами объектов. Реализации делятся на несколько категорий в зависимости от их поведения и структуры данных. Вот основные из них:

1. Списки (List)

Хранят элементы в определённой последовательности, допускают дубликаты и предоставляют доступ по индексу.

• ArrayList: Динамический массив. Обеспечивает быстрый произвольный доступ (O(1)), но вставка/удаление в середину могут быть медленными (O(n)).

  List<String> list = new ArrayList<>();
  list.add("Элемент");
  String element = list.get(0);
  

• LinkedList: Двусвязный список. Быстрая вставка/удаление в начале/конце (O(1)), но медленный произвольный доступ (O(n)).

  List<Integer> linkedList = new LinkedList<>();
  linkedList.add(1);
  linkedList.removeFirst();
  

• Vector: Устаревший аналог ArrayList с синхронизированными методами (потокобезопасный, но медленный).
• Stack: Наследуется от Vector, реализует структуру "последним пришёл — первым ушёл" (LIFO).

2. Множества (Set)

Хранят уникальные элементы (без дубликатов). Порядок элементов зависит от реализации.

• HashSet: Использует хэш-таблицу. Элементы не упорядочены, операции add, remove, contains в среднем O(1).

  Set<String> hashSet = new HashSet<>();
  hashSet.add("Яблоко");
  hashSet.add("Яблоко"); // Дубликат не добавится
  

• LinkedHashSet: Наследует HashSet, но сохраняет порядок вставки элементов.
• TreeSet: Использует красно-чёрное дерево. Элементы отсортированы (естественный порядок или через Comparator). Операции O(log n).

  Set<Integer> treeSet = new TreeSet<>();
  treeSet.add(5);
  treeSet.add(2); // Автоматически сортируется: [2, 5]
  

3. Очереди (Queue)

Используются для обработки элементов в определённом порядке (например, FIFO).

• LinkedList: Также реализует интерфейс Queue.
• PriorityQueue: Очередь с приоритетом. Элементы упорядочиваются по приоритету (наименьший элемент в голове).

  Queue<Integer> pq = new PriorityQueue<>();
  pq.offer(10);
  pq.offer(5); // Голова очереди: 5
  

• ArrayDeque: Двусторонняя очередь на основе массива. Эффективнее LinkedList для большинства операций.

4. Специализированные и потокобезопасные реализации

• CopyOnWriteArrayList (из java.util.concurrent): Потокобезопасный вариант ArrayList. Все мутирующие операции создают новую копию массива.
• ConcurrentLinkedQueue: Потокобезопасная неблокирующая очередь.
• Collections.synchronizedCollection(): Утилитный метод для обёртки любой коллекции в синхронизированную версию.

Ключевые отличия и выбор реализации

• Скорость доступа: ArrayList для частого доступа по индексу, HashSet для быстрой проверки наличия.
• Упорядоченность: LinkedHashSet для порядка вставки, TreeSet для сортировки.
• Потокобезопасность: Используйте коллекции из java.util.concurrent для многопоточных сценариев.
• Память: LinkedList потребляет больше из-за хранения ссылок, ArrayList более компактен.

Пример выбора на практике

// Частый поиск по значению: HashSet
Set<String> users = new HashSet<>();
users.add("user1");
boolean exists = users.contains("user1"); // Быстро

// Сортированный список уникальных элементов: TreeSet
Set<Product> sortedProducts = new TreeSet<>(Comparator.comparing(Product::getPrice));

// Быстрая вставка в начало: LinkedList или ArrayDeque
Deque<String> history = new ArrayDeque<>();
history.push("Page1");
history.push("Page2");

В Android-разработке особенно важно учитывать производительность и память: ArrayList и HashSet часто предпочтительны из-за их эффективности, но ArrayDeque может быть лучше LinkedList для стеков/очередей. Также стоит помнить о SparseArray и ArrayMap из Android SDK для примитивных ключей, которые не входят в стандартный JCF, но оптимизированы под мобильные устройства.