Java Collections DeepDive Part2

1.

JAVA · Ч АС Т Ь 2
Collections: глубокое погружение
Деревья, HashMap.get(), Iterator и полная карта сложности поиска
Продолжение конспекта: то, что не поместилось в первую часть

2.

ПЛАН
Пять тем
01
Static-методы с несколькими типами
02
HashSet изнутри: константы и пороги
03
Когда Iterator обязателен — 5 сценариев
04
HashMap.get() — пошаговый разбор
05
Деревья: AVL, Red-Black, B-дерево, Splay
06
Красно-чёрное дерево: балансировка
07
Полная карта сложности поиска
2

3.

GENERICS · УТОЧНЕНИЕ
Static-метод с несколькими типами
<T, U> указывается перед возвращаемым типом — каждый вызов метода может подставлять свою пару типов независимо от других
вызовов.
public class Utility {
public static <T, U> void printPair(T first, U second) {
System.out.println("First: " + first);
System.out.println("Second: " + second);
}
public static void main(String[] args) {
Utility.printPair(42, "Hello");
// T = Integer, U = String
Utility.printPair(3.14, true);
// T = Double, U = Boolean
}
}
Компилятор выводит типы T и U из аргументов каждого конкретного вызова — переиспользовать метод можно для любых комбинаций типов.
3

4.

C O L L E C T I O N S · В Н У Т Р И H A S H S E T/ H A S H M A P
Константы хеш-таблицы
HashSet построен поверх HashMap — они используют один и тот же набор внутренних порогов
16
0.75
8
DEFAULT_INITIAL_CAPACITY
DEFAULT_LOAD_FACTOR
TREEIFY_THRESHOLD
Начальная ёмкость хеш-таблицы по умолчанию
Коэффициент загрузки — порог для resize
Элементов в бакете → список превращается в
дерево
6
64
2^30
UNTREEIFY_THRESHOLD
MIN_TREEIFY_CAPACITY
MAXIMUM_CAPACITY
Элементов в бакете → дерево возвращается в
список
Минимальная ёмкость таблицы для перехода в
дерево
Максимально возможная ёмкость (≈1 млрд бакетов)
4

5.

COLLECTIONS · ОБХОД ЭЛЕМЕНТОВ
Когда Iterator обязателен
1
Удаление во время обхода
2
Коллекции без индексов
for-each при изменении коллекции бросает
ConcurrentModificationException. iterator.remove() — безопасен.
Set и Queue не поддерживают get(i) — перебор возможен только через
Iterator.
3
4
Сложная логика на лету
Нужно одновременно проверять условие, обрабатывать и удалять
элементы в одном проходе.
Полный контроль над обходом
hasNext()/next() дают явное управление позицией — полезно для
нестандартных сценариев.
Не нужен, если вы просто читаете List без изменений — обычный for-each компактнее и делает то же самое под капотом.
5

6.

COLLECTIONS · ВНУТРИ HASHMAP
Как работает get(key)?
1
Хеширование ключа
hashCode() вычисляет хеш, дополнительная функция перемешивает биты для равномерности
2
Индекс бакета
index = (n - 1) & hash — тот же индекс, что использовался при put()
3
Поиск в бакете
Если элемент один — сразу найден. Если несколько — обход списка или дерева
4
Сравнение через equals()
Совпадение хеша не гарантирует равенство — ключи сверяются через equals()
5
Результат
Ключ найден → возвращается значение. Не найден → возвращается null
6

7.

COLLECTIONS · ДЕРЕВЬЯ
Виды сбалансированных деревьев
Дерево
Поиск
Особенность
AVL-дерево
O(log n)
Строгий баланс высот поддеревьев (разница ≤ 1) — самое сбалансированное
Red-Black дерево
O(log n)
Меньше перебалансировок, чем AVL. Основа TreeMap/TreeSet в Java
B-дерево
O(log n)
Много элементов в узле — для баз данных и файловых систем
Splay-дерево
O(log n)*
Часто используемый узел перемещается в корень ('сплей')
* амортизированно — в худшем случае для одной операции гарантии O(log n) нет
Почему Java выбрала Red-Black, а не AVL?
AVL строже сбалансирован → чуть быстрее поиск, но дороже вставка/удаление (больше поворотов). Red-Black — компромисс: поиск почти так же
быстр, а модификация дешевле. Это и используют TreeMap/TreeSet, а также бакеты HashMap при коллизиях.
7

8.

COLLECTIONS · RED-BLACK ДЕРЕВО
Свойства красно-чёрного дерева
Каждый узел — красный или чёрный
Корень дерева всегда чёрный
Все листья (null) считаются чёрными
У красного узла оба потомка — чёрные (два красных подряд не бывает)
От узла до любого листа — одинаковое число чёрных узлов
чёрный
красный
Балансировка
При вставке новый узел всегда красный. Если это нарушает свойства — дерево восстанавливает баланс через повороты (левый/правый) и
перекраску узлов, поднимаясь вверх по дереву до корня.
8

9.

COLLECTIONS · ИТОГ ПО ДЕРЕВЬЯМ И ПОИСКУ
Полная карта сложности поиска
Структура
Поиск по значению
Комментарий
Массив (по индексу)
O(1)
Прямой доступ по адресу в памяти
Массив (по значению)
O(n)
Линейный перебор, если не отсортирован
Отсортированный массив
O(log n)
Бинарный поиск
Связанный список
O(n)
Только последовательный обход
Несбалансированное BST
O(n) в худшем случае
Может выродиться в список
AVL / Red-Black дерево
O(log n)
Гарантированно сбалансированы
Хеш-таблица (HashMap)
O(1) в среднем
O(n) при массовых коллизиях в старых версиях
Очередь с приоритетом (Heap)
O(n)
Быстрый доступ только к min/max — O(1)
9

10.

ИТОГ
Где встречаются красно-чёрные деревья
Java Collections
C++ STL
TreeMap и TreeSet — а также бакеты HashMap при >8 коллизиях
std::map и std::set построены на красно-чёрных деревьях
Базы данных
Кэш и очереди
Индексы в некоторых БД используют похожие балансирующиеся
структуры
Эффективное индексирование и очереди с приоритетом по ключам
Часть 1 (Generics + основы Collections) + Часть 2 (деревья + внутреннее устройство) закрывают все 23 вопроса конспекта.
10