Mappe e dizionari

Una mappa/dizionario è una collezione di entry (chiave, valore) che supporta ricerca, inserimento e rimozione per chiave. In Python è il tipo dict (Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →); qui si studia come è fatto dentro. La corrispondenza con l'ADT di questa nota (Tipi di dato astrattiUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti →) è: d[k] = v $\leftrightarrow$ put(k, v), d.get(k) $\leftrightarrow$ get(k), del d[k] $\leftrightarrow$ remove(k), d.keys(), d.values(), d.items() $\leftrightarrow$ keySet(), values(), entrySet(). 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

Definizione (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).

Metodo	Effetto
get(k)	se esiste $(k, x)$ restituisce $x$, altrimenti null
put(k, v)	se esiste $(k, x)$ lo sostituisce con $v$ e restituisce $x$; altrimenti inserisce $(k, v)$ e restituisce null
remove(k)	se esiste $(k, x)$ lo toglie e restituisce $x$, altrimenti null
keySet(), values(), entrySet()	iteratori sulle chiavi, sui valori, sulle entry

Esempio. Su una mappa vuota: put("a", 1) restituisce null, poi put("a", 2) restituisce 1, get("a") restituisce 2 e remove("a") restituisce 2.

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: è la ricerca lineare di Ricerca lineare e binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria →; sapendo l'ordine delle chiavi si potrebbe usare la ricerca binaria, ma non su una lista concatenata, dove l'accesso al nodo $i$ costa $\Theta(i)$, vedi Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →).
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 ($5\cdot10^{19}$ celle di memoria sono molto più di qualunque memoria disponibile, vedi Memoria principale a semiconduttoreCella di memoria e operazioni; RAM dinamica (condensatore, refresh) e statica (flip-flop), confronto; ROM, PROM, EPROM, EEPROM e flash; organizzazione dei chip e dei moduli con calcolo di linee di indirizzo e numero di chip; DRAM sincrona e DDR; errori e codici di correzione.Memoria principale a semiconduttore →); inoltre servirebbe una corrispondenza chiave $\to$ intero calcolabile in tempo costante. Il calcolo: ciascuna delle $9$ posizioni di lettera ha $26$ valori e ciascuna delle $7$ posizioni di cifra ne ha $10$, quindi le combinazioni sono $26^9\cdot10^7$ (principio moltiplicativo del calcolo combinatorioNegli spazi uniformi bisogna contare: principio di moltiplicazione, disposizioni con ripetizione n^k, disposizioni semplici n!/(n−k)!, permutazioni n!, combinazioni (n su k); estrazioni con e senza reinserimento e distribuzione ipergeometrica.Calcolo combinatorio per la probabilità →).

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

Dizionario (multimap)

Definizione (dizionario o 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.

Esempio. Dopo put(k, 1) e put(k, 2), get(k) restituisce la collezione $\{1,2\}$; remove(k, 1) lascia $\{2\}$.

Traccia dell'implementazione con una mappa di liste, partendo da una mappa vuota:

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.