Hash Tables

Cos’è una Hash Table

Una hash table (tabella hash) è una struttura dati che permette di memorizzare e recuperare coppie chiave-valore in modo estremamente efficiente. In JavaScript, gli oggetti sono implementati come hash table.

Concetto fondamentale: invece di cercare un elemento scansionando tutta la struttura, una hash table usa una funzione hash per calcolare direttamente la posizione in memoria dove memorizzare o cercare un elemento.

1
// Esempio: inventario di un negozio di ferramenta
2
// Chiave: "nails" → Valore: 1000
3
// La funzione hash calcola l'indirizzo dove memorizzare questa coppia

Come funziona una Hash Table

Struttura base

Una hash table è composta da:

• Array di indirizzi: spazio di memoria (array) dove vengono memorizzati gli elementi
• Funzione hash: calcola l’indirizzo basandosi sulla chiave
• Coppie chiave-valore: i dati memorizzati nella tabella

1
// Rappresentazione grafica
2
// Array di indirizzi: [0] [1] [2] [3] [4] [5] [6]
3
//
4
// set("nails", 1000) → hash("nails") = 2 → memorizza a indirizzo [2]
5
// set("screws", 800) → hash("screws") = 6 → memorizza a indirizzo [6]

Processo di inserimento

1. Input: chiave e valore (es. "nails" e 1000)
2. Hash: solo la chiave viene processata dalla funzione hash
3. Calcolo indirizzo: la funzione hash produce un numero (es. 2)
4. Memorizzazione: la coppia [chiave, valore] viene memorizzata all’indirizzo calcolato

Processo di ricerca

1. Input: chiave da cercare (es. "nails")
2. Hash: la chiave viene processata dalla stessa funzione hash
3. Calcolo indirizzo: produce lo stesso numero (es. 2)
4. Accesso diretto: vai direttamente all’indirizzo calcolato per recuperare il valore

Vantaggio: l’accesso è O(1) invece di O(n) come nelle linked lists o array non ordinati.

Funzione Hash

Caratteristiche fondamentali

Le funzioni hash hanno due caratteristiche essenziali:

1. One-way (unidirezionale):

   • Se hash("nails") produce 2, non puoi invertire il processo
   • Non puoi prendere 2 e ottenere "nails"
   • La funzione hash è unidirezionale

2. Deterministic (deterministica):

   • Se hash("nails") produce 2 una volta, produrrà sempre 2
   • La stessa chiave produce sempre lo stesso indirizzo
   • Questo permette di trovare gli elementi in modo consistente

Come funziona

La funzione hash prende una stringa e la converte in un numero usando:

• Valori ASCII: ogni carattere ha un valore numerico
• Equazione matematica: combina i valori ASCII con operazioni matematiche
• Modulo: garantisce che il risultato sia nell’intervallo valido (0 a size-1)

1
// Esempio semplificato
2
// "nails" → valori ASCII: n=110, a=97, i=105, l=108, s=115
3
// Equazione: (valori combinati * 23) % 7
4
// Risultato: un numero tra 0 e 6

Collisioni

Cos’è una collisione

Una collisione si verifica quando due chiavi diverse producono lo stesso indirizzo hash.

1
// Esempio
2
hash("nails") = 2
3
hash("bolts") = 2  // Collisione! Stesso indirizzo

Metodi per gestire le collisioni

Esistono diversi approcci per gestire le collisioni:

1. Separate Chaining (concatenamento separato)

Gli elementi che collidono vengono memorizzati in una struttura dati (array o linked list) nello stesso indirizzo.

1
// Indirizzo 2 contiene un array con più coppie chiave-valore
2
[2] = [["nails", 1000], ["bolts", 500]]

Vantaggi:

• Semplice da implementare
• Non richiede riallocazione quando l’array si riempie
• Permette di memorizzare tutti gli elementi che collidono

Svantaggi:

• Richiede memoria extra per le strutture ausiliarie
• In caso di molte collisioni, la ricerca diventa O(n) invece di O(1)

2. Linear Probing (sondaggio lineare)

Se un indirizzo è occupato, cerca il prossimo indirizzo libero.

1
// hash("nails") = 2 → occupato
2
// Prova indirizzo 3 → occupato
3
// Prova indirizzo 4 → libero, inserisci qui

Vantaggi:

• Utilizza solo l’array principale
• Nessuna struttura ausiliaria necessaria

Svantaggi:

• Può creare “cluster” di elementi
• La ricerca può richiedere più passaggi
• Rimozione più complessa

Nota: in questo documento useremo separate chaining con array per la nostra implementazione.

Implementazione

Classe HashTable

Iniziamo creando la classe base per la hash table:

1
class HashTable {
2
  constructor(size = 7) {
3
    // Crea un array vuoto di dimensione specificata
4
    // Se non viene passata una dimensione, usa 7 (numero primo)
5
    this.dataMap = new Array(size);
6
  }
7
}

Perché 7?: Usare un numero primo come dimensione dell’array aiuta a distribuire meglio gli elementi, riducendo le collisioni.

Funzione Hash

La funzione hash è un metodo privato (indicato dall’underscore _) che calcola l’indirizzo per una chiave:

1
_hash(key) {
2
  // Variabile per accumulare il valore hash
3
  let hash = 0;
4

5
  // Itera attraverso ogni carattere della chiave
6
  for (let i = 0; i < key.length; i++) {
7
    // Calcola: hash corrente + (valore ASCII del carattere * 23) % dimensione array
8
    // 23 è un numero primo che aiuta la randomizzazione
9
    hash = (hash + key.charCodeAt(i) * 23) % this.dataMap.length;
10
  }
11

12
  // Ritorna un numero tra 0 e (dimensione - 1)
13
  return hash;
14
}

Spiegazione dettagliata:

• key.charCodeAt(i): ottiene il valore ASCII del carattere alla posizione i
• * 23: moltiplica per un numero primo per aumentare la randomizzazione
• % this.dataMap.length: usa il modulo per garantire che il risultato sia nell’intervallo valido
• Il risultato è sempre un numero tra 0 e size - 1

Set - Inserire una coppia chiave-valore

Il metodo set inserisce una nuova coppia chiave-valore nella hash table:

1
set(key, value) {
2
  // 1. Calcola l'indirizzo usando la funzione hash
3
  let index = this._hash(key);
4

5
  // 2. Se l'indirizzo è vuoto, crea un array vuoto
6
  // Questo è necessario per gestire le collisioni con separate chaining
7
  if (!this.dataMap[index]) {
8
    this.dataMap[index] = [];
9
  }
10

11
  // 3. Aggiungi la coppia [chiave, valore] all'array all'indirizzo calcolato
12
  this.dataMap[index].push([key, value]);
13

14
  // 4. Ritorna l'istanza per permettere il method chaining
15
  return this;
16
}

Edge cases gestiti:

• Indirizzo vuoto: crea un nuovo array
• Collisione: aggiunge la nuova coppia all’array esistente
• Duplicati: vengono aggiunti come nuove entry (per aggiornare un valore esistente, serve logica aggiuntiva)

Esempio di utilizzo:

1
const myHashTable = new HashTable();
2
myHashTable.set("nails", 1000);
3
myHashTable.set("bolts", 500);
4
// Se hash("bolts") = hash("nails"), entrambi saranno nell'array all'indirizzo calcolato

Get - Recuperare un valore

Il metodo get recupera il valore associato a una chiave:

1
get(key) {
2
  // 1. Calcola l'indirizzo usando la funzione hash
3
  let index = this._hash(key);
4

5
  // 2. Verifica se esiste qualcosa all'indirizzo calcolato
6
  if (this.dataMap[index]) {
7
    // 3. Itera attraverso l'array all'indirizzo (gestisce collisioni)
8
    for (let i = 0; i < this.dataMap[index].length; i++) {
9
      // 4. Se la chiave corrisponde, ritorna il valore
10
      // dataMap[index][i][0] è la chiave, [1] è il valore
11
      if (this.dataMap[index][i][0] === key) {
12
        return this.dataMap[index][i][1];
13
      }
14
    }
15
  }
16

17
  // 5. Se la chiave non è stata trovata, ritorna undefined
18
  return undefined;
19
}

Logica:

• Se non c’è nulla all’indirizzo → la chiave non esiste
• Se c’è un array → itera per trovare la chiave corretta (gestisce collisioni)
• Ritorna il valore se trovato, altrimenti undefined

Keys - Ottenere tutte le chiavi

Il metodo keys ritorna un array con tutte le chiavi presenti nella hash table:

1
keys() {
2
  // 1. Array per memorizzare tutte le chiavi
3
  let allKeys = [];
4

5
  // 2. Itera attraverso tutti gli indirizzi dell'array
6
  for (let i = 0; i < this.dataMap.length; i++) {
7
    // 3. Se c'è qualcosa all'indirizzo corrente
8
    if (this.dataMap[i]) {
9
      // 4. Itera attraverso l'array all'indirizzo (gestisce collisioni)
10
      for (let j = 0; j < this.dataMap[i].length; j++) {
11
        // 5. Aggiungi la chiave all'array delle chiavi
12
        // dataMap[i][j][0] è la chiave
13
        allKeys.push(this.dataMap[i][j][0]);
14
      }
15
    }
16
  }
17

18
  // 6. Ritorna l'array con tutte le chiavi
19
  return allKeys;
20
}

Pattern: doppio loop annidato per attraversare tutti gli elementi, incluso quelli che hanno colliso.

Implementazione completa

Ecco il codice completo della classe HashTable:

1
class HashTable {
2
  constructor(size = 7) {
3
    this.dataMap = new Array(size);
4
  }
5

6
  _hash(key) {
7
    let hash = 0;
8
    for (let i = 0; i < key.length; i++) {
9
      hash = (hash + key.charCodeAt(i) * 23) % this.dataMap.length;
10
    }
11
    return hash;
12
  }
13

14
  set(key, value) {
15
    let index = this._hash(key);
16
    if (!this.dataMap[index]) {
17
      this.dataMap[index] = [];
18
    }
19
    this.dataMap[index].push([key, value]);
20
    return this;
21
  }
22

23
  get(key) {
24
    let index = this._hash(key);
25
    if (this.dataMap[index]) {
26
      for (let i = 0; i < this.dataMap[index].length; i++) {
27
        if (this.dataMap[index][i][0] === key) {
28
          return this.dataMap[index][i][1];
29
        }
30
      }
31
    }
32
    return undefined;
33
  }
34

35
  keys() {
36
    let allKeys = [];
37
    for (let i = 0; i < this.dataMap.length; i++) {
38
      if (this.dataMap[i]) {
39
        for (let j = 0; j < this.dataMap[i].length; j++) {
40
          allKeys.push(this.dataMap[i][j][0]);
41
        }
42
      }
43
    }
44
    return allKeys;
45
  }
46
}

Complessità Big O

Analisi delle operazioni

Caso peggiore

Nel caso peggiore, tutte le chiavi collidono nello stesso indirizzo:

• L’array a quell’indirizzo diventa molto lungo
• get e set diventano O(n) perché devono iterare attraverso l’array

Tuttavia, con una buona funzione hash e una dimensione appropriata:

• Le collisioni sono rare
• La distribuzione è uniforme
• Le operazioni rimangono O(1) nella pratica

Confronto con altre strutture

Vantaggio principale: le hash table permettono accesso rapido ai dati tramite chiave, senza dover scansionare tutta la struttura.

Quando usare Hash Tables

Usa una Hash Table quando:

• Devi accedere frequentemente a elementi per chiave: lookup O(1) vs O(n) di array/linked list
• Hai bisogno di memorizzare coppie chiave-valore: inventari, dizionari, cache
• Vuoi evitare duplicati: puoi verificare l’esistenza di una chiave in O(1)
• Lavori con dati non ordinati: non hai bisogno di mantenere un ordine specifico

Non usare una Hash Table quando:

• Hai bisogno di mantenere un ordine: le hash table non preservano l’ordine di inserimento
• Devi iterare in ordine: non puoi iterare in modo ordinato
• Lo spazio è limitato: le hash table possono avere overhead di memoria
• Le collisioni sono frequenti: se la funzione hash non distribuisce bene, le prestazioni peggiorano

Hash Tables in JavaScript

In JavaScript, ci sono due modi principali per usare hash tables:

1. Oggetti (Objects)

1
const inventory = {};
2
inventory["nails"] = 1000;
3
inventory["bolts"] = 500;
4

5
// Accesso
6
console.log(inventory["nails"]); // 1000

Caratteristiche:

• Chiavi devono essere stringhe (o convertite in stringhe)
• Prototipo con proprietà ereditate
• Non mantiene l’ordine di inserimento (in versioni vecchie di JS)

2. Map

1
const inventory = new Map();
2
inventory.set("nails", 1000);
3
inventory.set("bolts", 500);
4

5
// Accesso
6
console.log(inventory.get("nails")); // 1000

Caratteristiche:

• Chiavi possono essere di qualsiasi tipo
• Nessun prototipo, solo le chiavi che aggiungi
• Mantiene l’ordine di inserimento
• Metodi dedicati: set(), get(), has(), delete()

Quando usare Map vs Object:

• Usa Map quando le chiavi non sono stringhe o quando vuoi garantire l’ordine
• Usa Object per semplicità e quando le chiavi sono sempre stringhe

Esercizi e problemi comuni

Per praticare e approfondire le hash tables, consulta la sezione dedicata agli esercizi e problemi comuni