Какие алгоритмы разрешения коллизий вы знаете?

Открытая адресация и метод цепочек.

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

• Линейное зондирование: Поиск свободной ячейки происходит последовательно (H + 1, H + 2, ...).
• Квадратичное зондирование: Поиск свободной ячейки происходит по квадратичной зависимости (H + 1², H + 2², ...).
• Двойное хеширование: Используется вторая хеш-функция для определения шага при поиске (H + H2, H + 2*H2, ...).

Пример линейного зондирования:

c

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

Пример метода цепочек с использованием std::list:

c