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

Question

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

Answer 1

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

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