Jak działa HashMap: koszyki, funkcja haszująca, kolizje, LinkedList i drzewo czerwono-czarne w środku?

HashMap в Java реализован как массив бакетов (корзин), каждый из которых хранит элементы с одинаковым хэш-кодом по индексу, вычисленному хэш-функцией.

• Хэш-функция преобразует ключ в целочисленное значение (хэш-код), который затем используется для определения индекса бакета.
• Если несколько ключей попадают в один бакет (коллизия), то элементы в бакете хранятся в виде связного списка (LinkedList).
• При росте количества элементов в бакете и превышении порога длины списка, LinkedList преобразуется в красно-чёрное дерево (TreeNode), что улучшает производительность поиска с O(n) до O(log n).

Пример упрощённой структуры:

class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // для связного списка
}

// При коллизии элементы добавляются в связный список или дерево внутри бакета