Kako funkcioniše tabela heš?

Hash tabela (hash table) je struktura podataka koja implementira asocijativni niz.

Princip rada:

1. Hashiranje. Za svaki ključ (key) se izračunava hash kod (hash code) pomoću hash funkcije (hash function). Hash kod je celobrojna vrednost.
2. Indeksiranje. Hash kod se koristi za određivanje indeksa (index) u nizu (ili vektoru) unutrašnje strukture hash tabele. Obično se indeks računa kao hash_code % array_size, gde je array_size veličina niza.
3. Čuvanje. Na pronađeni indeks u nizu se čuva povezana vrednost (value) sa ključem.

Problemi i rešenja:

• Kolizije. Različiti ključevi mogu dati isti hash kod i, shodno tome, isti indeks u nizu. To se naziva kolizija.
  • Metode rešavanja kolizija:
    • Metod lančanog rešavanja (Separate Chaining): U svakoj ćoški niza se čuva lista (lista, vektor i sl.) parova "ključ-vrednost". Pri koliziji, nova par se dodaje u tu listu. Pri pretraživanju po indeksu, pregledava se odgovarajuća lista da bi se pronašao željeni ključ.
    • Metod otvorene adresacije (Open Addressing): Pri koliziji, traži se druga slobodna ćoška u nizu po određenom pravilu (probijanje).
      • Linearna proba (Linear Probing): Redom se proveravaju ćoške index + 1, index + 2 i tako dalje, modula veličine niza.
      • Kvadratna proba (Quadratic Probing): Proveravaju se ćoške index + 1^2, index + 2^2 i tako dalje, modula veličine niza.
      • Duple hashiranje (Double Hashing): Koristi se druga hash funkcija za određivanje koraka provere.

Prednosti:

• U proseku, operacije umetanja, brisanja i pretraživanja se obavljaju sa složenošću O(1).

Nedostaci:

• U najgorem slučaju (npr. pri velikom broju kolizija ili lošoj hash funkciji), složenost operacija može dostići O(n), gde je n broj elemenata.
• Zahteva dodatnu memoriju (npr. za liste kod metode lančanog rešavanja ili za proboj kod otvorene adresacije).

Primer upotrebe u C++ (std::unordered_map):

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

int main() {
    // Kreiranje hash tabele (unordered_map)
    std::unordered_map<std::string, int> starosti;

    // Umetanje elemenata
    starosti["Alice"] = 30;
    starosti["Bob"] = 25;
    starosti["Charlie"] = 35;

    // Dobijanje vrednosti po ključu
    std::cout << "Starost Alice: " << starosti["Alice"] << std::endl;

    // Pretraživanje elementa
    if (starosti.count("Bob")) {
        std::cout << "Bob je u mapi." << std::endl;
    }

    // Brisanje elementa
    starosti.erase("Charlie");

    return 0;
}