HashSet <T>против словаря <K, V> w.r.t время поиска, чтобы найти, существует ли элемент

Question

HashSet<T> t = new HashSet<T>();
// add 10 million items


Dictionary<K, V> t = new Dictionary<K, V>();
// add 10 million items.

Чей .Contains метод вернется быстрее?

Просто чтобы прояснить, мое требование - у меня есть 10 миллионов объектов (ну, в действительности, строк), которые мне нужно проверить, существуют ли они в структуре данных. Я никогда не буду повторяться.

Answer 1

HashSet vs List vs тест производительности словаря, взятый из здесь .

Добавить 1000000 объектов (без проверки дубликатов)

Содержит чек на половину предметов коллекции 10000

Удалить половину предметов из коллекции 10000

Answer 2

Полагаю, вы имеете в виду Dictionary<TKey, TValue> во втором случае? HashTable это неуниверсальный класс.

Вы должны выбрать правильную коллекцию для работы на основе ваших фактических требований. Вы на самом деле хотите сопоставить каждый ключ со значением? Если это так, используйте Dictionary<,>. Если вы только заботитесь о нем как о наборе, используйте HashSet<>.

Я бы ожидал, что HashSet<T>.Contains и Dictionary<TKey, TValue>.ContainsKey (которые являются сопоставимыми операциями, если вы разумно используете свой словарь) в основном выполняют то же самое - они в основном используют один и тот же алгоритм. Я полагаю, что если записи в Dictionary<,> будут больше, в итоге вы получите большую вероятность взрыва кеша с Dictionary<,>, чем с HashSet<>, но я ожидаю, что это будет незначительно по сравнению с болью выбора неправильных данных введите просто с точки зрения того, что вы пытаетесь достичь.

Answer 3

Из документации MSDN для словаря

"Получение значения с использованием его ключа выполняется очень быстро, близко к O (1) , поскольку класс Dictionary реализован в виде хеш-таблицы. "

С примечанием:

«Скорость поиска зависит от качества алгоритма хеширования типа, указанного для TKey»

Я знаю, что ваш вопрос / пост устарел - но, ища ответ на подобный вопрос, я наткнулся на это.

Надеюсь, это поможет. Прокрутите вниз до раздела Примечания для получения более подробной информации. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

Answer 4

Это разные структуры данных. Также нет общей версии HashTable.

HashSet содержит значения типа T, которые HashTable (или Dictionary) содержат пары ключ-значение. Таким образом, вы должны выбрать сборник о том, какие данные вы должны хранить.