Какие знаешь основные реализации коллекций?

Основные реализации коллекций в Java (Android/Kotlin)

В контексте Android-разработки на Kotlin/Java я рассматриваю коллекции через призму их интерфейсов и конкретных реализаций, оптимизированных для различных сценариев использования. Основные семейства: List, Set, Map и Queue (хотя последние реже в мобильной разработке).

1. Реализации List (упорядоченные коллекции)

ArrayList (java.util.ArrayList, kotlin.collections.ArrayList)

Наиболее распространённая реализация для случаев, когда нужен быстрый произвольный доступ по индексу.

val list = arrayListOf("A", "B", "C")
println(list[1]) // Быстрый доступ O(1)

• Основана на динамическом массиве, автоматически расширяющемся при заполнении
• Быстрый доступ по индексу (O(1)), но вставка/удаление в середину требуют сдвига элементов (O(n))
• Идеально для чтения и итерации, когда размер известен или меняется редко

LinkedList (java.util.LinkedList)

Двусвязный список, где каждый элемент хранит ссылки на соседей.

LinkedList<String> list = new LinkedList<>();
list.addFirst("first"); // O(1)
list.removeLast(); // O(1)

• Быстрая вставка/удаление в начало/конец (O(1)), но доступ по индексу медленный (O(n))
• Используется редко в Android, только для специфичных FIFO/LIFO сценариев

CopyOnWriteArrayList (java.util.concurrent.CopyOnWriteArrayList)

Потокобезопасная реализация, где каждая модификация создаёт новую копию массива.

• Дорогая модификация, но безопасное чтение без блокировок
• Применяется в многопоточных сценариях, когда чтение значительно преобладает над записью

2. Реализации Set (уникальные элементы)

HashSet (java.util.HashSet, kotlin.collections.HashSet)

Хранит элементы без гарантии порядка, использует hash-таблицу.

val set = hashSetOf(1, 2, 3, 2) // [1, 2, 3]
println(set.contains(2)) // O(1) в среднем случае

• Константное время для основных операций (O(1) в среднем)
• Требует правильной реализации hashCode() и equals() у элементов

LinkedHashSet (java.util.LinkedHashSet)

HashSet, сохраняющий порядок вставки благодаря доп. связанному списку.

• Немного медленнее HashSet из-за поддержания порядка
• Полезен для LRU-кэшей или когда нужен предсказуемый порядок итерации

TreeSet (java.util.TreeSet)

Хранит элементы отсортированными по естественному порядку или Comparator.

TreeSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(3); sortedSet.add(1); // [1, 3] автоматически сортировано

• Основан на красно-чёрном дереве, операции O(log n)
• Требует сравнимых элементов (Comparable) или Comparator

3. Реализации Map (пары ключ-значение)

HashMap (java.util.HashMap, kotlin.collections.HashMap)

Самая распространённая реализация, основанная на hash-таблице.

val map = hashMapOf("key1" to 1, "key2" to 2)
println(map["key1"]) // O(1) доступ

• Константное время для get/put в среднем случае
• Допускает один null-ключ и множество null-значений
• В Java 8+ при коллизиях использует сбалансированные деревья вместо списков

LinkedHashMap (java.util.LinkedHashMap)

Сохраняет порядок вставки или порядок доступа (режим access-order для LRU).

LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true);

• Часто используется для реализации кэшей с политикой LRU
• Немного медленнее HashMap из-за поддержания порядка

TreeMap (java.util.TreeMap)

Сортирует ключи по естественному порядку или Comparator.

• Основан на красно-чёрном дереве, операции O(log n)
• Полезен для диапазонных запросов (subMap(), headMap())

ConcurrentHashMap (java.util.concurrent.ConcurrentHashMap)

Высокопроизводительная потокобезопасная реализация.

• Сегментированная блокировка (в Java 8+ CAS операции)
• Идеально для многопоточных кэшей в Android

SparseArray (Android SDK)

Специфичная для Android оптимизированная структура для примитивных ключей.

val sparseArray = SparseArray<Int>()
sparseArray.put(10, 100) // Ключ int, значение Integer

• Замена HashMap с Integer ключами — избегает автоупаковки, экономит память
• Лучше для небольших коллекций (обычно до сотен элементов)

ArrayMap (Android SDK)

Оптимизированная реализация Map для Android, хранящая пары в двух массивах.

• Экономит 30-50% памяти по сравнению с HashMap для небольших коллекций
• Используется внутри Bundle, Intent, системных компонентов

4. Ключевые рекомендации для Android-разработки

Выбор коллекции по сценарию:

• Для большинства списков → ArrayList (быстрый доступ по индексу)
• Для уникальных элементов без порядка → HashSet
• Для пар ключ-значение → HashMap (общий случай) или ArrayMap/SparseArray для Android-оптимизации
• Для многопоточности → CopyOnWriteArrayList, ConcurrentHashMap

Важные нюансы:

• Kotlin предоставляет immutable-интерфейсы (List, Set, Map) и factory-функции (listOf(), mutableListOf())
• Все стандартные реализации не синхронизированы (кроме устаревших Vector, Hashtable)
• Итераторы большинства коллекций fail-fast — бросают ConcurrentModificationException при изменении во время итерации
• На Android всегда предпочитайте ArrayMap/SparseArray для случаев с десятками/сотнями элементов, особенно в адаптерах, ViewModel, Bundle

Производительность коллекций существенно влияет на отзывчивость UI и потребление памяти в Android-приложениях, поэтому выбор реализации должен быть осознанным, а не случайным. Современные подходы с Kotlin Flow и реактивными стримами также активно используют эти базовые структуры для временного хранения данных.