Какие знаешь способы разрешения хеш коллизий

«Какие знаешь способы разрешения хеш коллизий» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 23% Категория: Android Разработчик

Ответ

В Android/Java распространены следующие методы разрешения коллизий:

Метод цепочек (используется в HashMap)
Коллизии хранятся в связном списке или дереве (Java 8+) в одном бакете:

    // Внутри HashMap
    Node<K,V>[] table;

Открытая адресация
При коллизии ищется следующий свободный слот (линейное/квадратичное пробирование).
Двойное хеширование
Используется вторая хеш-функция для поиска слота.
Robin Hood hashing
Оптимизация открытой адресации, где "богатые" записи (с меньшим расстоянием от ideal slot) могут вытеснять "бедные".