HashSet <T> versus Dictionary <K, V> wrt czas wyszukiwania w celu znalezienia, czy element istnieje

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


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

Czyja .Containsmetoda zwróci się szybciej?

Dla wyjaśnienia, moim wymaganiem jest to, że mam 10 milionów obiektów (cóż, ciągów znaków), które muszę sprawdzić, czy istnieją w strukturze danych. NIGDY nie będę iterował.

Test wydajności HashSet vs List vs Dictionary, pobrany stąd .

Dodaj 1000000 obiektów (bez sprawdzania duplikatów)

Zawiera czek na połowę obiektów z kolekcji 10000

Usuń połowę obiektów z kolekcji 10000

Zakładam, że masz na myśli Dictionary<TKey, TValue>w drugim przypadku? HashTablenie jest klasą ogólną.

Należy wybrać odpowiednią kolekcję do pracy w oparciu o rzeczywiste wymagania. Czy faktycznie chcesz zamapować każdy klucz na wartość? Jeśli tak, użyj Dictionary<,>. Jeśli zależy Ci tylko na zestawie, użyj HashSet<>.

Spodziewałbym się HashSet<T>.Containsi Dictionary<TKey, TValue>.ContainsKey(które są porównywalnymi operacjami, zakładając, że rozsądnie używasz swojego słownika), zasadniczo wykonają to samo - używają zasadniczo tego samego algorytmu. Wydaje mi się, że przy Dictionary<,>większych wpisach kończy się większe prawdopodobieństwo wysadzenia pamięci podręcznej Dictionary<,>niż z HashSet<>, ale spodziewałbym się, że będzie to nieistotne w porównaniu z bólem związanym z wyborem niewłaściwego typu danych po prostu pod względem tego, czym jesteś próbując osiągnąć.

Z dokumentacji MSDN dla Dictionary <TKey, TValue>

„Pobieranie wartości przy użyciu jej klucza jest bardzo szybkie, zbliżone do O (1) , ponieważ klasa Dictionary jest zaimplementowana jako tabela skrótów ”.

Z dopiskiem:

„Szybkość pobierania zależy od jakości algorytmu mieszającego typu określonego dla TKey”

Wiem, że Twoje pytanie / post jest stare - ale szukając odpowiedzi na podobne pytanie, natknąłem się na to.

Mam nadzieję że to pomoże. Przewiń w dół do sekcji Uwagi, aby uzyskać więcej informacji. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

To są różne struktury danych. Nie ma również ogólnej wersji HashTable.

HashSetzawiera wartości typu T, które HashTable(lub Dictionary) zawierają pary klucz-wartość. Dlatego powinieneś wybrać zbiór, na jakich danych chcesz przechowywać.

Przyjęta odpowiedź na to pytanie NIE daje ważnej odpowiedzi na pytanie! Zdarza się, że daje poprawną odpowiedź, ale nie wynika to z przedstawionych przez nich dowodów.

Ta odpowiedź pokazuje, że wyszukiwanie kluczy na a Dictionarylub HashSetjest znacznie szybsze niż wyszukiwanie w List. Co jest prawdą, ale nie jest interesujące, ani zaskakujące, ani dowodem na to, że mają taką samą prędkość.

Uruchomiłem poniższy kod, aby porównać czasy wyszukiwania i dochodzę do wniosku, że w rzeczywistości SĄ one tą samą prędkością. (Lub przynajmniej, jeśli jest jakaś różnica, to różnica mieści się w granicach odchylenia standardowego tej prędkości)

Konkretnie, 100 000 000 wyszukiwań trwało od 10 do 11,5 sekundy w obu przypadkach w tym teście.

Kod testu:

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");
    }
}