Какие знаешь типы коллекций?

Типы коллекций в Java/Kotlin

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

1. List (Список)

Упорядоченная коллекция с индексацией:

// ArrayList — динамический массив, O(1) доступ, O(n) вставка в начало
val list: List<String> = arrayListOf("a", "b", "c")
val mutableList: MutableList<String> = mutableListOf("a", "b")
mutableList.add("c")          // O(1) амортизировано
mutableList[0]                // O(1) доступ

// LinkedList — двусвязный список, O(n) доступ, O(1) вставка в начало
val linked: LinkedList<String> = linkedListOf("a", "b")
linked.addFirst("0")         // O(1)
linked[0]                     // O(n)

// CopyOnWriteArrayList — thread-safe, для частых чтений
val copyOnWrite = CopyOnWriteArrayList<String>()
copyOnWrite.add("item")      // Медленно, копирует массив

Когда использовать:

• ArrayList: частые доступы, редкие вставки в начало
• LinkedList: вставки в начало/конец, редкие доступы по индексу
• CopyOnWriteArrayList: многопоточность, частые чтения

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

Уникальные значения без дубликатов:

// HashSet — hash таблица, O(1) в среднем
val hashSet: HashSet<String> = hashSetOf("a", "b", "c")
hashSet.add("a")             // O(1), не добавится (уже есть)
hashSet.contains("b")        // O(1)

// LinkedHashSet — сохраняет порядок добавления
val linkedHashSet = linkedSetOf("z", "a", "b")
// Порядок: z, a, b (как добавляли)

// TreeSet — отсортированное множество, O(log n)
val treeSet = sortedSetOf<String>()
treeSet.add("banana")
treeSet.add("apple")
// Порядок: apple, banana (отсортировано)

// CopyOnWriteArraySet — thread-safe Set
val copyOnWriteSet = CopyOnWriteArraySet<String>()

Характеристики:

• HashSet быстрее, но нет порядка
• LinkedHashSet медленнее, но сохраняет порядок
• TreeSet медленнее всех, но отсортировано

3. Map (Словарь, ассоциативный массив)

Пары ключ-значение:

// HashMap — hash таблица, O(1) в среднем
val hashMap: HashMap<String, Int> = hashMapOf("a" to 1, "b" to 2)
hashMap["c"] = 3             // O(1)
val value = hashMap["a"]     // O(1), может быть null

// LinkedHashMap — сохраняет порядок вставки
val linkedHashMap = linkedMapOf("z" to 1, "a" to 2)
// Порядок: z, a

// TreeMap — отсортировано по ключам, O(log n)
val treeMap = sortedMapOf<String, Int>()
treeMap["banana"] = 1
treeMap["apple"] = 2
// Порядок ключей: apple, banana

// WeakHashMap — автоматически удаляет элементы, на которые нет ссылок
val weakHashMap = WeakHashMap<String, String>()

// IdentityHashMap — использует == вместо equals()
val identityMap = IdentityHashMap<String, Int>()

4. Queue (Очередь)

Наследует элементы в порядке FIFO (First In First Out):

// LinkedList как Queue
val queue: Queue<String> = LinkedList()
queue.add("first")           // Добавить в конец
queue.offer("second")        // То же самое
val first = queue.poll()     // Получить и удалить из начала, null если пусто
val peek = queue.peek()      // Получить без удаления

// PriorityQueue — по приоритету, O(log n)
val priorityQueue = PriorityQueue<Int>()
priorityQueue.add(5)
priorityQueue.add(1)
priorityQueue.add(3)
while (priorityQueue.isNotEmpty()) {
    println(priorityQueue.poll())  // 1, 3, 5 (отсортировано)
}

// ArrayDeque — двусторонняя очередь
val deque = ArrayDeque<String>()
deque.addFirst("front")
deque.addLast("back")
deque.pollFirst()            // O(1) удалить из начала
deque.pollLast()             // O(1) удалить из конца

5. Deque (Двусторонняя очередь)

Вставка и удаление с обоих концов:

val deque: Deque<String> = ArrayDeque()
deque.addFirst("front")      // Добавить в начало
deque.addLast("back")        // Добавить в конец
deque.removeFirst()          // Удалить из начала
deque.removeLast()           // Удалить из конца

6. Специальные коллекции Kotlin

// Sequence — ленивая (lazy) коллекция
val sequence = sequenceOf(1, 2, 3, 4, 5)
    .filter { it % 2 == 0 }  // Не выполняется сразу
    .map { it * 2 }          // Не выполняется сразу
    .toList()                // Теперь выполнится

// Pair
val pair: Pair<String, Int> = "hello" to 5
val (str, num) = pair

// Triple
val triple = Triple(1, 2, 3)
val (a, b, c) = triple

// groupBy
val groups = listOf(1, 2, 3, 4, 5).groupBy { it % 2 }
// {1=[1,3,5], 0=[2,4]}

7. Thread-safe коллекции

// Collections.synchronizedList() — синхронизированный лист
val syncList = Collections.synchronizedList(mutableListOf<String>())

// ConcurrentHashMap — эффективная многопоточность
val concurrentMap = ConcurrentHashMap<String, Int>()
concurrentMap["key"] = 1    // O(1), thread-safe

// Используй в многопоточном коде!

Сравнение производительности

*Амортизировано в среднем случае

Best Practices

• ArrayList по умолчанию для списков
• HashSet/HashMap когда нужна скорость O(1)
• TreeSet/TreeMap когда нужна сортировка
• LinkedList только если часто вставляешь в начало
• Sequence для больших коллекций с цепочкой операций
• Избегай synchronized коллекций, используй ConcurrentHashMap
• Выбирай начальный размер: ArrayList(expectedSize)