Приведи примеры стандартных реализаций контейнеров

Основные категории контейнеров в Java/Kotlin для Android

В разработке под Android мы работаем с коллекциями из стандартных библиотек Java (java.util) и Kotlin (kotlin.collections). Все они построены на нескольких фундаментальных интерфейсах: Iterable, Collection, List, Set, Map.

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

Список хранит элементы в определённом порядке, предоставляет доступ по индексу и допускает дубликаты.

ArrayList

Наиболее распространённая реализация на основе динамического массива.

val arrayList: MutableList<String> = ArrayList()
arrayList.add("Camera")
arrayList.add("Microphone")
arrayList[0] = "GPS" // Быстрый доступ по индексу O(1)
println(arrayList) // [GPS, Microphone]

Характеристики: Быстрый произвольный доступ, медленные вставка/удаление в середине (кроме конца).

LinkedList

Реализация на основе двусвязного списка. В Android используется реже из-за накладных расходов на память.

LinkedList<Bitmap> bitmapCache = new LinkedList<>();
bitmapCache.addFirst(bitmap1); // Быстрая вставка в начало O(1)
Bitmap oldest = bitmapCache.pollLast(); // Удаление с конца

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

2. Реализации интерфейса Set (уникальные коллекции)

Множество хранит только уникальные элементы, порядок зависит от реализации.

HashSet

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

val uniqueIds: MutableSet<Long> = HashSet()
uniqueIds.add(1001L)
uniqueIds.add(1002L)
uniqueIds.add(1001L) // Игнорируется
println(uniqueIds.size) // 2

Характеристики: Константное время операций O(1) в среднем случае, требует корректной реализации hashCode().

LinkedHashSet

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

val orderedSet = LinkedHashSet<String>()
orderedSet.add("Первый")
orderedSet.add("Второй")
orderedSet.add("Первый")
println(orderedSet) // [Первый, Второй] - порядок сохранён

Характеристики: Немного медленнее HashSet, но предсказуемый порядок итерации.

TreeSet

Хранит элементы отсортированными (по natural order или Comparator).

TreeSet<Integer> sortedScores = new TreeSet<>();
sortedScores.add(1500);
sortedScores.add(1200);
sortedScores.add(1800);
Integer bestScore = sortedScores.last(); // 1800 - максимальный

Характеристики: Элементы отсортированы, операции O(log n), реализует интерфейс NavigableSet.

3. Реализации интерфейса Map (словари "ключ-значение")

HashMap

Классическая хэш-таблица, не гарантирует порядок.

val userMap: MutableMap<String, User> = HashMap()
userMap["user1"] = User("Ivan")
userMap.put("user2", User("Maria"))
val user = userMap["user1"] // Быстрое получение по ключу

Характеристики: Константное время операций, требует immutable ключи в Android во избежание утечек.

LinkedHashMap

Сохраняет порядок вставки пар "ключ-значение". Часто используется для LRU-кэшей.

val lruCache = object : LinkedHashMap<String, Bitmap>(10, 0.75f, true) {
    override fun removeEldestEntry(eldest: Map.Entry<String, Bitmap>): Boolean {
        return size > MAX_CACHE_SIZE
    }
}

Характеристики: Полезен для кэширования, доступ к элементу обновляет его позицию (access-order).

TreeMap

Хранит ключи отсортированными, на основе красно-черного дерева.

TreeMap<String, String> localeData = new TreeMap<>();
localeData.put("en_US", "Hello");
localeData.put("ru_RU", "Привет");
String firstKey = localeData.firstKey(); // "en_US" - сортировка по ключам

Характеристики: Ключи отсортированы, операции O(log n).

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

SparseArray и его вариации

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

val sparseArray = SparseArray<String>()
sparseArray.put(100, "Value for key 100")
sparseArray.append(101, "Next value")
val value = sparseArray.get(100) // Работает с int ключами

// SparseIntArray, SparseLongArray, SparseBooleanArray
val sparseIntArray = SparseIntArray()
sparseIntArray.put(R.id.view_id, 255)

ArrayMap

Оптимизированная замена HashMap для небольших коллекций (до сотен элементов).

val arrayMap = ArrayMap<String, Any>()
arrayMap.put("config_key", "value")
arrayMap.put("version", 2)

Характеристики: Меньше потребление памяти, чем у HashMap, за счёт хранения хэшей и пар в отдельных массивах.

5. Неизменяемые (immutable) коллекции Kotlin

Kotlin предоставляет удобные фабричные функции для создания read-only коллекций:

val immutableList = listOf("item1", "item2", "item3")
val immutableSet = setOf(1, 2, 3, 2) // [1, 2, 3]
val immutableMap = mapOf("key1" to "value1", "key2" to "value2")

// Mutable версии
val mutableList = mutableListOf<String>()
val mutableMap = mutableMapOf<String, Int>()

Критерии выбора реализации:

1. Требуется ли порядок? Нет → HashSet/HashMap, да вставке → LinkedHashSet/LinkedHashMap, отсортированный → TreeSet/TreeMap
2. Частый доступ по индексу? → ArrayList
3. Частые вставки/удаления в середине? → LinkedList (но измерьте производительность!)
4. Маленькая коллекция (< 100)? → ArrayMap, SparseArray
5. Ключи-примитивы? → SparseArray семейство
6. Коллекция для UI (RecyclerView.Adapter)? → ArrayList
7. Неизменяемые данные? → listOf(), mapOf() из Kotlin

Правильный выбор контейнера напрямую влияет на производительность Android-приложения, особенно при работе с большими наборами данных или в критичных по времени операциях (например, во время рендеринга кадра за 16 мс). Всегда тестируйте предполагаемый сценарий использования под нагрузкой!