Ответ
Основа — массив бакетов (Node<K,V>[] table), где каждый бакет может содержать:
- Ничего (null).
- Один узел (коллизии нет).
- Связный список узлов (решение коллизий методом цепочек).
- Сбалансированное дерево (TreeBin) в Java 8+ при большом количестве коллизий в бакете.
Внутренний узел (упрощенно):
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // Хеш-код ключа
final K key;
V value;
Node<K,V> next; // Ссылка на следующий узел в цепочке
}Эволюция при коллизиях (Java 8+):
- При малом количестве элементов в бакете (
TREEIFY_THRESHOLD = 8) используется связный список. - При превышении порога список преобразуется в красно-черное дерево для обеспечения сложности O(log n) вместо O(n) для операций в этом бакете.
- Обратное преобразование (дерево в список) происходит при уменьшении размера (
UNTREEIFY_THRESHOLD = 6).
Ответ 18+ 🔞
Слушай, давай разберём эту конструкцию, как она там внутри устроена, а то некоторые думают, что там магия какая-то, а на деле — всё просто, как три копейки, только с подвохом.
Представь себе, что у тебя есть большой шкаф с ящиками. Этот шкаф — это массив, который зовётся table. Каждый ящик — это бакет. И вот что может лежать в таком ящике, блядь:
- Вообще нихуя. Пусто, null, вакуум. Идеальная чистота, мечта минималиста.
- Одинокая хуйня. Один-единственный узел валяется. Коллизий нет, всё спокойно, жизнь удалась.
- Связная хуета. Это когда в один ящик накидали кучу узлов, и они связаны друг с другом, как пьяные друзья после корпоратива, — цепочкой. Это и есть классическое решение коллизий.
- Ёбаное дерево (TreeBin). Это уже высший пилотаж, появившийся в Java 8. Когда в одном ящике скопилось столько узлов, что искать среди них — это пиздец как долго, они самоорганизуются в сбалансированное дерево. Не абы какое, а красно-чёрное, чтобы не развалиться.
А вот как выглядит сам узел, эта кирпичик-то:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // Посчитанный хеш ключа. Final, блядь, менять низя.
final K key; // Ключ. Тоже final, приехал — и сиди.
V value; // А вот значение можно и поменять, хитрая жопа.
Node<K,V> next; // А это — ссылка на следующего бедолагу в этой цепочке. Или null, если ты последний лох.
}Теперь про эволюцию, ёпта. В Java 8 разработчики, видимо, с утра кофе хороший выпили и подумали: "А что, если в одном ящике овердохуища узлов? Искать будем до второго пришествия".
И сделали так:
- Пока в бакете мало народу (меньше
TREEIFY_THRESHOLD, а это 8), работает старый добрый связный список. O(n) и хуй с ним, n маленькое. - Но как только набивается 8 (восемь, Карл!) узлов в одну ячейку — вжух! — и список превращается в красно-чёрное дерево. Теперь поиск в этом конкретном забитом бакете будет не O(n), а O(log n). Уже веселее.
- А если из дерева узлы поудалять и их станет мало (меньше
UNTREEIFY_THRESHOLD, а это 6), то оно, дерево, скрипнет и обратно превратится в простой список. Зачем дереву зря память занимать, когда и так справится?
Вот и вся магия, блядь. Никакой хуйни, просто инженерная мысль, чтобы твоя мапа не превращалась в тормозной суп при неудачных хешах.