Hogyan épül fel egy hash-tábla az unordered_map konténerben?

Az unordered_map C++-ban hash-táblaként van megvalósítva.

Működési elv:

1. Hash-elés: A kulcs egy egész számra — hash-kódra — lesz alakítva egy hash-függvény segítségével.
2. Indexelés: A hash-kódot használják az index (kád vagy bucket) meghatározására egy mutatók vagy listák tömbjében.
3. Tárolás: Minden kádba kulcs-érték párok kerülnek tárolásra.

Jellemzők:

• Kádak: A hash-tábla egy kádakból álló tömbből áll. A kádak száma dinamikusan változhat (rehashing), amikor eléri a meghatározott terhelési tényezőt.
• Ütközések: Különböző kulcsok ugyanazt a hash-kódot adhatják. Ezt ütközésnek nevezik. Az ütközések feloldására az unordered_map a ** láncolás ** módszert használja: azonos hash-ű kulcsok egy összekapcsolt listába (vagy más adatstruktúrába) kerülnek a megfelelő kádba.
• Hash-függvény és összehasonlító függvény: A helyes működéshez két dolog szükséges:
  • Egy jó hash-függvény, amely egyenletesen osztja el a kulcsokat a kádak között, minimalizálva az ütközéseket.
  • Egy egyenlőség-függvény (==), amellyel meg lehet különböztetni az azonos hash-kódú kulcsokat ugyanabban a kábban.
• Teljesítmény: Átlagosan az beszúrás, törlés és keresés műveletek időkomplexitása O(1). A legrosszabb esetben (pl. sok ütközés vagy rosszul választott hash-függvény esetén) a teljesítmény O(n)-re romolhat, ahol n az elemek száma.

Egyszerűsített szerkezetpélda:

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // A láncolt lista a kádon belül
};

struct Bucket {
  Node* head; // A lista kezdete
};

Bucket* buckets; // Kádak tömbje
size_t num_buckets;

Elem hozzáadási folyamat:

1. A kulcs hash-kódja kiszámításra kerül.
2. A kád indexe meghatározásra kerül: bucket_index = hash(key) % num_buckets.
3. A kulcs-érték pár hozzáadódik az adott kád listájához. Ha a kulcs már létezik, az érték frissül.

Elem keresési folyamat:

1. A kulcs hash-kódja kiszámításra kerül.
2. A kád indexe meghatározásra kerül.
3. A kád listáját végigjárva, összehasonlítjuk a kulcsokat a keresett kulccsal a == operátor segítségével.

A rehashing akkor történik, amikor az elemek száma a kádak számához viszonyítva meghalad egy küszöböt (terhelési tényező). Rehashing során egy nagyobb, új kádakból álló tömb jön létre, és minden elem az eredeti kádakból újra hash-elve és átmozgatva kerül az új tömbbe.