Kaip yra sukurta hash lentelė unordered_map konteineryje?

unordered_map C++ įgyvendintas kaip žemės maišos lentelė.

Veikimo principas:

1. Maišavimas: Raktas paverčiamas į sveikąjį skaičių — maišos kodą — naudojant maišos funkciją.
2. Indeksavimas: Maišos kodas naudojamas nustatyti indeksą (krepšelį arba baketą) masyve rodyklių arba sąrašų.
3. Saugojimas: Kiekviename krepšelyje saugomos raktų-vertės poros.

Ypatybės:

• Krepšeliai: Maišos lentelė susideda iš krepšelių masyvo. Krepšelių skaičius gali dinamiškai keistis (permaišymas) pasiekus tam tikrą apkrovos koeficientą.
• Kolizijos: Skirtingi raktai gali duoti tą patį maišos kodą. Tai vadinama kolizija. Norint išspręsti kolizijas unordered_map naudojama sekučių (chaining) metodas: elementai su tuo pačiu maišos kodu pridedami į susietą sąrašą (ar kitą duomenų struktūrą) atitinkame krepšelyje.
• Maišos funkcija ir palyginimo funkcija: Norint tinkamai veikti, reikalingi du dalykai:
  • Geras maišos funkcija, kuri tolygiai paskirsto raktus po krepšelius, sumažindama kolizijų skaičių.
  • Lygumo funkcija (== operatorius), skirta atskirti raktus su tuo pačiu maišos kodu viename krepšelyje.
• Našumas: Vidutiniškai, įterpimo, ištrynimo ir paieškos operacijos turi laiko sudėtingumą O(1). Blogiausiu atveju (pvz., dėl daugybės kolizijų arba blogai parinktos maišos funkcijos) našumas gali sumažėti iki O(n), kur n — elementų skaičius.

Pavyzdinė struktūra (supaprastinta):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Susieto sąrašo elementas
};

struct Bucket {
  Node* head; // Nuoroda į sąrašo pradžią
};

Bucket* buckets; // Krepšelių masyvas
size_t num_buckets;

Elemento pridėjimo procesas:

1. Apskaičiuojamas rakto maišos kodas.
2. Nustatomas krepšelio indeksas: bucket_index = hash(key) % num_buckets.
3. Raktų-vertės pora pridedama į atitinkamo krepšelio sąrašą. Jei raktas jau yra, vertė atnaujinama.

Elemento paieškos procesas:

1. Apskaičiuojamas rakto maišos kodas.
2. Nustatomas krepšelio indeksas.
3. Peržiūrimas šio krepšelio sąrašas, lyginant raktus naudojant == operatorių.

Permaišymas vyksta, kai elementų skaičius viršija nustatytą slenkstį (load factor). Tada sukuriamas naujas, didesnis krepšelių masyvas, ir visi elementai iš senųjų krepšelių permaišomi ir perkeliami į naujus.