Tabelle hash

Con 47 memorizzato in una tabella di 7 bucket, il computer va dritto al bucket 47 mod 7 = 5 invece di cercare in tutta la tabella.

Trasformare una chiave in una posizione

Finora trovare un valore voleva dire cercare: fino a n passi in un array non ordinato o in una lista concatenata. Gli array, però, raggiungono qualsiasi posizione in un passo. E se fosse la chiave stessa a indicare la posizione? Se le chiavi fossero piccoli numeri interi, per esempio numeri di matricola da 0 a 99, potresti tenere un array di 100 celle e mettere lo studente k nella cella k. Gli appunti del MIT lo chiamano direct access array (array ad accesso diretto). Non funziona quando le chiavi possibili sono enormi, come numeri di telefono o parole, perché non puoi permetterti una cella per ogni chiave possibile.

Una funzione hash risolve il problema comprimendo qualsiasi chiave in un piccolo intervallo di posizioni, da 0 a m − 1. Una semplice per i numeri interi è h(k) = k mod m, il resto della divisione per m. L'array di m celle è la tabella hash, e le sue celle sono spesso chiamate bucket. Per memorizzare 47 con m = 7, calcola 47 mod 7 = 5 e mettilo nel bucket 5. Per ritrovare 47 più tardi, fai lo stesso calcolo e guarda solo nel bucket 5.

Collisioni e concatenamento

C'è un problema. Con 7 bucket e più di 7 chiavi possibili, alcune chiavi devono condividere un bucket: 12, 33 e 47 danno tutte resto 5. Si chiama collisione, e gli appunti del MIT fanno notare che non si può evitare, per il principio dei cassetti. Il rimedio solito è il concatenamento (chaining): ogni bucket contiene una piccola lista, una catena, di tutte le chiavi finite lì. Trovare 47 costa allora 1 passo per l'hash più un confronto per ogni chiave controllata nella catena 5. Se 12 e 33 sono davanti, fa 1 + 3 = 4 passi.

Quanto sono lunghe le catene? Se le chiavi si distribuiscono in modo uniforme, ogni catena contiene circa n/m chiavi, un numero chiamato fattore di carico. Tieni m grande più o meno quanto n e le catene restano corte, così trovare, inserire ed eliminare richiedono in media un numero costante di passi. Il pericolo è una cattiva distribuzione. Se tutte le chiavi finiscono nello stesso bucket, una sola catena contiene tutte le n chiavi e la tabella non è migliore di una lista concatenata. Nel laboratorio imposta 7 bucket e inserisci 14, 21 e 28: finiscono tutte nel bucket 0.

Le tabelle hash in JavaScript

Raramente scrivi da solo una tabella hash, perché JavaScript ha Map e Set. La specifica ECMAScript dice che devono essere «implementati usando tabelle hash o altri meccanismi che, in media, forniscano tempi di accesso sublineari rispetto al numero di elementi». In altre parole, map.get(key) e set.has(x) devono essere più veloci che cercare in tutta la collezione. MDN aggiunge che una Map conserva le chiavi nell'ordine di inserimento e, a differenza di un oggetto semplice, non contiene chiavi predefinite che potrebbero scontrarsi con le tue.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, nessuna ricerca nella lista
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true