Z jakých komponent se skládá hashovací tabulka?

Hashová tabulka se skládá z:

1. Pole (nebo seznam): Hlavní datová struktura, ve které jsou uloženy prvky. Někdy se nazývá "kbelíky" (buckets) nebo "sloty".
2. Hashovací funkce: Funkce, která přijímá klíč jako vstup a vrací index (celé číslo) v poli. Dobrá hashovací funkce zajišťuje rovnoměrné rozložení klíčů v poli, minimalizující kolize.
3. Mechanismus řešení kolizí: Metoda, jak řešit situaci, kdy hashovací funkce generuje stejný index pro různé klíče. Dva hlavní způsoby:
   • Oddělené řetězení (Separate Chaining): Každý prvek pole uchovává ukazatel na seznam (spojený seznam, B-strom atd.) prvků, které byly hashovány na tento index.
   • Otevřená adresace (Open Addressing): Při kolizi se hledá jiné volné místo v samotném poli pro umístění prvku. Strategie hledání:
     • Lineární sondování (Linear Probing)
     • Kvadratické sondování (Quadratic Probing)
     • Dvojité hashování (Double Hashing)
4. Operace: Implementace základních operací: vkládání (insert), hledání (search), mazání (delete). Tyto operace používají hashovací funkci k určení umístění prvků v poli a mechanismus řešení kolizí podle potřeby.