Hash-tábla hogyan működik?

A hash-tábla (hash table) egy olyan adatszerkezet, amely egy asszociatív tömböt valósít meg.

Működési elv:

1. Hash-elés. Minden kulcs (key) esetén egy hash-kód (hash code) kerül kiszámításra egy hash függvény (hash function) segítségével. A hash-kód egész szám.
2. Indexelés. A hash-kódot arra használják, hogy meghatározzák a tömb (vagy vektor) indexét a hash-tábla belső struktúrájában. Általában az indexet a hash_code % tömb_méret képlettel számítják, ahol a tömb_méret a tömb mérete.
3. Tárolás. A megtalált indexen tárolódik a kulcshoz kapcsolódó érték (value).

Problémák és megoldások:

• Ütközések. Különböző kulcsok ugyanazt a hash-kódot adhatják, így ugyanaz az index is lehet a tömbben. Ezt ütközésnek nevezik.
  • Az ütközések kezelésének módszerei:
    • Láncolás (Separate Chaining): Minden tömbcellában egy lista (lista, vektor, stb.) tárolja a "kulcs-érték" párokat. Ütközés esetén az új pár hozzáadódik ehhez a listához. Az index szerinti keresés során a listát végigiterálva találjuk meg a kívánt kulcsot.
    • Nyitott címzés (Open Addressing): Ütközés esetén más szabad cellát keresünk a tömbben egy meghatározott szabály szerint (szondázás).
      • Lineáris szondázás (Linear Probing): Sorban ellenőrizzük a index + 1, index + 2, stb. cellákat, a tömb méretének moduljával.
      • Kvadratikus szondázás (Quadratic Probing): Ellenőrizzük a index + 1^2, index + 2^2, stb. cellákat, a tömb méretének moduljával.
      • Dupla hash (Double Hashing): Egy második hash függvényt használunk a lépés meghatározására.

Előnyök:

• Átlagosan az beszúrás, törlés és keresés műveletek O(1) komplexitással végezhetők.

Hátrányok:

• A legrosszabb esetben (pl. sok ütközés vagy rossz hash függvény esetén) az műveletek komplexitása elérheti az O(n)-t, ahol n az elemek száma.
• További memóriát igényel (pl. láncolt listákhoz vagy nyitott címzéshez).

Példa C++-ban (std::unordered_map):

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

int main() {
    // Hash-tábla létrehozása (unordered_map)
    std::unordered_map<std::string, int> életkorok;

    // Elemek beszúrása
    életkorok["Alice"] = 30;
    életkorok["Bob"] = 25;
    életkorok["Charlie"] = 35;

    // Érték lekérése kulcs alapján
    std::cout << "Alice életkora: " << életkorok["Alice"] << std::endl;

    // Elem keresése
    if (életkorok.count("Bob")) {
        std::cout << "Bob benne van a térképen." << std::endl;
    }

    // Elem törlése
    életkorok.erase("Charlie");

    return 0;
}