Как устроена хеш-таблица и как разрешаются коллизии?

Хеш-таблица отображает ключи на индексы массива через хеш-функцию, давая в среднем O(1) на поиск и вставку; коллизии — попадание разных ключей в одну ячейку — разрешают цепочками или открытой адресацией.

Цепочки (chaining)

• Каждая ячейка хранит список пар ключ-значение; коллизии просто добавляются в цепочку.
• Плюсы: простая реализация, таблица терпит переполнение, удаление тривиально.
• Минусы: лишняя память на указатели и плохая локальность кеша.

Открытая адресация

• Все элементы лежат в самом массиве; при коллизии пробуются следующие ячейки: линейное или квадратичное пробирование, двойное хеширование.
• Отличная локальность кеша, но резкая деградация при высокой заполненности; удаление требует маркеров-«могил».

Худший случай

При плохой хеш-функции все ключи сваливаются в одну ячейку — O(n). Защита: качественная функция и рандомизация сида против хеш-атак.

Коротко для собеседования

Хеш-таблица превращает ключ в номер корзины, поэтому поиск и вставка в среднем O(1), а коллизии решают цепочками или пробированием соседних ячеек. Скорость держится на качестве хеш-функции и низкой заполненности; в худшем случае всё падает в одну корзину, поэтому Java превращает длинные цепочки в деревья.