dotNETportal.cz

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: