asp.net: сложность времени поиска значения по ключу в словаре с постоянным временем или log2 (n)?

Question

мне нужна структура данных в dotnet, где я могу искать элемент в постоянном времени. Это означает, что структура данных должна реализовывать внутреннюю индексацию. Является ли словарь полезным для этой цели или каким-либо другим?

Answer 1

Да, используйте Dictionary <> (или Hashtable, если вы используете более старую версию .NET). Убедитесь, что объекты, которые вы добавляете в словарь, имеют хорошее значение хеша (посмотрите на переопределение GetHashCode () и Equals () для ваших объектов, которые вы используете в качестве ключей в Словаре). Если ваши объекты данных имеют плохие хэш-коды, производительность начнет ухудшаться. И да, чтобы ответить на ваш вопрос, выглядит взлетов в хэш-таблицу / словарь должен быть относительно постоянной времени (книги, как правило, говорят, что это O (1), но это спорно). Производительность поиска будет зависеть от многих факторов:

1. Хеш-функция (определяет распределение)
2. Как таблица обрабатывает коллизии? Зондирование? Ковши? (большинство реализаций используют сегменты).
3. Можно ли изменять размер таблицы? Как это изменить размер? Небольшие приращения? Мощность 2? Простые числа?
4. и т.д ...