Ako funguje hashovacia tabuľka?

Hash tabuľka (hash table) je dátová štruktúra, ktorá implementuje asociatívny poľom.

Princíp práce:

1. Hashovanie. Pre každý kľúč (key) sa vypočíta hash kód (hash code) pomocou hash funkcie (hash function). Hash kód je celé číslo.
2. Indexovanie. Hash kód sa používa na určenie indexu (index) v poli (alebo vektore) vnútornej štruktúry hash tabuľky. Zvyčajne sa index vypočíta ako hash_code % array_size, kde array_size je veľkosť poľa.
3. Uloženie. Na nájdenom indexe v poli sa uloží spojená hodnota (value) s kľúčom.

Problémy a ich riešenia:

• Kolízie. Rôzne kľúče môžu dávať rovnaký hash kód a teda aj rovnaký index v poli. Toto sa nazýva kolízia.
  • Metódy riešenia kolízií:
    • Metóda reťazcov (Separate Chaining): V každej bunke poľa sa uchová zoznam (zoznam, vektor a pod.) dvojíc "kľúč-hodnota". Pri kolízii sa nová dvojica pridá do tohto zoznamu. Pri vyhľadávaní podľa indexu sa prehliada príslušný zoznam na nájdenie požadovaného kľúča.
    • Metóda otvorenej adresácie (Open Addressing): Pri kolízii sa hľadá iná voľná bunka v poli podľa určeného pravidla (probijanie).
      • Lineárne probíjanie (Linear Probing): Postupne sa kontrolujú bunky index + 1, index + 2 a tak ďalej, modulo veľkosti poľa.
      • Kvadratické probíjanie (Quadratic Probing): Kontrolujú sa bunky index + 1^2, index + 2^2 a tak ďalej, modulo veľkosti poľa.
      • Dvojité hashovanie (Double Hashing): Používa sa druhá hash funkcia na určenie kroku probíjania.

Výhody:

• V priemere sa operácie vkladania, odstraňovania a vyhľadávania vykonávajú s časovou zložitosťou O(1).

Nevýhody:

• V najhoršom prípade (napríklad pri veľkom počte kolízií alebo zlej hash funkcii) môže časová zložitosť operácií dosiahnuť O(n), kde n je počet prvkov.
• Vyžaduje si ďalšiu pamäť (napríklad pre zoznamy pri metóde reťazcov alebo pre probíjanie pri otvorenej adresácii).

Príklad použitia v C++ (std::unordered_map):

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

int main() {
    // Vytvorenie hash tabuľky (unordered_map)
    std::unordered_map<std::string, int> veky;

    // Vloženie prvkov
    veky["Alice"] = 30;
    veky["Bob"] = 25;
    veky["Charlie"] = 35;

    // Získanie hodnoty podľa kľúča
    std::cout << "Vek Alice: " << veky["Alice"] << std::endl;

    // Vyhľadanie prvku
    if (veky.count("Bob")) {
        std::cout << "Bob je v mape." << std::endl;
    }

    // Vymazanie prvku
    veky.erase("Charlie");

    return 0;
}