Ce este un tabel hash?

O masă hash, sau matrice asociativă, este o structură de date care implementează interfața de matrice asociativă, adică leagă cheile de valori. Folosește o funcție hash pentru a calcula un indice, sau "hash", al coșului sau slotului unde ar trebui să se afle valoarea căutată.

Componente principale:

• Cheie: Identificator unic al elementului.
• Valoare: Datele asociate cheii.
• Funcție hash: Transformă cheia într-o valoare numerică (hash), utilizată pentru a determina indicele coșului.
• Coșuri (Buckets): Array în care sunt stocate perechi cheie-valoare.
• Gestionarea coliziunilor: Mecanism pentru rezolvarea situațiilor în care diferite chei generează același hash (și, prin urmare, indică același coș). Metode comune:
  • Împletire: Fiecare coș conține o listă (de exemplu, listă înlănțuită) de elemente ale căror hash-uri indică spre acel coș.
  • Adresare deschisă: În cazul unei coliziuni, se caută următorul coș liber folosind algoritmi precum hashing liniar, pătratic sau hashing dublu.

Principiul de funcționare:

1. Inserare: Funcția hash se aplică cheii pentru a obține hash-ul. Hash-ul este folosit pentru a determina indicele coșului. Perechea cheie-valoare este stocată în acest coș. În cazul unei coliziuni, se aplică metoda de gestionare a coliziunilor.

   // Exemplu de inserare într-o masă hash (împletire)
   function insert(key, value) {
     const hash = hashFunction(key); // Calculăm hash-ul
     const bucketIndex = hash % tableSize; // Determinăm indicele coșului
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Creăm lista dacă nu există
     }
     buckets[bucketIndex].push({ key, value }); // Adăugăm perechea în listă
   }
   

2. Căutare: Funcția hash se aplică cheii pentru a obține hash-ul. Hash-ul este folosit pentru a determina indicele coșului. Apoi, în acest coș, se caută elementul cu cheia dată. În metoda de împletire, se caută în lista din interiorul coșului. În adresarea deschisă, se verifică succesiv alte coșuri până se găsește elementul sau se stabilește că nu există.

   // Exemplu de căutare într-o masă hash (împletire)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Calculăm hash-ul
     const bucketIndex = hash % tableSize; // Determinăm indicele coșului
   
     if (buckets[bucketIndex]) {
       // Căutăm elementul în lista coșului
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Dacă este necesar să ștergeți
           return value; // Returnăm valoarea
         }
       }
     }
     return undefined; // Elementul nu a fost găsit
   }
   

Avantaje:

• Operații rapide de inserare, căutare și ștergere în medie (O(1)).
• Utilizare eficientă a memoriei comparativ cu un array de adresare directă (dacă cheile sunt dispersate).

Dezavantaje:

• Performanța poate scădea în cazul multor coliziuni (cel mai rău caz O(n)).
• Ordinea elementelor inserate nu este păstrată.
• Este necesară o funcție hash bună pentru distribuție uniformă a cheilor.

În JavaScript, tabelele hash sunt implementate prin obiectul încorporat Map și, din punct de vedere istoric, Object. Map este preferat deoarece permite utilizarea oricărui tip de date ca cheie și păstrează ordinea adăugării elementelor. Object convertește toate cheile în șiruri.