Mappe e dizionari

Una mappa/dizionario è una collezione di entry (chiave, valore) che supporta ricerca, inserimento e rimozione per chiave. L'ADT ha varianti secondo due scelte: chiavi distinte o no, universo delle chiavi totalmente ordinato o no.

Nel testo adottato dizionario $\equiv$ multimap. Le strutture studiate sono: tabelle hash per mappe non necessariamente ordinate (vedi Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →); alberi binari di ricerca, multi-way search tree e alberi (2,4) per mappe e dizionari ordinati (vedi Alberi binari di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca →, Multi-way search tree e alberi (2,4)Multi-way search tree (nodi con più entry, d figli e d-1 chiavi ordinate), ricerca in O(d_max h), un MWS tree con n entry ha n+1 foglie; albero (2,4): nodi con 2-4 figli e tutte le foglie alla stessa profondità, altezza Theta(log n) con dimostrazione, operazioni in Theta(log n); idea di overflow e underflow; tabella di confronto con gli alberi binari di ricerca.Multi-way search tree e alberi (2,4) →).

Applicazioni

• Database (anagrafica degli studenti): chiave = matricola, valore = informazioni dello studente.
• Compilatori, controllo dei tipi: chiave = nome della variabile, valore = tipo.
• Motori di ricerca: chiave = parola, valore = lista dei documenti che la contengono (lista invertita).
• Conteggio di frequenze: chiave = oggetto, valore = conteggio (ad esempio nell'analisi di sequenze biologiche, con oggetto = $k$-mer, sequenza di $k$ caratteri).

L'ADT mappa

Mappa: entry con chiavi distinte provenienti da un dominio su cui è definito =; concetto analogo a un indice (associative array: la chiave è l'indice di accesso).

Con get(k) che restituisce null per "assente", un valore null non è distinguibile da una chiave mancante: per questo di solito si vietano valori null.

Implementazioni semplici ma poco efficienti

1. Lista (doppiamente) concatenata non ordinata: get, put, remove richiedono la ricerca lineare della chiave, $\Theta(n)$ al caso pessimo (la mappa non ha ordine, quindi non si può fare di meglio).
2. Array di taglia $\lvert U \rvert$: se le chiavi sono interi nell'intervallo $[0, \lvert U \rvert - 1]$ si usa la chiave come indice e le tre operazioni costano $\Theta(1)$. Ma lo spazio è $\Theta(\lvert U \rvert)$, spesso sproporzionato: il codice fiscale ha $16$ caratteri (nove lettere e sette cifre, quindi circa $26^9 \cdot 10^7 \approx 5 \cdot 10^{19}$ chiavi possibili) contro qualche milione di cittadini; inoltre servirebbe una corrispondenza chiave $\to$ intero calcolabile in tempo costante.

La tabella hash nasce per tenere il tempo costante senza lo spazio proporzionale a $\lvert U \rvert$.

Dizionario (multimap)

Ammette più entry con la stessa chiave. Metodi caratteristici:

• get(k): restituisce una collezione (anche vuota) con tutti i valori associati a $k$;
• put(k, x): inserisce sempre una nuova entry $(k, x)$, senza toccare le altre con la stessa chiave; non restituisce nulla;
• remove(k, v): toglie una entry con chiave $k$ e valore $v$, se esiste; non restituisce nulla.

Implementazione con una mappa: le entry sono $(k, L_k)$ con $L_k$ collezione non vuota dei valori di $k$ (una doppia lista); $(k, L_k)$ rappresenta in modo compatto le $\ell = \lvert L_k \rvert$ entry $(k, v_1), \dots, (k, v_\ell)$. get e put costano come nella mappa (si aggiunge $v$ a $L_k$ se la entry esiste, altrimenti si crea con il solo $v$); remove(k, v) costa come nella mappa più un termine $s = \lvert L_k \rvert$ per cercare $v$ in $L_k$; se $L_k$ resta vuota si toglie la entry dalla mappa. In alternativa si modificano alberi di ricerca e alberi (2,4) per ammettere chiavi uguali.

Errori comuni

• Confondere mappa (chiavi distinte, put sostituisce) e dizionario (put aggiunge sempre).
• Usare una struttura che richiede l'ordine (albero di ricerca) per chiavi senza ordine totale.
• Dimenticare che put restituisce il vecchio valore.