Ako je štruktúrovan hash tabuľka v kontajneri unordered_map?

unordered_map v C++ je implementovaný ako hash tabuľka.

Princíp práce:

1. Hashovanie: Kľúč sa prevedie na celé číslo — hash kód — pomocou hash funkcie.
2. Indexovanie: Hash kód sa používa na určenie indexu (košíka alebo baketu) v poli ukazovateľov alebo zoznamov.
3. Ukladanie: V každom košíku sa ukladajú páry kľúč-hodnota.

Vlastnosti:

• Košíky: Hash tabuľka pozostáva z poľa košíkov. Počet košíkov sa môže dynamicky meniť (rehashovanie) pri dosiahnutí určitého koeficientu zaťaženia.
• Kolízie: Rôzne kľúče môžu dávať rovnaký hash kód. Toto sa nazýva kolízia. Na riešenie kolízií v unordered_map sa používa metóda reťazcov (chaining): prvky s rovnakým hashom sa pridávajú do prepojeného zoznamu (alebo inej dátovej štruktúry) v príslušnom košíku.
• Hash funkcia a funkcia porovnania: Pre správnu funkciu sú potrebné dve veci:
  • Dobrá hash funkcia, ktorá rovnomerne rozdeľuje kľúče po košíkoch, minimalizujúc kolízie.
  • Funkcia ekvivalencie (operator ==), aby sa odlíšili kľúče s rovnakým hash kódom v jednom košíku.
• Výkonnosť: Priemerné operácie vkladania, odstraňovania a vyhľadávania majú časovú zložitosť O(1). V najhoršom prípade (napríklad pri veľkom počte kolízií alebo zle zvolenej hash funkcii) sa výkon môže zhoršiť na O(n), kde n je počet prvkov.

Príklad štruktúry (zjednodušene):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Pre prepojený zoznam v košíku
};

struct Bucket {
  Node* head; // Ukazovateľ na začiatok zoznamu
};

Bucket* buckets; // Pole košíkov
size_t num_buckets;

Proces pridania prvku:

1. Vypočíta sa hash kód kľúča.
2. Určí sa index košíka: bucket_index = hash(key) % num_buckets.
3. Pár kľúč-hodnota sa pridá do zoznamu prvkov v tomto košíku. Ak kľúč už existuje, hodnota sa aktualizuje.

Proces vyhľadávania prvku:

1. Vypočíta sa hash kód kľúča.
2. Určí sa index košíka.
3. Prejde sa zoznam prvkov v tomto košíku, porovnávajúc kľúče pomocou operátora ==.

Rehashing sa vykonáva, keď počet prvkov voči počtu košíkov prekročí stanovený prah (load factor). Pri rehashingu sa vytvorí nový, väčší zoznam košíkov a všetky prvky zo starých košíkov sa re-hashujú a presúvajú do nových.