Kā ir uzbūvēta hash tabula unordered_map konteinerā?

unordered_map C++ realizēts kā haštabula.

Darbo princips:

1. Hašēšana: Atslēga tiek pārvērsta par veselīgu skaitli — haškodu — ar hašfunkcijas palīdzību.
2. Indeksēšana: Haškods tiek izmantots, lai noteiktu indeksu (korpusi vai baketu) masīvā ar norādītājiem vai sarakstiem.
3. Glabāšana: Katrā korpusā tiek glabāti atslēgu-vertību pāri.

Īpatnības:

• Korpusi: Haštabula sastāv no korpusu masīva. Korpusu skaits var dinamiski mainīties (rehašēšana), sasniedzot noteiktu slodzes koeficientu.
• Kolīzijas: Dažādi atslēgas var dot vienādu haškodu. To sauc par kolīziju. Lai risinātu kolīzijas unordered_map, tiek izmantota ķēdēšanas (chaining) metode: elementi ar vienādu haškodu tiek pievienoti sasaistītā sarakstā (vai citā datu struktūrā) attiecīgajā korpusā.
• Hašfunkcija un salīdzināšanas funkcija: Lai nodrošinātu pareizu darbību, nepieciešamas divas lietas:
  • Labas hašfunkcijas, kas vienmērīgi sadala atslēgas pa korpusiem, samazinot kolīziju skaitu.
  • Vienādošanas funkcija (== operators), lai atšķirtu atslēgas ar vienādu haškodu vienā korpusā.
• Veiktspēja: Vidēji, ievietošanas, dzēšanas un meklēšanas operācijas ir ar laika sarežģītību O(1). Sliktākajos gadījumos (piemēram, ar daudzām kolīzijām vai slikti izvēlētu hašfunkciju) veiktspēja var samazināties līdz O(n), kur n — elementu skaits.

Piemēra struktūra (vienkāršota):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Sasaistīta saraksta elements
};

struct Bucket {
  Node* head; // Saites uz saraksta sākumu
};

Bucket* buckets; // Korpusu masīvs
size_t num_buckets;

Elementa pievienošanas process:

1. Aprēķina atslēgas haškodu.
2. Nosaka korpusa indeksu: bucket_index = hash(key) % num_buckets.
3. Atslēgu-vertību pāris tiek pievienots attiecīgā korpusa sarakstā. Ja atslēga jau ir, vērtība tiek atjaunināta.

Elementa meklēšanas process:

1. Aprēķina atslēgas haškodu.
2. Nosaka korpusa indeksu.
3. Pārlūko šī korpusa sarakstu, salīdzinot atslēgas ar == operatoru.

Rehašēšana notiek, kad elementu skaits pārsniedz noteiktu slieksni (load factor). Tad tiek izveidots jauns, lielāks korpusu masīvs, un visi elementi no vecajiem korpusiem tiek rehašēti un pārvietoti jaunajos.