Programování – Hashové tabulky v C#
- Hashtable je typ kolekce, nachází se ve jmenném prostoru System.Collections
- ukládá obecně jakékoliv objekty (typ object) pod určitým klíčem (také object) = jedná se de facto o slovník
- není možné vložit dvakrát stejný klíč, není možné objekty třídit a nepamatuje si pořadí vkládaných objektů
- objekt je ukládaný do nějakého vnitřního pole, přičemž index je určený pomocí metody GetHashCode() z našeho klíče (objekt klíče musí tedy tuto metodu implementovat – standardně implementováno u všech typů poděděných od object)
- poměr zaplněné části tabulky k její kapacitě se nazývá faktor zaplnění, můžeme ho nastavit a určuje nám kolik položek může být skutečně zaplněno
- čím menší faktor zaplnění, tím lépe bude hashová tabulka fungovat, ale tím více bude zabírat paměti
- můžeme v konstruktoru určit základní kapacitu pro jakou si má Hashtable alokovat paměť; výchozí hodnota je 16
- když se kapacita vyčerpá (v závislosti na faktoru zaplnění), automaticky si Hashtable realokuje paměť; nová kapacita je rovna nejbližšímu prvočíslu, které je větší než dvojnásobek aktuální kapacity
- slovníky jsou nejefektivnější, když je jejich kapacita definovaná prvočíslem
- hledání pomocí klíče v Hashtable je velice rychlé
- implementováno přes indexer
- přidávání a odebírání objektů je šetrné, není nutné vždycky přesouvat položky v paměti(oproti poli)
- metoda Add() pro přidávání, Remove() pro odebírání
- metody ContainsKey() a ContainsValue()
- pokud jako klíče používáme řetězce, je doporučeno místo Hashtable použít StringDictionary (System.Collections.Specialized)
- vlastní slovník si můžeme vytvořit poděděním od abstraktní třídy DictionaryBase
1: using System;
2: using System.Collections.Generic;
3: using System.Text;
4: using System.Collections;
5:
6: namespace TeorieHashtable
7: {
8: class Klic
9: {
10: string retezec;
11:
12: public string Retezec
13: { get { return retezec; } set { retezec = value; } }
14:
15: public Klic(string retezec)
16: {
17: this.retezec = retezec;
18: }
19:
20: public override string ToString()
21: {
22: return retezec;
23: }
24: }
25:
26: // vsimnete si volani konstrukturu rodice
27: // na procviceni dedicnosti
28: class Hodnota : Klic
29: {
30: public Hodnota(string retezec) : base(retezec) {}
31: }
32:
33: class Program
34: {
35: static void Main(string[] args)
36: {
37: Hashtable kolekce = new Hashtable(51, 0.5f);
38: // nastavili jsme kapacitu na 51 polozek a faktor
39: // zaplneni na 0.5, coz znamena ze bude
40: // hashova tabulka zaplnena vzdy jen z jedne poloviny
41:
42: Klic klic1 = new Klic("abc");
43: Klic klic2 = new Klic("xyz");
44:
45: Hodnota hodnota1 = new Hodnota("hodnota");
46:
47: // pridani polozek
48: kolekce.Add(klic1, hodnota1);
49: kolekce.Add(klic2, hodnota1);
50:
51: Console.WriteLine(kolekce[klic2]); // vypise 'hodnota'
52:
53: // odebrani polozky
54: kolekce.Remove(klic2);
55:
56: // jak projit vsechny objekty v hashtabulce?
57: // pomoci enumeratoru:
58: IDictionaryEnumerator enumerator = kolekce.GetEnumerator();
59: while (enumerator.MoveNext())
60: {
61: Console.WriteLine(enumerator.Key.ToString() + " " +
62: enumerator.Value.ToString());
63: }
64:
65: // nebo pomoci foreach
66: foreach (DictionaryEntry polozka in kolekce)
67: {
68: Console.WriteLine(polozka.Key.ToString() + " " +
69: polozka.Value.ToString());
70: }
71:
72: // vypise dvakrat 'abc hodnota'
73: Console.ReadLine();
74:
75: }
76: }
77: }