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

Hash-tábla egy fix méretű tömbből (kád vagy slot) és egy hash-függvényből áll.

• Tömb (Kádak/Slotok): Olyan cellák sorozatát jelenti, amelyek "kulcs-érték" párokat tárolnak. A tömb mérete meghatározza a lehetséges helyek számát az elemek tárolására.

• Hash-függvény: A kulcsot egész szám értékre (hash-kód) alakítja, amit a tömbben (kád) lévő cella indexének meghatározására használnak, ahol a megfelelő érték tárolódik vagy kinyerésre kerül.

Ezen kívül, lehetnek:

• Ütközéskezelési stratégia: Mechanizmus arra, hogy kezelje az olyan helyzeteket, amikor különböző kulcsok ugyanazt a hash-kódot generálják, és ugyanarra a tömbcellára mutatnak. Gyakori stratégiák:
  • Láncolás (Separate Chaining): Minden tömbcellában egy mutató van egy összekapcsolt listára (vagy más adatstruktúrára), amely tartalmazza az összes "kulcs-érték" párt, amelyek hash-kódjai erre a cellára mutatnak.
  • Nyitott címzés: Ütközés esetén egy szabály szerint (pl. lineáris vagy kvadratikus szondázás) keresnek szabad cellát a tömbben.