HashSet <T> против Dictionary <K, V> по времени поиска, чтобы определить, существует ли элемент

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


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

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

Чтобы прояснить, мое требование: у меня есть 10 миллионов объектов (ну, на самом деле строк), которые мне нужно проверить, существуют ли они в структуре данных. Я НИКОГДА не буду повторять.

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

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

Содержит проверку на половину объектов коллекции из 10000

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

Я так понимаю, вы имеете Dictionary<TKey, TValue>в виду второй случай? HashTableне общий класс.

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

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

Из документации MSDN для Dictionary <TKey, TValue>

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

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

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

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

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

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

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

Принятый ответ на этот вопрос НЕ является правильным ответом на вопрос! Бывает, что даётся правильный ответ, но этот ответ не подтверждается предоставленными доказательствами.

Этот ответ показывает, что поиск ключей в Dictionaryили HashSetнамного быстрее, чем поиск в List. Что верно, но не интересно, не удивительно и не доказывает, что у них одинаковая скорость.

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

В частности, для меня в этом тесте 100000000 поисков занимали от 10 до 11,5 секунд для обоих.

Код теста:

private const int TestReps = 100_000_000;
[Test]
public void CompareHashSetContainsVersusDictionaryContainsKey()
{
    for (int j = 0; j < 10; j++)
    {
        var rand = new Random();
        var dict = new Dictionary<int, int>();
        var hash = new HashSet<int>();

        for (int i = 0; i < TestReps; i++)
        {
            var key = rand.Next();
            var value = rand.Next();
            hash.Add(key);
            dict.TryAdd(key, value);
        }

        var testPoints = Enumerable.Repeat(1, TestReps).Select(_ => rand.Next()).ToArray();
        var timer = new Stopwatch();
        var total = 0;
        
        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (hash.Contains(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);
        
        var target = total;
        Assert.That(total == target);
        

        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (dict.ContainsKey(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);

        Assert.That(total == target * 2);
        Console.WriteLine("Set");
    }
}