Care este principiul de funcționare al unui tabel hash?

O tabel hash (sau matrice asociativă) stochează perechi "cheie-valoare". Principiul de funcționare se bazează pe utilizarea unei funcții hash, care transformă cheia într-un indice numeric (hash), indicând locul de stocare a valorii în matrice (coș).

Pași:

1. Calcularea hash-ului: Pentru o cheie dată, se calculează hash-ul.

   <?php
   $key = "example";
   $hash = crc32($key); // Exemplu de funcție hash simplă
   

2. Determinarea indicelui: Hash-ul este transformat într-un indice al matricei, de obicei folosind operația modulo a dimensiunii matricei.

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Accesul la coș: Se accesează coșul corespunzător în matrice folosind indicele calculat.
4. Rezolvarea coliziunilor: Deoarece diferite chei pot avea același hash (coliziune), coșul poate conține mai multe perechi "cheie-valoare". Pentru rezolvarea coliziunilor, se folosesc diferite metode:
   • Metoda lanțurilor (Separate Chaining): În fiecare coș se păstrează o listă (de exemplu, o listă legată) de perechi "cheie-valoare" ale căror hash-uri coincid.
   • Metoda adresării deschise (Open Addressing): În cazul coliziunii, se face o căutare repetată a unei celule libere în matrice conform unei reguli determinate (sondare liniară, pătratică, dublu hash).

Operații:

• Inserție: Se calculează hash-ul cheii, se determină indicele, și perechea "cheie-valoare" se plasează în coșul corespunzător. În cazul coliziunii, se adaugă în listă (lanțuri) sau se caută un loc liber (adresare deschisă).
• Căutare: Se calculează hash-ul cheii, se determină indicele. În coșul corespunzător, se caută valoarea după cheie. În metoda lanțurilor, se parcurg elementele listei; în adresarea deschisă, se face o căutare secvențială.
• Ștergere: Se calculează hash-ul cheii, se determină indicele. În coșul corespunzător, se găsește și se șterge perechea după cheie.

Avantaje:

• Acces rapid la elemente (în medie O(1)).
• Utilizare eficientă a memoriei.

Dezavantaje:

• Performanța poate scădea odată cu creșterea numărului de coliziuni.
• Dimensiunea tabelului poate necesita ajustare (rehashing) pentru menținerea eficienței.