Cos'è una tabella hash?

Una tabella hash, o array associativo, è una struttura dati che implementa l'interfaccia di array associativo, cioè collega chiavi a valori. Utilizza una funzione hash per calcolare un indice, o "hash", della casella o slot dove deve trovarsi il valore cercato.

Componenti principali:

• Chiave: Identificatore univoco dell'elemento.
• Valore: Dati associati alla chiave.
• Funzione hash: Trasforma la chiave in un valore numerico (hash), usato per determinare l'indice della casella.
• Caselle (Buckets): Array in cui vengono memorizzate coppie chiave-valore.
• Gestione delle collisioni: Meccanismo per risolvere situazioni in cui chiavi diverse producono lo stesso hash (e quindi puntano alla stessa casella). Metodi comuni:
  • Chaining: Ogni casella memorizza una lista (ad esempio, lista collegata) di elementi i cui hash puntano a quella casella.
  • Indirizzamento aperto: In caso di collisione, si cerca la casella successiva libera usando algoritmi come hashing lineare, quadratico o doppio hashing.

Principio di funzionamento:

1. Inserimento: La funzione hash viene applicata alla chiave per ottenere l'hash. L'hash viene usato per determinare l'indice della casella. La coppia chiave-valore viene memorizzata in questa casella. In caso di collisione, si applica il metodo di gestione delle collisioni.

   // Esempio di inserimento in una tabella hash (chaining)
   function insert(key, value) {
     const hash = hashFunction(key); // Calcola l'hash
     const bucketIndex = hash % tableSize; // Determina l'indice della casella
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Crea la lista se non esiste
     }
     buckets[bucketIndex].push({ key, value }); // Aggiungi coppia alla lista
   }
   

2. Ricerca: La funzione hash viene applicata alla chiave per ottenere l'hash. L'hash viene usato per determinare l'indice della casella. Poi, in questa casella, si cerca l'elemento con la chiave data. Con il metodo di chaining, si cerca nella lista all'interno della casella. Con l'indirizzamento aperto, si verificano successivamente altre caselle finché non si trova l'elemento o si determina che non esiste.

   // Esempio di ricerca in una tabella hash (chaining)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Calcola l'hash
     const bucketIndex = hash % tableSize; // Determina l'indice della casella
   
     if (buckets[bucketIndex]) {
       // Cerca elemento nella lista della casella
       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); // Se necessario rimuovere
           return value; // Restituisce il valore
         }
       }
     }
     return undefined; // Elemento non trovato
   }
   

Vantaggi:

• Operazioni di inserimento, ricerca e cancellazione rapide in media (O(1)).
• Uso efficiente della memoria rispetto a un array di indirizzi diretti (se le chiavi sono distribuite in modo sparso).

Svantaggi:

• La performance può diminuire in caso di molte collisioni (nel peggiore dei casi O(n)).
• L'ordine di inserimento degli elementi non viene mantenuto.
• È necessaria una buona funzione hash per una distribuzione uniforme delle chiavi.

In JavaScript, le tabelle hash sono implementate tramite l'oggetto incorporato Map e storicamente Object. Map è preferibile poiché permette di usare qualsiasi tipo di dato come chiave e mantiene l'ordine di inserimento. Object converte tutte le chiavi in stringhe.