Mi az a hash-tábla?

Hash-tábla egy olyan adatszerkezet, amely egy asszociatív tömböt (szótárat) valósít meg. Párokat tárol "kulcs-érték", ahol a kulcsok egyediek.

Alapelvek:

• Hash függvény: Átalakítja a kulcsot egy számra (hash-kód vagy index). Ez az index mutat a tárolási helyre a tömbben (kosár).
• Tömb (kosarak): A "kulcs-érték" párok tényleges tárolása.
• Ütközések: Olyan helyzet, amikor különböző kulcsok ugyanazt a hash-kódot generálják.

Ütközések kezelése:

• Láncolási módszer (Separate chaining): Minden kosárban egy lista (vagy más adatstruktúra) tárolja ugyanazt a hash-kódot kapott elemeket.
• Nyitott címzés (Open addressing): Ütközés esetén különböző stratégiák (lineáris szondázás, kvadratikus szondázás, dupla hash) alkalmazásával keresünk szabad kosarat.

Jellemzők:

• Gyors hozzáférés: Ideális esetben O(1) beszúrás, keresés és törlés műveletekre.
• A hash függvény minőségétől függ: A hash függvény és az ütközéskezelési stratégia jelentősen befolyásolja a teljesítményt.
• Memóriahasználat: További memóriát igényel a kosarak tömbje.

Használat QA-ban:

• Tesztadatok tárolása (kulcs - paraméter neve, érték - várt vagy tényleges érték).
• Az elemek egyediségeinek ellenőrzése (pl. felhasználói azonosítók).
• Gyorsítótárazás (cache) megvalósítása.