.NET Tip #19: Generické kolekce (6/6) - HashSet

Tomáš Jecha       18. 10. 2008       VB.NET, .NET Tips       7234 zobrazení

HashSet je neseřazený seznam unikátních hodnot typu, který předáváme jako generický parametr. Unikátnost se zaručuje indexací pole pomocí tzv. hashe. Lze získat z každého objektu funkci GetHashCode(), která vrací celočíselnou hodnotu. Ta je snadno porovnatelná s hashem osatních objektů stejného typu.

Obecně platí, že GetHashCode() by měl vracet stejnou hodnotu o dvou objektů, které reprezentují stejné hodnoty. To, jak vypočítávat hash je sporné a neexistuje žádný 100% postup. Naštěstí všechny datové typy v .NETu mají již tuto funkci nějakým způsobem navrženou a i u našich objektů si .NET s generováním poradí. Nic nám ale nebrání si tuto funkci napsat sami. Ale to nebudeme probírat.

Používání HashSetu je velmi podobné jako u kolekce List. Zásadní rozdíly jsou 2:

  1. V HashSetu není možné mít více prvků, které mají stejný hash kód získaný funkcí GetHashCode()
  2. Vnitřní uspořádání je odlišné. HashSet je uzpůsoben pro velmi rychlé hledání výskytů (podle hash kódu) a naopak pomalé procházení podle indexu - tedy přesný opak Listu.
  3. HashSet nabízí funkce pro práci s množinou. To právě díky tomu, že dokáže rychle rozpoznávat zda se položka vyskytuje v seznamu.

    Jsou to například funkce:
  • IntersectWith - průnik (odstranit z HashSetu vše, co není v obou seznamech)
  • ExceptWith - odstranit ze seznamu všechny společné prvky (opak průniku)
  • UnionWith - sloučí množiny
  • SymmetricExceptWith - sloučí množiny, ale smaže všechny společné prvky
  • IsSubsetOf - zjistí, zda je HashSet podmnožinou toho předaného v argumentu funkce
  • IsSupersetOf - opak IsSubsetOf - zjistí, zda je HashSet předaný v argumentu podmnožinou

Příklad průniku množin:

Dim hs1 As New HashSet(Of String)(New String() {"a", "b", "c", "d"})
Dim hs2 As New HashSet(Of String)(New String() {"c", "d", "e"})

' vypsat všechny prvky v hs1 - a,b,c,d
Console.WriteLine("Původní hs1:")
For Each s As String In hs1
    Console.WriteLine(s)
Next

' vypsat všechny prvky v hs2 - c,d,e
Console.WriteLine("Původní hs2:")
For Each s As String In hs2
    Console.WriteLine(s)
Next

' do hs1 uděláme průnik z hs2
hs1.IntersectWith(hs2)

' po průniku budou v hs1 jen položky - c,d
Console.WriteLine("Pprůnik hs1 a hs2:")
For Each s As String In hs1
    Console.WriteLine(s)
Next

Na závěr bych chtěl jen upozornit, že hash kód nemusí být unikátní. I když se toho ve většině případů nemusíme bát, může se stát, že pro odlišné hodnoty objektů získáme stejný hash. Přeci jenom velikosti hashe je 32bitů, což je naprosté minimum proti velikosti dat, které se srovnávají v objektech. To si můžeme ověřit například na tomto kusu kódu (oba odlišné řetězce mají stejný hash):

Dim retezec1 As String = "MB7A175000"
Dim retezec2 As String = "MB7F185000"

Console.WriteLine(retezec1.GetHashCode())
Console.WriteLine(retezec2.GetHashCode())

V této sérii jsem psal i o následujících třídách:

  • List
  • Dictionary
  • SortedDictionary a SortedList
  • Queue
  • Stack
  • HashSet
  •  

    hodnocení článku

    0       Hodnotit mohou jen registrované uživatelé.

     

    Nový příspěvek

     

                           
    Nadpis:
    Antispam: Komu se občas házejí perly?
    Příspěvek bude publikován pod identitou   anonym.

    Nyní zakládáte pod článkem nové diskusní vlákno.
    Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

    Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

     

    • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
      Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
    • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

    přihlásit pomocí externího účtu

    přihlásit pomocí jména a hesla

    Uživatel:  
    Heslo:  

    zapomenuté heslo

     

    založit nový uživatelský účet

    zaregistrujte se

     
    zavřít

    Nahlásit spam

    Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

    Nahlásit Zrušit

    Chyba

    zavřít

    feedback