Din ce este format un tabel hash?

O tabelă hash constă dintr-un array de dimensiune fixă (căldare sau slot) și o funcție hash.

• Array (Căldări/Sloturi): Reprezintă o secvență de celule în care sunt stocate perechi "cheie-valoare". Dimensiunea array-ului determină numărul de locuri posibile pentru stocarea elementelor.

• Funcție hash: Transformă cheia într-o valoare întreagă (cod hash), care este utilizată pentru a determina indicele celulei în array (căldare), unde va fi stocată sau de unde va fi extrasă valoarea corespunzătoare.

De asemenea, poate exista:

• Strategie de rezolvare a coliziunilor: Mecanism pentru gestionarea situațiilor în care cheile diferite generează același cod hash și indică aceeași celulă a array-ului. Strategii comune:
  • Chaining (Încâlcire): Fiecare celulă a array-ului stochează un pointer către o listă legată (sau altă structură de date), care conține toate perechile "cheie-valoare" ale căror coduri hash indică către acea celulă.
  • Adresare deschisă: În cazul coliziunii, se caută o celulă liberă în array conform unei reguli stabilite (de exemplu, sondare liniară sau pătratică).