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

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

Java Collections Framework предоставляет множество реализаций интерфейсов Collection, List, Set, Map и других. Это одна из самых важных частей стандартной библиотеки Java. Рассмотрю основные реализации и их характеристики.

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

Collection
├── List (упорядоченная коллекция с дубликатами)
├── Set (уникальные элементы)
├── Queue (очередь)
└── Deque (двусторонняя очередь)

Map (ключ-значение)

List реализации

1. ArrayList

Реализация на основе динамического массива. Самая часто используемая коллекция.

List<String> list = new ArrayList<>();
list.add("Java");           // O(1)
list.get(0);               // O(1) — быстрый доступ по индексу
list.add(0, "Python");     // O(n) — вставка в начало
list.remove(0);            // O(n) — удаление из начала

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

• Быстрый доступ по индексу — O(1)
• Медленная вставка/удаление в начало — O(n)
• Не потокобезопасная
• Использует массив, который увеличивается при необходимости

2. LinkedList

Реализация на основе двусвязного списка.

List<String> list = new LinkedList<>();
list.add("Java");           // O(1)
list.add(0, "Python");      // O(1) — вставка в начало
list.get(0);               // O(n) — медленный доступ
list.remove(0);            // O(1) — удаление из начала

// LinkedList также реализует Deque
LinkedList<String> deque = new LinkedList<>();
deque.addFirst("first");
deque.addLast("last");
deque.removeFirst();
deque.removeLast();

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

• Медленный доступ по индексу — O(n)
• Быстрая вставка/удаление в начало и конец — O(1)
• Не потокобезопасная
• Много памяти на ссылки между элементами

3. Vector (устаревший)

Древняя реализация ArrayList, потокобезопасная, но медленная.

Vector<String> vector = new Vector<>();  // Синхронизирована
vector.add("Java");
Enumeration<String> e = vector.elements();

Не рекомендуется использовать в новом коде. Используй Collections.synchronizedList(new ArrayList<>()) вместо этого.

Set реализации

1. HashSet

Реализация на основе хеш-таблицы. Самый быстрый Set.

Set<String> set = new HashSet<>();
set.add("Java");           // O(1)
set.contains("Java");      // O(1)
set.remove("Java");        // O(1)

// Порядок элементов не гарантирован
for (String lang : set) {
    System.out.println(lang);  // Может быть любой порядок
}

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

• Быстрые операции — O(1) в среднем
• Порядок элементов не гарантирован
• Не потокобезопасная
• Использует HashMap под капотом

2. LinkedHashSet

Реализация HashSet с сохранением порядка вставки.

Set<String> set = new LinkedHashSet<>();
set.add("Java");
set.add("Python");
set.add("C++");

for (String lang : set) {
    System.out.println(lang);  // Java, Python, C++ (в порядке добавления)
}

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

• Быстрые операции — O(1)
• Сохраняет порядок вставки
• Больше памяти чем HashSet

3. TreeSet

Реализация на основе красно-чёрного дерева. Отсортирована.

Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);

for (Integer num : set) {
    System.out.println(num);  // 1, 2, 3 (в отсортированном порядке)
}

// TreeSet предоставляет методы работы с сортировкой
NavigableSet<Integer> nums = (NavigableSet<Integer>) set;
System.out.println(nums.first());   // 1
System.out.println(nums.last());    // 3
System.out.println(nums.ceiling(2)); // 2
System.out.println(nums.floor(2));  // 2

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

• Всегда отсортирован — O(log n) для операций
• Требует Comparable или Comparator
• Медленнее чем HashSet
• Потокобезопасность можно добавить через Collections.synchronizedSortedSet()

Map реализации

1. HashMap

Реализация на основе хеш-таблицы. Самая часто используемая.

Map<String, Integer> map = new HashMap<>();
map.put("Java", 10);       // O(1)
map.get("Java");           // O(1)
map.remove("Java");        // O(1)

for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}

// Java 8+ способы итерации
map.forEach((key, value) -> System.out.println(key + ": " + value));

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

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

• Быстрые операции — O(1) в среднем
• Порядок не гарантирован
• Не потокобезопасная
• null-ключи и null-значения допускаются

2. LinkedHashMap

HashMap с сохранением порядка вставки.

Map<String, Integer> map = new LinkedHashMap<>();
map.put("Java", 10);
map.put("Python", 8);
map.put("C++", 9);

for (String key : map.keySet()) {
    System.out.println(key);  // Java, Python, C++ (в порядке вставки)
}

// LinkedHashMap можно использовать как LRU кеш
LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 5;  // Максимум 5 элементов
    }
};

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

• Быстрые операции — O(1)
• Сохраняет порядок вставки или доступа (в режиме LRU)
• Больше памяти чем HashMap

3. TreeMap

Редализация на основе красно-чёрного дерева. Отсортирована по ключам.

Map<String, Integer> map = new TreeMap<>();
map.put("Z", 26);
map.put("A", 1);
map.put("M", 13);

for (String key : map.keySet()) {
    System.out.println(key);  // A, M, Z (отсортирован)
}

NavigableMap<String, Integer> navMap = (NavigableMap<String, Integer>) map;
System.out.println(navMap.firstKey());    // A
System.out.println(navMap.lastKey());     // Z
System.out.println(navMap.ceilingKey("M")); // M

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

• Всегда отсортирован — O(log n) для операций
• Требует Comparable или Comparator
• Медленнее чем HashMap

4. Hashtable (устаревший)

Древняя потокобезопасная реализация HashMap. Не используй в новом коде.

Hashtable<String, Integer> table = new Hashtable<>();
table.put("Java", 10);

Вместо этого используй ConcurrentHashMap для потокобезопасности.

Queue реализации

1. LinkedList (как Queue)

Queue<String> queue = new LinkedList<>();
queue.offer("first");       // Добавить в конец
queue.offer("second");
queue.poll();              // Удалить с начала (FIFO)
queue.peek();              // Посмотреть первый элемент

2. PriorityQueue

Очередь с приоритетом на основе кучи (heap).

Queue<Integer> pq = new PriorityQueue<>();  // Min-heap
pq.offer(3);
pq.offer(1);
pq.offer(2);
pq.poll();  // 1 (наименьший)

// Max-heap
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
maxHeap.poll();  // 3 (наибольший)

Потокобезопасные реализации

// Синхронизированные коллекции (блокируют целую коллекцию)
Collection<String> syncCol = Collections.synchronizedCollection(new ArrayList<>());
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// Concurrent коллекции (более тонкая блокировка)
Map<String, Integer> concMap = new ConcurrentHashMap<>();
List<String> concList = new CopyOnWriteArrayList<>();
Set<String> concSet = ConcurrentHashMap.newKeySet();
Queue<String> concQueue = new ConcurrentLinkedQueue<>();

Выбор коллекции

Производительность в таблице

*O(1) амортизированное время для ArrayList.add() в конец

Это основные реализации коллекций в Java. Знание их характеристик и правильный выбор — это ключ к написанию эффективного кода.