Jak je v kontejneru unordered_map strukturována hash tabulka?

unordered_map v C++ je implementován jako hash tabulka.

Princip fungování:

1. Hashování: Klíč je převeden na celé číslo — hash kód — pomocí hashovací funkce.
2. Indexace: Hash kód se používá k určení indexu (kontejner nebo bucket) v poli ukazatelů nebo seznamů.
3. Uložení: V každém bucketu jsou uloženy páry klíč-hodnota.

Vlastnosti:

• Bucket: Hash tabulka se skládá z pole bucketů. Počet bucketů se může dynamicky měnit (rehashování), když je dosažen určitý faktor zatížení.
• Kolize: Různé klíče mohou dávat stejný hash kód. To se nazývá kolize. Pro řešení kolizí se v unordered_map používá metoda ** chaining **: prvky se stejným hashem jsou přidávány do spojovaného seznamu (nebo jiné datové struktury) v příslušném bucketu.
• Hashovací funkce a funkce porovnání: Pro správnou funkci jsou potřeba dvě věci:
  • Dobrá hashovací funkce, která rovnoměrně rozděluje klíče mezi buckety, minimalizuje kolize.
  • Operátor == pro rozlišení klíčů se stejným hashem v jednom bucketu.
• Výkon: Průměrně mají operace vkládání, mazání a hledání časovou složitost O(1). V nejhorším případě (například při velkém počtu kolizí nebo špatně zvolené hashovací funkci) může výkon klesnout na O(n), kde n je počet prvků.

Příklad struktury (zjednodušené):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Pro spojovaný seznam v bucketu
};

struct Bucket {
  Node* head; // Ukazatel na začátek seznamu
};

Bucket* buckets; // Pole bucketů
size_t num_buckets;

Proces přidání prvku:

1. Vypočítá se hash kód klíče.
2. Určí se index bucketu: bucket_index = hash(key) % num_buckets.
3. Pár klíč-hodnota se přidá do seznamu prvků v tomto bucketu. Pokud klíč již existuje, aktualizuje se hodnota.

Proces hledání prvku:

1. Vypočítá se hash kód klíče.
2. Určí se index bucketu.
3. Prochází se seznam prvků v tomto bucketu, porovnávají se klíče s hledaným pomocí operátoru ==.

Rehashing nastává, když počet prvků v poměru k počtu bucketů překročí práh (faktor zatížení). Během rehashingu se vytvoří nový, větší pole bucketů a všechny prvky ze starých bucketů jsou znovu hashovány a přesunuty do nových.