Miből áll egy hash-tábla?

Hash-tábla a következőkből áll:

1. Tömb (vagy lista): Az adatstruktúra, amelyben az elemek tárolódnak. Néha "kád" (buckets) vagy "slot" néven is ismert.
2. Hash függvény: Olyan függvény, amely bemenetként egy kulcsot vesz, és egy egész számot ad vissza a tömbben. Egy jó hash függvény egyenletes eloszlást biztosít a kulcsok között, minimalizálva az ütközéseket.
3. Ütközéskezelő mechanizmus: Módszer arra, hogy megoldja a helyzetet, amikor a hash függvény ugyanazt az indexet generálja különböző kulcsokhoz. Két fő módszer:
   • Szétszórás (Separate Chaining): Minden tömb elem tartalmaz egy mutatót egy listára (láncolt lista, B-fa stb.), amely az adott indexhez tartozó hash-elt elemeket tartalmazza.
   • Nyitott címzés (Open Addressing): Ütközés esetén más szabad helyet keres a tömbben az elem elhelyezéséhez. Keresési stratégiák:
     • Lineáris próbálkozás (Linear Probing)
     • Kvadratikus próbálkozás (Quadratic Probing)
     • Dupla hash (Double Hashing)
4. Műveletek: Az alapműveletek megvalósítása: beszúrás (insert), keresés (search), törlés (delete). Ezek a műveletek a hash függvényt használják az elemek helyének meghatározására a tömbben, és az ütközéskezelő mechanizmust, ha szükséges.