Kaip veikia maišos lentelė?

Žodynėlis (hash table) — tai duomenų struktūra, įgyvendinanti asociatyvųjį masyvą.

Veikimo principas:

1. Hash'inimas. Kiekvienam raktui (key) apskaičiuojamas hash kodas (hash code) naudojant hash funkciją (hash function). Hash kodas yra sveikas skaičius.
2. Indeksavimas. Hash kodas naudojamas nustatyti indeksą (index) vidinėje struktūros masyve (arba vektoriuje). Paprastai indeksas skaičiuojamas kaip hash_code % array_size, kur array_size yra masyvo dydis.
3. Saugojimas. Suradus indeksą, masyve saugoma susijusi su raktu reikšmė (value).

Problemos ir jų sprendimai:

• Kolizijos. Skirtingi raktai gali duoti tą patį hash kodą ir, atitinkamai, tą patį indeksą masyve. Tai vadinama kolizija.
  • Kolizijų sprendimo metodai:
    • Atskirų grandinių (Separate Chaining) metodas: Kiekvienoje masyvo ląstelėje saugomas sąrašas (arba vektorius) porų "raktas-reikšmė". Kolizijos atveju nauja pora pridedama į šį sąrašą. Paieška pagal indeksą apžvelgiama atitinkamas sąrašas, kad rastų reikiamą raktą.
    • Atvirosios adresacijos (Open Addressing) metodas: Kolizijos atveju ieškoma kita laisva ląstelė masyve pagal tam tikrą taisyklę (bandymą).
      • Linijinis bandymas (Linear Probing): Tikrinamos ląstelės index + 1, index + 2 ir t.t., imant modulį pagal masyvo dydį.
      • Kvadratinis bandymas (Quadratic Probing): Tikrinamos ląstelės index + 1^2, index + 2^2 ir t.t., imant modulį pagal masyvo dydį.
      • Dvigubas hash'inimas (Double Hashing): Naudojama antra hash funkcija, nustatant žingsnio dydį.

Privalumai:

• Vidutiniškai, įterpimo, ištrynimo ir paieškos operacijos vykdomos su sudėtingumu O(1).

Trūkumai:

• Blogiausiu atveju (pavyzdžiui, esant daug kolizijų arba blogai hash funkcijai) operacijų sudėtingumas gali siekti O(n), kur n — elementų skaičius.
• Reikalauja papildomos atminties (pavyzdžiui, sąrašų naudojant atskirų grandinių metodą arba bandymui naudojant atvirą adresaciją).

Pavyzdys naudojimo C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Sukurti hash lentelę (unordered_map)
    std::unordered_map<std::string, int> amžius;

    // Įterpti elementus
    amžius["Alice"] = 30;
    amžius["Bob"] = 25;
    amžius["Charlie"] = 35;

    // Gauti reikšmę pagal raktą
    std::cout << "Alice amžius: " << amžius["Alice"] << std::endl;

    // Rasti elementą
    if (amžius.count("Bob")) {
        std::cout << "Bob yra žemėlapyje." << std::endl;
    }

    // Ištrinti elementą
    amžius.erase("Charlie");

    return 0;
}