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

103
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ł.

halivingston
źródło
1
Krok 1: Sprawdź, czy oba robią to samo (w tym przypadku dwie kolekcje służą do różnych celów) Krok 2: Sprawdź dokumentację i sprawdź, czy dobrze czujesz się z ich asymptotyczną złożonością. Krok 3: Jeśli czujesz, że musisz bardziej się martwić, zmierz się, a następnie zadaj pytanie, umieszczając wraz z nim test porównawczy. W twoim przypadku w pierwszym kroku pytanie staje się bezcelowe.
nawfal

Odpowiedzi:

153

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

miał
źródło
9
Świetna analiza! Wygląda na to, że .Contains for Dictionary jest tak szybki, że w przypadku OP nie ma żadnych korzyści z używania HashSet.
EtherDragon
2
tak, miałem to samo pytanie co OP. Mam już słownik, którego używam z innych powodów, i chciałem wiedzieć, czy skorzystam na zmianie na Hashset zamiast używania ContainsKey. Wygląda na to, że odpowiedź brzmi nie, ponieważ obie są tak szybkie.
FistOfFury
4
W przeciwieństwie do tego, co zdają się sugerować poprzednie komentarze, tak, powinieneś przełączyć się na HashSet, ponieważ daje ci to, czego chcesz: przechowywanie zestawu wartości (w przeciwieństwie do utrzymywania pewnego rodzaju mapowania). Ta odpowiedź wskazuje, że nie będzie to negatywnego wpływu na wydajność w porównaniu do Słownika.
Francois Beaussier
Ta odpowiedź NIE mówi ci, jak wydajność porównania HashSet i słownika ... mówi ci tylko, że oba są szybsze niż lista ... cóż ... tak! Oczywiście! HashSet może być 3 razy szybszy i nie wiesz, ponieważ odpowiedni test zwinął oba do „są natychmiastowe ... w porównaniu do listy ”.
Brondahl
71

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ąć.

Jon Skeet
źródło
Tak, miałem na myśli Dictionary <TKey, TValue>. Martwię się tylko szukaniem istnienia elementu w strukturze danych, to wszystko .
halivingston
3
@halivingston W takim przypadku użyj HashSet. To pokazuje, że to wszystko, czego potrzebujesz.
Jon Skeet
2
Ok dzięki. Właściwie mam teraz HashSet <TKey> i kopię Dictionary <Tkey, TValue> również w pamięci. Najpierw .Contains na HashSet, a następnie pobieram wartość w Dictionary <TKey, TValue>. Mam teraz nieskończoną pamięć, ale wkrótce obawiam się, że moja pamięć będzie ograniczona i nasz zespół poprosi mnie o usunięcie tych duplikatów z pamięci, w którym to momencie będę zmuszony użyć Dictionary <TKey, TValue>.
halivingston
4
Wiesz, że słownik również ma funkcję ContainsKey, prawda? Dlaczego duplikujesz dane?
Blindy
8
Jeśli masz już dane w słowniku, to pierwszy komentarz jest ewidentnie niepoprawny - musisz również skojarzyć klucze z wartościami. Może nie dla tego konkretnego fragmentu kodu, ale to nie ma znaczenia. Jeśli masz już z Dictionaryinnych powodów, powinieneś użyć tego.
Jon Skeet
7

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

ripvlan
źródło
4

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ć.

Andrew Bezzub
źródło
0

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");
    }
}
Brondahl
źródło