Ce este un tabel hash?

O tabel hash este o structură de date care implementează un array asociativ (dicționar). Stochează perechi "cheie-valoare", unde cheile sunt unice.

Principii de bază:

• Funcție hash: Transformă cheia într-un număr (cod hash sau index). Acest index indică locul de stocare a valorii în array (coș).
• Array (coșuri): Stocarea efectivă a perechilor "cheie-valoare".
• Coliziuni: Situația în care cheile diferite generează același cod hash.

Rezolvarea coliziunilor:

• Metoda de lanț (Separate chaining): În fiecare coș se păstrează o listă (sau altă structură de date) de elemente cu același cod hash.
• Adresare deschisă (Open addressing): În cazul coliziunii, se caută un coș liber folosind diferite strategii (sondare liniară, sondare pătratică, dublu hash).

Caracteristici:

• Acces rapid: În cazul ideal O(1) pentru operațiile de inserare, căutare și ștergere.
• Dependența de funcția hash: Calitatea funcției hash și strategia de rezolvare a coliziunilor influențează semnificativ performanța.
• Utilizarea memoriei: Necesită memorie suplimentară pentru array-ul de coșuri.

Utilizare în QA:

• Stocarea datelor de test (cheie - numele parametrului, valoare - valoarea așteptată sau reală).
• Verificarea unicitații elementelor (de exemplu, ID-uri de utilizatori).
• Implementarea cache-urilor.