Алгоритмы trainee
Как устроена хэш-таблица и как разрешаются коллизии?
Ответ
Массив бакетов. По хэшу ключа определяется индекс. Две стратегии разрешения коллизий: (1) Chaining (цепочки) — в бакете связный список (или дерево). (2) Open addressing (открытая адресация) — элемент ищет следующий свободный слот в самом массиве (линейное/квадратичное пробирование, double hashing).
Разбор: Две классические стратегии — chaining (связный список/дерево в бакете) и open addressing (линейное/квадратичное пробирование, double hashing), где элемент ищет следующий свободный слот в самом массиве. Rehashing — это реакция на рост load factor, а не способ разрешения коллизии; открытая и закрытая адресация — противоположные подходы, а не синонимы.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.