Jak funguje hashovací tabulka?

Hashová tabulka (hash table) je datová struktura, která implementuje asociativní pole.

Princip fungování:

1. Hashování. Pro každý klíč (key) se vypočítá hash kód (hash code) pomocí hash funkce (hash function). Hash kód je celé číslo.
2. Indexování. Hash kód se používá k určení indexu (index) v poli (nebo vektoru) vnitřní struktury hashové tabulky. Obvykle se index počítá jako hash_code % velikost_pole, kde velikost_pole je velikost pole.
3. Uložení. Na nalezeném indexu je uložená hodnota (value) spojená s klíčem.

Problémy a jejich řešení:

• Kolize. Různé klíče mohou dávat stejný hash kód a tím pádem i stejný index v poli. To se nazývá kolize.
  • Metody řešení kolizí:
    • Řetězení (Separate Chaining): V každé buňce pole je uložen seznam (seznam, vektor, atd.) párů "klíč-hodnota". Při kolizi je nový pár přidán do tohoto seznamu. Při hledání podle indexu se prohledá odpovídající seznam, aby se našel požadovaný klíč.
    • Otevřené adresování (Open Addressing): Při kolizi se hledá jiná volná buňka v poli podle určitého pravidla (sondování).
      • Lineární sondování (Linear Probing): Kontrolují se postupně buňky index + 1, index + 2, atd., modulo velikost pole.
      • Kvadratické sondování (Quadratic Probing): Kontrolují se buňky index + 1^2, index + 2^2, atd., modulo velikost pole.
      • Dvojité hashování (Double Hashing): Používá se druhá hash funkce k určení kroku sondování.

Výhody:

• Průměrně jsou operace vkládání, mazání a hledání prováděny s složitostí O(1).

Nevýhody:

• V nejhorším případě (například při velkém počtu kolizí nebo špatné hash funkci) může složitost operací dosáhnout O(n), kde n je počet prvků.
• Vyžaduje další paměť (například pro seznamy při metodě řetězení nebo pro sondování při otevřeném adresování).

Příklad použití v C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Vytvoření hashové tabulky (unordered_map)
    std::unordered_map<std::string, int> věk;

    // Vložení prvků
    věk["Alice"] = 30;
    věk["Bob"] = 25;
    věk["Charlie"] = 35;

    // Získání hodnoty podle klíče
    std::cout << "Věk Alice: " << věk["Alice"] << std::endl;

    // Vyhledání prvku
    if (věk.count("Bob")) {
        std::cout << "Bob je v mapě." << std::endl;
    }

    // Odstranění prvku
    věk.erase("Charlie");

    return 0;
}