Il TDA Map

Tabelle hash

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 2

Definizione informale

Il TDA Map memorizza coppie formate da una chiave k e da un valore v – La coppia è chiamata entry

Ogni chiave deve essere unica– Questa è la differenza principale con i

DictionarySia la chiave sia il valore sono degli oggetti generici

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 3

I metodi del TDA Map – 1size()isEmpty()get(k)– Se esiste un entry con chiave k, restituisce il valore

associato a k, altrimenti restituisce nullput(k, v)– Se la mappa non ha un entry con chiave uguale a k,

allora aggiunge l’entry (k,v) alla mappa; altrimenti, rimpiazza con v il valore esistente associato alla chiave k e restituisce il vecchio valore

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 4

I metodi del TDA Map – 2remove(k)– Cancella dalla mappa l’entry con chiave uguale a

k e restituisce il valore associato a k; se la mappa non ha tale entry, viene restituito il valore null

keys()– Restituisce un iteratore su tutte le chiavi della

mappavalues()– Restituisce un iteratore su tutte i valori associati

alle chiavi della mappa

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 5

NO_SUCH_KEY

Questa volta non utilizziamo l’elemento speciale NO_SUCH_KEY per indicare che non esiste un entry con la chiave passata al metodo, ma utilizziamo la sentinella nullIl codice da scrivere in questo caso è più sempliceL’unico svantaggio è che non possiamo avere nella mappa un entry (k,null)Avremmo potuto gestire un’eccezione, ma è più lento che eseguire un test su di una sentinella

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 6

Interfaccia Map – 1public interface Map {// Restituisce il numero degli elementi nella mappapublic int size();

// Restituisce true se la mappa è vuotapublic boolean isEmpty();

// Inserisce una coppia chiave-valore nella mappa, // rimpiazzando il precedente se esistepublic Object put(Object key, Object value)

throws InvalidKeyException;

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 7

Interfaccia Map – 2//Restituisce il valore associato alla chiave keypublic Object get(Object key) throws InvalidKeyException;

// Rimuove la coppia chiave-valore specificata da keypublic Object remove(Object key)

throws InvalidKeyException;

// Restituisce un iteratore su tutte le chiavi della mappapublic Iterator keys();

// Restituisce un iteratore su tutte i valori della mappapublic Iterator values();

}

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 8

Note per l’implementazione

Una entry della mappa viene rappresentata dalla classe Entry– È la stessa classe usata per il TDA Dictionary

Per confrontare le chiavi usiamo un oggetto che supporta l’operazione isEqual(k1,k2) (equality tester) I metodi presenti nell’interfaccia Map devono lanciare l’eccezione InvalidKeyException se la chiave specificata non una chiave valida per il contenitore in esame

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 9

Funzione checkKeyCosì come abbiamo fatto per l’implementazione del TDA Dictionary, anche per l’implementazione di Mapabbiamo la funzione checkKey

private void checkKey(Object key) {if (!_cmp.isComparable(key))throw new InvalidKeyException(

" Chiave non confrontabile "); }

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 10

EqualityTester

public interface EqualityTester {

boolean isEqualTo(Object x, Object y);

boolean isComparable(Object x);

}

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 11

Esercizio

Implementare il TDA Map tramite – Una lista – Un vettore– Una sequenza – Un dizionario

Scrivere un programma per testare tutti i metodi delle implementazioniAssumendo che un utente non inserisca mai entry con la stessa chiave, illustrare come si possa usare una mappa per implementare il TDA Dictionary

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 12

Mappe e grafi – 1

Possiamo inserire nell’implementazione di un vertice (arco) un’istanza della classe che implementa MapLa mappa associata al vertice conterrà delle informazioni aggiuntive sul nodo che possono essere inserite a seconda dell’algoritmo che utilizzerà il grafo (BFS, DFS, MST, …)– Le chiavi della mappa potranno essere stringhe

tipo: colore, distanza, genitore, …– Questo è il design pattern Decorator

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 13

Mappe e grafi – 2

A questo punto le interfacce di Vertex e Edgesaranno

public interface Vertex extends Position, Map { }public interface Edge extends Position, Map { }

La classe V che implementa di Vertex (Edge) dovrà anche implementare anche i metodi di Map– Se V ha come variabile d’istanza Map m, allora

tutto si semplifica• get(k) è implementato come m.get(k), e così via

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 14

Tabelle Hash

Una tabella hash è un modo efficiente per implementare il TDA MapUna tabella hash per un dato tipo di chiavi consiste di – Una funzione hash h– Un array (tabella) di dimensione N

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 15

Funzione HashUna funzione hash h mappa un insieme di chiavi di un certo tipo in insieme di interi in un intervallo prefissato [0, N – 1]Esempio:h(x) = x mod N

• h(x) in questo caso è definita per chiavi di tipo intero

h(x) è chiamato valore hash di xLo scopo di una funzione hash è di distribuire le chiavi uniformemente nell’intervallo [0, N - 1]

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 16

Mappe implementati con tavole hash

L’entry (k, o) è memorizzata nella posizione della tabella di indice i = h(k)– Prima di applicare la funzione hash, alla chiave k

deve essere associato un valore intero

Si verifica una collisione quando due chiavi del dizionario hanno lo stesso valore hash

Esistono vari schemi per risolvere le collisioni

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 17

Risoluzione di una collisione

Chaining–Le entry che hanno generato la

collisione vengono memorizzate in una sequenza

Open addressing– L’entry che ha generato la collisione

viene sistemata in un’altra cella della tabella

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 18

Esempio

Tabella hash per una mapa che memorizza le entry della forma (matricola, nome studente)– Array di dimensione N=10000– Valore hash di h(x) calcolato dalle ultime 4

cifre di x– Risoluzione delle collisioni con chaining

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 19

Esempio Le entry con matricola 056-432221 e quello con matricola 056-222221 collidono

∅

∅∅

01234 …

056-432221 056-222221

056/000999

∅

∅

999799989999

…

056/888889

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 20

Chaining

Ciascuna posizione dell’array è un riferimento ad una sequenza (vanno bene anche una lista o un vettore)– A[ i ] Si

– Si memorizza tutte le voci le cui chiavi hanno valore hash uguale ad i

– Si può essere visto come un piccolo dizionario implementato come log file

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 21

Linear Probing

Il metodo del linear probing risolve le collisioni sistemando le entry che collidono nella prossima cella disponibile della tabella – La tabella è vista come una struttura circolare

Ogni volta che viene ispezionata una cella per vedere se è libera si dice che si effettua un “sondaggio”

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 22

Problemi con il linear probing

Le entry che collidono tendono ad essere disposte in lunghi blocchi di celle consecutive aumentando così il numero di sondaggi necessari per inserire una nuova voce– Metodi alternativi: quadratic probing,

double hashing

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 23

Esercizi

Implementare una tabella hash usando il metodo del chaining per risolvere le collisioni– Le sequenze delle entry collidenti sono

viste come dizionari implementati come log-file

Implementare una tabella hash usando il metodo del linear probing per risolvere le collisioni

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 24

Nota su linear probing – 1

Quando cancelliamo un elemento dalla tabella hash marchiamo la cella dell’array con un oggetto speciale chiamato AVAILABLE– È simile all’oggetto NO_SUCH_KEY

Con null indichiamo il fatto che la cella è vuota e non ha mai contenuto un elemento

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 25

Nota su linear probing – 2

Se l’entry è rappresentata da un oggetto di tipo Entry, allora AVAILABLE può essere rappresentato come

protected static Entry AVAILABLE = new Entry(null, null);

get(key) e remove(key) quando incontrano l’elemento AVAILABLE proseguono con la prossima cella fino a quando trovano null o un Entry con chiave key

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 26

Nota per l’implementazione

Ci vuole un modo per confrontare le chiavi in una tabella hash (HashComparator)– isEqualTo(k1,k2), isComparable(k)

Ci vuole una funzione hashValue(k) che restituisce il valore hash associato a k– Possiamo applicare a k il metodo built-in

hashCode() che restituisce un intero R di 32 bit– Al valore R applichiamo una funzione di

compressione (funzione hash) a nostra scelta e restituiamo il valore ottenuto

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 27

Esercizio

Implementare il TDA Map usando una tabella hash che usa il metodo di chaining per risolvere le collisioniDescrivere una struttura dati efficiente per implementare il TDA Bag che supporta i metodi add(e) che aggiunge l’elemento e al contenitore ed il metodo remove() che cancella un elemento arbitrario dal contenitore– Entrambi i metodi devono avere una complessità

pari a O(1)