Kā darbojas haštabula?

Hash tabula (hash table) ir struktūra datu, kas realizē asociatīvo masīvu.

Darba princips:

1. Hashēšana. Katram atslēgas (key) tiek aprēķināts hash kods (hash code) ar hash funkciju (hash function). Hash kods ir vesels skaitlis.
2. Indeksēšana. Hash kods tiek izmantots, lai noteiktu indeksu (index) iekšējā struktūras masīvā (vai vektorā). Parasti indekss tiek aprēķināts kā hash_code % array_size, kur array_size ir masīva izmērs.
3. Glabāšana. Atrodot indeksu, masīvā tiek glabāta ar atslēgu saistītā vērtība (value).

Problēmas un risinājumi:

• Kolīzijas. Dažādi atslēgas var dot to pašu hash kodu un, attiecīgi, to pašu indeksu masīvā. To sauc par kolīziju.
  • Kolīziju risināšanas metodes:
    • Atsevišķu ķēžu (Separate Chaining) metode: Katras masīva šūnas glabā sarakstu (vai vektoru) ar "atslēga-vērtība" pāriem. Kolīzijas gadījumā jauns pāris tiek pievienots šim sarakstam. Meklēšanā pēc indeksa tiek pārskatīts attiecīgais saraksts, lai atrastu vajadzīgo atslēgu.
    • Atvērtās adresēšanas (Open Addressing) metode: Kolīzijas gadījumā tiek meklēta cita brīva šūna masīvā pēc noteikta noteikuma (pārbaude).
      • Līnijas pārbaude (Linear Probing): Tiek pārbaudītas šūnas index + 1, index + 2 un tā tālāk, ņemot moduli pēc masīva izmēra.
      • Kvadrātiskā pārbaude (Quadratic Probing): Tiek pārbaudītas šūnas index + 1^2, index + 2^2 un tā tālāk, ņemot moduli pēc masīva izmēra.
      • Dubultā hashēšana (Double Hashing): Otrā hash funkcija tiek izmantota, lai noteiktu soļa lielumu.

Priekšrocības:

• Vidēji, ievietošanas, dzēšanas un meklēšanas operācijas tiek veiktas ar sarežģītību O(1).

Trūkumi:

• Sliktākajos gadījumos (piemēram, daudz kolīziju vai sliktas hash funkcijas gadījumā) operāciju sarežģītība var sasniegt O(n), kur n ir elementu skaits.
• Prasa papildu atmiņu (piemēram, sarakstiem atsevišķu ķēžu metodē vai pārbaudei ar atvērtās adresēšanas metodi).

Piemērs C++ izmantošanai (std::unordered_map):

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

int main() {
    // Izveidot hash tabulu (unordered_map)
    std::unordered_map<std::string, int> vecums;

    // Ievietot elementus
    vecums["Alice"] = 30;
    vecums["Bob"] = 25;
    vecums["Charlie"] = 35;

    // Saņemt vērtību pēc atslēgas
    std::cout << "Alice vecums: " << vecums["Alice"] << std::endl;

    // Meklēt elementu
    if (vecums.count("Bob")) {
        std::cout << "Bob ir kartē." << std::endl;
    }

    // Dzēst elementu
    vecums.erase("Charlie");

    return 0;
}