Выбор ответа Senior Коллекции обновлено
Худший случай поиска в dict
Вопрос
Пусть у всех ключей словаря одинаковый __hash__, а __eq__ различает их. Как поведёт себя словарь?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Будет работать корректно, но поиск станет O(n). Одинаковые хеши ведут в одну цепочку проб, и при поиске Python сравнивает ключи через == один за другим.
Варианты ответа
- Будет работать корректно, но поиск станет O(n)правильный ответ
- Словарь будет хранить только последний вставленный ключ
- Вставка бросит
TypeErrorиз-за коллизии - Ничего не изменится: Python кеширует позиции ключей
Разбор
Одинаковые хеши ведут в одну цепочку проб, и при поиске Python сравнивает ключи через == один за другим. Корректность сохраняется, потому что ключи различаются по равенству, но поиск и вставка становятся линейными, а заполнение словаря квадратичным. На этом строились DoS-атаки через коллизии, поэтому хеш строк в Python рандомизирован (PYTHONHASHSEED). Ключи не теряются и ошибок нет.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.