Din ce componente este formată un tabel hash?

O tabel hash constă din:

1. Array (sau listă): Structura principală de date în care sunt stocate elementele. Uneori sunt numite "găleți" (buckets) sau "sloturi".
2. Funcție hash: Funcție care primește o cheie ca intrare și returnează un indice (număr întreg) în array. O funcție hash bună asigură o distribuție uniformă a cheilor în array, minimizând coliziunile.
3. Mecanism de gestionare a coliziunilor: Metodă pentru rezolvarea situației când funcția hash generează același indice pentru diferite chei. Două metode principale:
   • Încâlcire (Separate Chaining): Fiecare element al array-ului stochează un pointer către o listă (listă legată, arbore B etc.) de elemente care au fost hash-uite în acel indice.
   • Adresare deschisă (Open Addressing): În cazul unei coliziuni, se caută alt loc liber în array pentru a plasa elementul. Strategii de căutare:
     • Probing liniar (Linear Probing)
     • Probing pătratic (Quadratic Probing)
     • Dublu hash (Double Hashing)
4. Operații: Implementarea operațiilor de bază: inserare (insert), căutare (search), ștergere (delete). Aceste operații folosesc funcția hash pentru a determina poziția elementelor în array și mecanismul de gestionare a coliziunilor dacă este necesar.