Выбор ответа Junior Коллекции и LINQ спрашивают часто обновлено
Сложность поиска в Dictionary
Вопрос
Какова сложность поиска по ключу в Dictionary<TKey, TValue> и от чего она зависит?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: В среднем O(1), но при плохом GetHashCode с коллизиями деградирует. Dictionary это хеш-таблица с цепочками в массиве бакетов: по хешу находится бакет, затем ключи сравниваются через Equals.
Варианты ответа
- В среднем O(1), но при плохом
GetHashCodeс коллизиями деградируетправильный ответ - Всегда O(log n): внутри сбалансированное красно-чёрное дерево
- O(n): словарь перебирает все пары и сравнивает через
Equals - O(1) всегда: коллизии невозможны благодаря простым числам
Разбор
Dictionary это хеш-таблица с цепочками в массиве бакетов: по хешу находится бакет, затем ключи сравниваются через Equals. В среднем O(1). Если GetHashCode возвращает одинаковые значения для разных ключей, цепочки растут, и поиск стремится к O(n). Дерево внутри у SortedDictionary, там O(log n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.