Z čeho se skládá hash tabulka?

Hash tabulka se skládá z pole pevné velikosti (kbelík nebo slot) a hashovací funkce.

• Pole (Kbelíky/Sloty): Představuje posloupnost buněk, ve kterých jsou uloženy páry "klíč-hodnota". Velikost pole určuje počet možných míst pro uložení prvků.

• Hashovací funkce: Převádí klíč na celé číslo (hash kód), které se používá k určení indexu buňky v poli (kbelíku), kde bude hodnota uložena nebo odkud bude extrahována.

Dále může být přítomna:

• Strategie řešení kolizí: Mechanismus pro zpracování situací, kdy různé klíče generují stejný hash kód a ukazují na stejnou buňku pole. Časté strategie:
  • Řetězení (Separate Chaining): Každá buňka pole uchovává ukazatel na spojový seznam (nebo jinou datovou strukturu), který obsahuje všechny páry "klíč-hodnota", jejichž hash kódy ukazují na tuto buňku.
  • Otevřené adresování: Při kolizi se hledá volná buňka v poli podle určitého pravidla (například lineární nebo kvadratické sondování).