Mi az a hash-tábla?

A hash-tábla, vagy asszociatív tömb, egy olyan adatszerkezet, amely az asszociatív tömb felületét valósítja meg, azaz kulcsokat köt össze értékekkel. Hash függvényt használ az index, vagy "hash" kiszámítására, ahol a keresett értéknek lennie kell.

Fő összetevők:

• Kulcs: Az elem egyedi azonosítója.
• Érték: A kulccsal összekapcsolt adatok.
• Hash függvény: A kulcsot numerikus értékké (hash) alakítja, amelyet az index meghatározására használnak.
• Kosarak (Buckets): Egy tömb, ahol a kulcs-érték párokat tárolják.
• Ütközéskezelés (Collision Handling): Olyan mechanizmus, amely megoldja azokat a helyzeteket, amikor különböző kulcsok ugyanarra a hash értékre adnak, és így ugyanarra a kosárra mutatnak. Gyakori módszerek:
  • Láncolási módszer (Chaining): Minden kosárban egy lista (pl. összekapcsolt lista) tárolja azokat az elemeket, amelyek hash értéke erre a kosárra mutat.
  • Nyitott címzéses módszer (Open Addressing): Ütközés esetén a következő szabad kosarat keresi lineáris, kvadratikus vagy kettős hash-elés algoritmusok segítségével.

Működési elv:

1. Beszúrás: A hash függvényt alkalmazzuk a kulcsra, hogy hash értéket kapjunk. A hash érték alapján határozzuk meg a kosár indexét. A kulcs-érték pár ebbe a kosárba kerül. Ütközés esetén alkalmazzuk az ütközéskezelő módszert.

   // Példa elem beszúrására hash-táblába (láncolási módszer)
   function insert(key, value) {
     const hash = hashFunction(key); // Hash számítása
     const bucketIndex = hash % tableSize; // Kosár indexének meghatározása
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Lista létrehozása, ha nem létezik
     }
     buckets[bucketIndex].push({ key, value }); // Pár hozzáadása a listához
   }
   

2. Keresés: A hash függvényt alkalmazzuk a kulcsra, hogy hash értéket kapjunk. A hash alapján meghatározzuk a kosár indexét. Ezután ebben a kosárban keresünk a megadott kulccsal. Láncolási módszernél a lista belsejében keresünk. Nyitott címzés esetén egymás után ellenőrizzük a többi kosarat, amíg meg nem találjuk a keresett elemet vagy meg nem állapítjuk annak hiányát.

   // Példa elem keresésére hash-táblában (láncolási módszer)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Hash számítása
     const bucketIndex = hash % tableSize; // Kosár indexének meghatározása
   
     if (buckets[bucketIndex]) {
       // Elem keresése a kosár listájában
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Ha törlés szükséges
           return value; // Érték visszaadása
         }
       }
     }
     return undefined; // Elem nem található
   }
   

Előnyök:

• Magas sebesség az beszúrás, keresés és törlés műveletekben átlagosan (O(1)).
• Hatékony memóriahasználat a közvetlen hozzáférésű tömbhöz képest (ha a kulcsok ritkán oszlanak el).

Hátrányok:

• A teljesítmény romolhat sok ütközés esetén (rosszabb esetben O(n)).
• Nem őrzi meg az elemek beszúrási sorrendjét.
• Jó hash függvény szükséges a kulcsok egyenletes eloszlásához.