Cos'è una tabella hash?

Una tabella hash (o array associativo, dizionario) è una struttura dati che implementa l’interfaccia di un array associativo, cioè permette di memorizzare coppie "chiave-valore" e di eseguire ricerche rapide del valore tramite la chiave.

Il principio di funzionamento si basa sull’uso di una funzione hash, che trasforma la chiave in un indice (hash) all’interno dell’array (o bucket).

Operazioni principali:

1. Inserimento: Si calcola l’hash della chiave, e la coppia "chiave-valore" viene inserita nel bucket corrispondente.
2. Cancellazione: Si calcola l’hash della chiave, si trova il bucket corrispondente, e la coppia viene rimossa.
3. Ricerca: Si calcola l’hash della chiave, si trova il bucket corrispondente, e si cerca la coppia con la chiave desiderata.

Le tabelle hash offrono in media alte prestazioni per le operazioni di inserimento, cancellazione e ricerca (idealmente $O(1)$). Tuttavia, nel caso peggiore (quando ci sono molte collisioni, cioè chiavi diverse che si trasformano nello stesso indice), le prestazioni possono scendere a $O(n)$.

Esistono diverse strategie per risolvere le collisioni:

• Metodo di chaining (Separate Chaining): In ogni bucket si memorizza una lista (ad esempio, una lista collegata) di elementi con lo stesso hash.
• Addressing aperto (Open Addressing): Quando si verifica una collisione, la ricerca di uno spazio libero avviene tramite un algoritmo predefinito (sondaggio lineare, quadratico, ecc.).

Esempio concettuale (semplificato):

// Esempio di funzione hash semplificata
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Trasformazione in 32-bit
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Metodo di chaining
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Verifica se la chiave esiste già per aggiornare il valore
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Chiave non trovata
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Eliminato con successo
      }
    }
    return false; // Chiave non trovata
  }
}

// Uso
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

In JavaScript, oggetti ({}) e mappe (Map) sono esempi di implementazioni di tabelle hash. Map è spesso preferito perché supporta chiavi di qualsiasi tipo e mantiene l’ordine di inserimento.

Proprietà di una buona funzione hash:

• Calcolo rapido.
• Distribuzione uniforme degli hash per chiavi diverse.
• Minimize collisioni.