Qual è il principio di funzionamento di una tabella hash?

La tabella hash (o array associativo) memorizza coppie "chiave-valore". Il principio di funzionamento si basa sull'uso di una funzione hash, che trasforma la chiave in un indice numerico (hash), indicando il luogo di memorizzazione del valore nell'array (cestino).

Passaggi:

1. Calcolo dell'hash: Per una chiave data, si calcola l'hash.

   <?php
   $key = "example";
   $hash = crc32($key); // Esempio di funzione hash semplice
   

2. Determinazione dell'indice: L'hash viene trasformato in un indice dell'array, di solito usando l'operazione modulo della dimensione dell'array.

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

3. Accesso al cestino: Si accede al cestino corrispondente nell'array usando l'indice calcolato.
4. Risoluzione delle collisioni: Poiché chiavi diverse possono avere lo stesso hash (collisione), il cestino può contenere più coppie "chiave-valore". Per risolvere le collisioni, si usano metodi diversi:
   • Metodo di chaining (separate chaining): Ogni cestino memorizza una lista (ad esempio, una lista collegata) di coppie "chiave-valore" i cui hash coincidono.
   • Metodo di indirizzamento aperto (open addressing): In caso di collisione, si effettua una ricerca ripetuta di una cella libera nell'array secondo una regola determinata (sondaggio lineare, quadratico, doppio hashing).

Operazioni:

• Inserimento: Si calcola l'hash della chiave, si determina l'indice, e la coppia "chiave-valore" viene inserita nel cestino corrispondente. In caso di collisione, si aggiunge alla lista (chaining) o si cerca un posto libero (indirizzamento aperto).
• Ricerca: Si calcola l'hash della chiave, si determina l'indice. Nel cestino corrispondente, si cerca il valore tramite la chiave. Nel metodo di chaining, si percorrono gli elementi della lista; nell'indirizzamento aperto, si effettua una ricerca sequenziale.
• Cancellazione: Si calcola l'hash della chiave, si determina l'indice. Nel cestino corrispondente, si trova e si elimina la coppia tramite la chiave.

Vantaggi:

• Accesso rapido agli elementi (in media O(1)).
• Uso efficiente della memoria.

Svantaggi:

• La performance può peggiorare con un grande numero di collisioni.
• La dimensione della tabella può richiedere una regolazione (rehashing) per mantenere l'efficienza.