Puteți explica principiul de funcționare al unui tabel hash și modul în care sunt stocate datele în acesta?

O masă de dispersie este o structură de date care asigură acces foarte rapid la date pe baza cheii. Principiul de funcționare se bazează pe utilizarea unei funcții de dispersie, care transformă cheia într-un index al unui array, unde este stocată valoarea corespunzătoare.

Când trebuie să salvăm un cuplu cheie-valoare, funcția de dispersie calculează indexul, iar datele sunt plasate în celula array-ului la acel index. La căutarea după cheie, funcția de dispersie calculează din nou indexul, și valoarea necesară este găsită rapid.

Dacă două chei diferite dau același index (coliziune), de obicei se folosește metoda lanțurilor: în celulă se stochează o listă cu toate elementele cu acel index, iar căutarea se face în acea listă.

Exemplu în Dart (Flutter):

void main() {
  Map<String, int> hashTable = {};
  hashTable['apple'] = 5;
  hashTable['banana'] = 3;

  print(hashTable['apple']); // 5
}

Aici, Map este o implementare a unei tabele de dispersie, unde cheia este un șir de caractere, iar valoarea este un număr.