Kuidas töötab hajutustabel?

Hash-tabel (hash table) on andmestruktuur, mis realiseerib assotsiatiivse massiivi.

Tööpõhimõte:

1. Hashimine. Iga võtme (key) jaoks arvutatakse hash-kood (hash code) hash-funktsiooni (hash function) abil. Hash-kood on täisarv.
2. Indekseerimine. Hash-kood kasutatakse indeksi (index) määramiseks sisemise struktuuri massiivis (või vektoris). Tavaliselt arvutatakse indeks kui hash_code % array_size, kus array_size on massiivi suurus.
3. Salvestamine. Leidmisel indeksis salvestatakse seotud väärtus (value) võtmega.

Probleemid ja nende lahendused:

• Kolizioonid. Erinevad võtmed võivad anda sama hash-koodi ja seega sama indeksi massiivis. Seda nimetatakse kolitsiooniks.
  • Kolitsioonide lahendamise meetodid:
    • Eraldatud ahelad (Separate Chaining) meetod: Igas massiivi elemendis hoitakse nimekiri (või vektor) "võti- väärtus" paaridest. Kolitsiooni korral lisatakse uus paar sellele nimekirjale. Otsing indeksil hõlmab selle nimekirja läbivaatamist, et leida vajalik võti.
    • Ava aadressimine (Open Addressing) meetod: Kolitsiooni korral otsitakse teist vaba kohta massiivis kindla reegli (katse) järgi.
      • Lineaarne katse (Linear Probing): Kontrollitakse kohti index + 1, index + 2 ja nii edasi, mooduli massiivi suurusest.
      • Kvadraatne katse (Quadratic Probing): Kontrollitakse kohti index + 1^2, index + 2^2 ja nii edasi, mooduli massiivi suurusest.
      • Topelt-hashimine (Double Hashing): Teine hash-funktsioon määrab katse sammu.

Eelised:

• Keskmiselt teostatakse sisestus-, kustutamis- ja otsingutegevusi O(1) keerukusega.

Puudused:

• Halvimal juhul (näiteks, kui palju kolitsioone või halb hash-funktsioon) võib tegevuste keerukus jõuda O(n), kus n on elementide arv.
• Vajab täiendavat mälu (näiteks, loendite jaoks eraldatud ahelate meetodil või katse jaoks avatud aadressimisel).

Näide kasutamisest C++-s (std::unordered_map):

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

int main() {
    // Hash-tabeli loomine (unordered_map)
    std::unordered_map<std::string, int> vanus;

    // Elementide lisamine
    vanus["Alice"] = 30;
    vanus["Bob"] = 25;
    vanus["Charlie"] = 35;

    // Väärtuse saamine võtmega
    std::cout << "Alice vanus: " << vanus["Alice"] << std::endl;

    // Elementi otsimine
    if (vanus.count("Bob")) {
        std::cout << "Bob on kaardil." << std::endl;
    }

    // Elementi kustutamine
    vanus.erase("Charlie");

    return 0;
}