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:  }