Этот вопрос проверяет знание методов разрешения коллизий в хэш-таблицах, которые используются когда разные ключи имеют одинаковый хэш.
Основные механизмы разрешения коллизий: метод цепочек (chaining), где коллизии хранятся в связном списке, и открытая адресация (open addressing), где коллизии разрешаются поиском следующего свободного слота. Также есть двойное хэширование и другие вариации.
Коллизии в хэш-таблицах возникают, когда разные ключи имеют одинаковый хэш. Для их разрешения используются различные методы.
1. Метод цепочек (Chaining):
Каждая ячейка таблицы содержит связный список элементов с одинаковым хэшем.
При коллизии новый элемент добавляется в конец списка.
Преимущества: Простота реализации, таблица никогда не заполняется полностью.
Недостатки: Дополнительная память для указателей, медленный доступ при длинных цепочках.
2. Открытая адресация (Open Addressing):
Все элементы хранятся в самой таблице.
При коллизии ищется следующая свободная ячейка с помощью probing (линейное, квадратичное, двойное хэширование).
Преимущества: Лучшая производительность из-за locality of reference, меньше памяти.
Недостатки: Таблица может заполниться, сложнее удалять элементы.
3. Двойное хэширование (Double Hashing):
Используется в open addressing для вычисления шага probing с помощью второй хэш-функции.
Уменьшает кластеризацию.
Пример в Swift:
Словари (Dictionary) в Swift используют open addressing с линейным probing для эффективности.
