Accedere a nodi di una catena 

1

Iteratori e

iteratore in una catena (capitolo 14)

SETTIMANA 9

Accedere a nodi di una catena 

Per eseguire operazioni sulla catena che necessitano  di accedere ai nodi è necessario aggiungere metodi  all’interno della classe LinkedList

 che è l’unica ad avere accesso ai nodi della catena

Potremmo volere, ad esempio

 Contare i nodi nella catena

 verificare la presenza di un particolare oggetto nella  catena (algoritmo di ricerca)

 aggiungere/togliere elementi alla catena, anche in  posizioni intermedie

Questo limita molto l’utilizzo della catena come  struttura dati definita una volta per tutte…

3

Accedere a nodi di una catena 

Esempio: vogliamo contare i nodi della catena

 È  necessario scorrere tutta la catena

 Il codice va scritto dentro la classe LinkedList 

public class LinkedList { ...

public int getSize()

{ ListNode temp = head.getNext();

int size = 0;

while (temp != null) { size++;

temp = temp.getNext();

} //se la catena è vuota size = 0 (giusto!) return size;

} ....

}

Accedere a nodi di una catena

Vogliamo che la catena fornisca uno strumento per  accedere ordinatamente a tutti i suoi elementi.

 Idea: scriviamo un metodo getHead che restituisce un  riferimento al nodo header

Questo approccio però non funziona

 Se la classe ListNode è public in LinkedList si viola  l'incapsulamento, perché diventa possibile modificare lo  stato della catena dall'esterno 

 Se invece è private allora i nodi sono inaccessibili e il 

public class LinkedList

{... public ListNode getHead() { return head; }

...}

5

Iteratore in una catena

Soluzione del problema

 fornire all’utilizzatore della catena uno strumento con  cui interagire con la catena per scandire i suoi nodi

Tale oggetto si chiama iteratore e ne definiamo prima  di tutto il comportamento astratto

 Un iteratore rappresenta in astratto il concetto di  posizione all’interno di una catena

 Un iteratore si trova sempre dopo un nodo e prima del  nodo successivo (che può non esistere se l’iteratore si  trova dopo l’ultimo nodo)

• In particolare, quando viene creato l’iteratore si trova  dopo il nodo header

Iteratore in una catena

Un iteratore rappresenta in astratto il concetto di  posizione all’interno di una catena

 la posizione è rappresentata concretamente da un  riferimento ad un nodo (il nodo precedente alla  posizione dell’iteratore)

dato dato dato

null

inizio (head) fine (tail)

null

header

ITERATORE

7

L'ADT ListIterator

import java.util.NoSuchElementException;

public interface ListIterator

{ /*Una classe che realizza ListIterator per una catena avra` un costruttore del tipo NomeClasse(ListNode h), che crea un iteratore che si trova subito dopo il nodo h*/

/*Lancia NoSuchElementException se l'iteratore e` alla fine, altrimenti restituisce l'oggetto che si trova dopo la pos.

attuale e sposta l’iteratore di una pos. in avanti*/

Object next() throws NoSuchElementException;

/*verifica se si puo` invocare next()*/

boolean hasNext();

/*inserisce x in prima della posizione attuale, senza modificare la posizione dell'iteratore*/

void add(Object x);

/*Lancia IllegalStateException se invocato 2 volte consecutive altrimenti elimina l'ultimo oggetto esaminato da next() o inserito da add() senza modificare la pos. dell’iteratore*/

void remove() throws IllegalStateException;

}

L'ADT ListIterator

Possiamo immaginare un iteratore come un cursore in  un elaboratore di testi

 Un nodo della catena corrisponde ad un carattere

 L’iteratore si trova sempre “tra due nodi”, come un cursore

9

Iteratore in una catena

A questo punto, è sufficiente che la catena fornisca  un metodo per creare un iteratore

E si può scandire la catena senza accedere ai nodi

public class LinkedList { ...

public ListIterator getIterator()

{ ... }// dopo vediamo come scrivere questo metodo ...

}

LinkedList list = new LinkedList();

...ListIterator iter = list.getIterator();

while(iter.hasNext())

System.out.println(iter.next());

// notare similitudine con StringTokenizer e Scanner

L’interfaccia Iterator in Java

La libreria standard di Java definisce in java.util una  interfaccia Iterator

 Definisce in particolare i metodi next e hasNext

Sempre in java.util si trova l’interfaccia ListIterator

 Estende Iterator

 Definisce altri metodi, tra cui add e remove

L’interfaccia Iterator è implementata da una classe  che abbiamo utilizzato molto spesso: Scanner

 Ha il metodo next

 Ha il metodo hasnext

11

Implementare ListIterator

getIterator restituisce un riferimento ad una interfaccia

 Quindi in realtà deve creare un oggetto di una classe che  realizzi tale interfaccia

Implementiamo ListIterator con la classe LinkedListIterator

 I suoi oggetti sono costruiti solo all’interno di LinkedList e  restituiti all’esterno solo tramite riferimenti a ListIterator

 Per un corretto funzionamento dell’iteratore occorre concedere  a tale oggetto il pieno accesso alla catena

• in particolare, alla sua variabile di esemplare head 

 Non vogliamo che l’accesso sia consentito ad altre classi

Tutto questo ci porta a definire LinkedListIterator come una  classe interna privata di LinkedList

La classe interna LinkedListIterator

public class LinkedList

{ ... //codice di LinkedList come prima

... //incluso codice della classe privata ListNode

public ListIterator getIterator() //metodo di LinkedList

{ //crea un iteratore posizionato al primo nodo della catena return new LinkedListIterator(head); }

private class LinkedListIterator implements ListIterator { //costruttore

public LinkedListIterator(ListNode h) { current = h;

previous = null;

}

//metodi pubblici (dobbiamo ancora realizzarli) public boolean hasNext() { ... }

public Object next() { ... } public void add(Object x) { ... } public void remove() { ... } //campi di esemplare

private ListNode current;//nodo che precede pos. attuale private ListNode previous;//nodo che precede current }

13

I metodi di LinkedListIterator

import java.util.NoSuchElementException;

public class LinkedList { ...

private class LinkedListIterator implements ListIterator { ...

//metodi pubblici hasNext, next public boolean hasNext()

{ return current.getNext() != null;

}

public Object next()

{ if (!hasNext()) throw new NoSuchElementException();

previous = current;

current = current.getNext();

return current.getElement();

}

//metodi pubblici add,remove (dobbiamo ancora realizzarli) public void add(Object x) { ... }

public void remove() { ... } //campi di esemplare

private ListNode current;//nodo che precede pos. attuale private ListNode previous;//nodo che precede current }}

Il metodo add di LinkedListIterator

public void add(Object obj)

{ ListNode n = new ListNode(obj, current.getNext());

current.setNext(n);

previous = current; //aggiorno riferimenti iteratore current = current.getNext(); //a subito dopo nuovo nodo if (!hasNext()) // se ho aggiunto all'ultimo nodo LinkedList.this.tail = current; //aggiorno tail }

Aggiunge il nuovo nodo e avanza di una posizione

Se il nodo viene aggiunto alla fine della catena, allora  bisogna anche aggiornare il riferimento tail della catena

 Nota sintattica: il riferimento LinkedList.this punta  all'oggetto LinkedList all'interno di cui è stato creato  l'iterator

15

Il metodo add di LinkedListIterator

dato dato dato

null

inizio (head) fine (tail)

null

header

ITERATORE

(inizio esecuzione) obj

ITERATORE (fine esecuzione)

Il metodo remove di LinkedListIterator

/* Va sempre invocato dopo add o next, anche la prima volta */

public void remove() throws IllegalStateException

{ /*Se dalla costruzione dell'iteratore o dall'ultima

invocazione di remove non e` stato invocato next o add, allora previous==null. Stato illegale! */

if (previous == null) throw new IllegalStateException();

previous.setNext(current.getNext());

current = previous; // aggiorno riferimenti iteratore previous = null; // a subito prima del nodo rimosso if (!hasNext()) // se ho rimosso l'ultimo nodo

LinkedList.this.tail = current; //aggiorno tail }

L'iteratore non ha un riferimento al nodo prima di previous

 Quindi non posso aggiornare correttamente previous dopo la  rimozione: gli assegno valore null, con la conseguenza che  l'iteratore si trova in uno stato illegale dopo la rimozione

 Per questo motivo non si può invocare nuovamente remove. 

17

Il metodo remove di LinkedListIterator

dato dato dato

null

inizio (head) fine (tail)

null

header

ITERATORE (fine esecuzione)

ITERATORE (inizio esecuzione)

dato

null

Operazioni su catene 

mediante un iteratore 

19

Catena: conteggio elementi

Problema: data una catena ed un riferimento ad essa, si  vuole sapere il numero di nodi che la compongono

Soluzione: con un iteratore possiamo contare i nodi al di  fuori del codice di LinkedList, in una classe qualsiasi

public class MyClass

{ public static void main(String[] args) { LinkedList list = new LinkedList();

... // operazioni sulla catena int listSize = getSize(list);

public static int getSize(LinkedList list)} { ListIterator iter = list.getIterator();

int size = 0;

while (iter.hasNext()) { size++;

iter.next(); // ignoro l’oggetto ricevuto } // perché devo solo contarli return size;

}}

Catena: inserimento e rimozione

Abbiamo visto l’inserimento e la rimozione di un  elemento all’inizio e alla fine della catena, tramite i  metodi addFirst, removeFirst, addLast, removeLast

Vogliamo estendere le modalità di funzionamento della  catena per poter inserire e rimuovere elementi in 

qualsiasi punto della catena stessa

 abbiamo il problema di rappresentare il concetto di  posizione nella catena in cui inserire (o da cui  rimuovere) il nodo 

 Possiamo usare di nuovo l’iteratore, e in particolare i  suoi metodi add e remove

21

Catena: osservazioni finali

Ci sono alcune differenze tra la nostra realizzazione  della catena e la realizzazione della classe 

LinkedList proposta sul libro di testo

Usiamo un primo nodo “vuoto”

 “Sprechiamo” dello spazio in memoria 

 Ma semplifichiamo la realizzazione dei metodi (non  bisogna trattare i casi limite diversamente dagli altri) 

Usiamo un riferimento tail all’ultimo nodo

 Questo migliora le prestazioni di addLast senza  peggiorare le altre e non richiede molto spazio di  memoria

Catena doppia

(doubly linked list)

23

Catena doppia

La catena doppia (o lista doppiamente concatenata,  doubly linked list) non è un nuovo ADT

 Come la catena, è una struttura dati per la  realizzazione di ADT

Una catena doppia è un insieme ordinato di nodi

ogni nodo è un oggetto che contiene

 un riferimento ad un elemento (il dato)

 un riferimento al nodo successivo della lista (next)

 un riferimento al nodo precedente della lista (prev)

Catena doppia

next

dato

next

dato

next null

inizio (head) fine (tail)

null ^{prev prev prev}

null null

Dato che la struttura è simmetrica, si usano due nodi  vuoti, uno a ciascun estremo della catena

Tutto quanto detto per la catena (semplice) può essere  agevolmente esteso alla catena doppia

 Il metodo removeLast diventa O(1) come gli altri metodi

 Un iteratore su catena doppia avrà anche un metodo per  retrocedere di una posizione, oltre a quello per avanzare 

25

Il tipo di dato astratto Lista

Lista

Il concetto di iteratore su catena, esplicitato 

nell'interfaccia ListIterator, definisce il comportamento  astratto di un contenitore in cui

 i dati sono disposti in sequenza (cioè per ogni dato è  definito un precedente ed un successivo)

 nuovi dati possono essere inseriti in ogni punto 

 dati possono essere rimossi da qualsiasi punto

Un contenitore con un tale comportamento può essere  molto utile, per cui si definisce un tipo di dati astratto,  detto lista, con la seguente interfaccia

public interface List extends Container { ListIterator getIterator();

27

Lista

Attenzione a non confondere la lista (che è un ADT)  con la lista concatenata o catena (che è una 

struttura dati)

 La classe LinkedList può essere usata per realizzare  l'interfaccia List:

 ma non è necessario realizzare una lista mediante una  catena, perché nella definizione della lista non 

vengono menzionati i nodi

 Ad esempio è possibile definire una lista che usa un  array come struttura di memorizzazione dei dati

public class LinkedList implements List { ... // codice tutto come prima

}

Collaudo di List e LinkedList (1)

public class SimpleListTester1

{ public static void main(String[] args) { LinkedList list = new LinkedList();

//posso usare tutti i metodi di LinkedList list.addFirst("A"); //A

list.addLast("B"); //AB list.addFirst("C"); //CAB

ListIterator iter = list.getIterator();

iter.next();

iter.add("I"); //CIAB while (iter.hasNext())

iter.next();

iter.remove(); //CIA list.addLast("O"); //CIAO iter = list.getIterator();

while (iter.hasNext())

System.out.println(iter.next());

} }

C I A

29

Collaudo di List e LinkedList (2)

public class SimpleListTester2

{ public static void main(String[] args) { List list = new LinkedList();

//posso usare solo il metodo getIterator di List ListIterator iter = list.getIterator();

iter.add("A"); //A iter.add("B"); //AB iter = list.getIterator();

iter.add("C"); //CAB

iter.add("I"); //CIAB while (iter.hasNext())

iter.next();

iter.remove(); //CIA iter.add("O"); //CIAO iter = list.getIterator();

while (iter.hasNext())

System.out.println(iter.next());

} }

C I A O

Liste posizionali e

liste con rango (vettori) 

31

Rango, posizione, liste, vettori

Le operazioni più generali che vogliamo effettuare su una  lista riguardano l’inserimento e l’eliminazione di un  nuovo elemento in una posizione qualsiasi

La posizione di un elemento nella lista può essere

 indicata in modo relativo attraverso un iteratore

 indicata in modo assoluto attraverso il rango di un  elemento

Il rango è un indice che possiamo definire ricorsivamente 

 ha valore 0 per il primo elemento della lista

 ha valore i+1 per l’elemento che segue l’elemento di rango i

Conveniamo di chiamare vettore una lista con rango

Gli ADT “lista” e “vettore”

Il tipo di dato astratto “vettore” e il tipo di dato astratto 

“lista” hanno astrazioni diverse

Un vettore è una sequenza ordinata di dati, ciascuno  accessibile mediante un indice intero (il rango)

 Un vettore consente quindi l’accesso casuale a tutti gli  elementi tramite l’uso di indici

Una lista è una sequenza ordinata di dati, accessibili in  sequenza mediante un iteratore

 Una lista consente solamente accesso sequenziale ai  propri elementi

33

L'ADT “vettore”

L'ADT vettore è una generalizzazione del concetto di  array:

 Ha una lunghezza variabile

 È possibile aggiungere e togliere elementi in qualsiasi  posizione del vettore

 È possibile accedere (in lettura e scrittura) al valore di un  elemento noto il suo rango

 Un modo naturale per realizzare l'ADT vettore è quello  di utilizzare un array riempito solo in parte

In java.util esiste la classe ArrayList, che realizza una  lista con rango e con una ricca dotazione di funzionalità 

Vettori e liste: efficienza operazioni

L'efficienza delle operazioni fondamentali cambia se  la posizione è specificata tramite rango o iteratore

 Con rango: l'accesso richiede tempo costante, ma  inserimenti e rimozioni comportano in media lo  spostamento di n/2 elementi, cioè tempo O(n)

 Con iteratore: l'accesso richiede tempo lineare O(n)  (bisogna scorrere la lista dall'inizio), ma inserimenti e  rimozioni comportano un numero costante di operazioni

35

Riassunto: dati in sequenza

Abbiamo fin qui visto diversi tipi di contenitori per  dati in sequenza, rappresentati dagli ADT

 pila

 coda

 lista con iteratore

 lista con rango (vettore)

Per realizzare tali ADT, abbiamo usato diverse  strutture dati

 Array

 Catena

 Catena doppia

37

Mappe e Dizionari

(capitolo 15 ­ ma la nostra 

trattazione è abbastanza diversa)

Mappa: definizione

Una mappa è un ADT con le seguenti proprietà

 Contiene dati (non in sequenza) che sono coppie di tipo  chiave/valore

 Non può contenere coppie con identica chiave: ogni chiave  deve essere unica nell’insieme dei dati memorizzati

 Consente di inserire nuove coppie chiave/valore

 Consente di effettuare ricerca e rimozione di valori usando  la chiave come identificatore

39

Dizionario: definizione

L'ADT dizionario ha molte similitudini con l'ADT mappa

 Valgono tutte le proprietà dell'ADT mappa, tranne una

 Non si richiede che le chiavi siano uniche nel dizionario

C'è analogia con un dizionario di uso comune, in cui

 le chiavi sono le singole parole

 I valori sono le definizioni delle parole nel dizionario

 le chiavi (parole) possono essere associate a più valori  (definizioni) e quindi comparire più volte nel dizionario

 la ricerca di un valore avviene tramite la sua chiave

Si distinguono dizionari ordinati e dizionari non­ordinati 

 A seconda che sull'insieme delle chiavi sia o no definita una  relazione totale di ordinamento, cioè (in Java) che le chiavi  appartengano ad una classe che implementa Comparable

La nostra trattazione è limitata ad un caso ben preciso

 Dizionari ordinati a chiave unica (cioè mappe)

L’interfaccia Dictionary

public interface Dictionary extends Container

{ // l'inserimento va sempre a buon fine; se la chiave non // esiste la coppia viene aggiunta al dizionario. Se esiste, // il valore ad essa associato viene sovrascritto dal nuovo // valore; se key e` null si lancia IllegalArgumentException void insert(Comparable key, Object value);

// la rimozione della chiave rimuove anche il corrispondente // valore dal dizionario. Se la chiave non esiste si lancia // DictionaryItemNotFoundException

void remove(Comparable key);

// la ricerca per chiave restituisce solo il valore ad essa // associato nel dizionario. Se la chiave non esiste si // lancia DictionaryItemNotFoundException

Object find(Comparable key);

}

//Eccezione che segnala il mancato ritrovamento di una chiave class DictionaryItemNotFoundException extends RuntimeException { }

41

Implementare Dictionary con array

Un dizionario può essere realizzato usando la  struttura dati array

 Ogni cella dell’array contiene un riferimento ad una  coppia chiave/valore 

 La coppia chiave/valore sarà un oggetto di tipo Pair  (da definire)

 Generalmente si usa un array riempito solo in parte

A seconda degli ambiti applicativi ci sono due  strategie possibili

 mantenere le chiavi ordinate nell’array

 mantenere le chiavi non ordinate nell’array

A seconda della strategia scelta, cambiano le  prestazioni dei metodi del dizionario

Dizionario con array ordinato

Se le n chiavi vengono conservate ordinate nell’array

La ricerca ha prestazioni O(log n)

 Perché si può usare la ricerca per bisezione

la rimozione ha prestazioni O(n)

 Perché bisogna effettuare una ricerca, e poi spostare  mediamente n/2 elementi per mantenere l’ordinamento

L’inserimento ha prestazioni O(n) 

 Perché si può usare l’ordinamento per inserimento in  un array ordinato

 Usando un diverso algoritmo occorre riordinare l’intero  array, con prestazioni almeno O(n log n)

43

Dizionario con array non ordinato

Se le n chiavi vengono conservate non ordinate

La ricerca ha prestazioni O(n)

 Bisogna usare la ricerca lineare

La rimozione ha prestazioni O(n)

 Bisogna effettuare una ricerca (lineare), e poi spostare  nella posizione trovata l'ultimo elemento dell'array 

(l’ordinamento non interessa)

L’inserimento ha prestazioni O(n)

 Bisogna rimuovere (sovrascrivere) un elemento con la  stessa chiave, se c'è, e poi inserire il nuovo elemento nella  ultima posizione dell’array (l’ordinamento non interessa)

 [Se non si richiede che le chiavi siano uniche nel dizionario,  la rimozione non è necessaria e l'inserimento è O(1) ]

Prestazioni di un dizionario

La scelta di una particolare realizzazione dipende  dall’utilizzo tipico del dizionario nell’applicazione

 Se si fanno frequenti inserimenti e sporadiche ricerche  e rimozioni la scelta migliore è l’array non ordinato

 Se il dizionario viene costruito una volta per tutte, poi  viene usato soltanto per fare ricerche la scelta migliore è 

[O(1) per chiavi non uniche]

45

Realizzazione di un  dizionario

La classe interna Pair

public class ArrayDictionary implements Dictionary { ...

protected class Pair //classe interna ad ArrayDictionary { public Pair(Comparable key, Object value)

{ setKey(key);

setValue(value); } //metodi pubblici

public String toString()

{ return key + " " + value; } public Comparable getKey()

{ return key; }

public Object getValue() { return value; }

public void setKey(Comparable key) { this.key = key; }

public void setValue(Object value) { this.value = value; }

//campi di esemplare private Comparable key;

private Object value;

}

47

La classe ArrayDictionary

public class ArrayDictionary implements Dictionary { public ArrayDictionary()

{ v = new Pair[INITSIZE]; // ... sempre uguale makeEmpty();

}

public boolean isEmpty()

{ return vSize == 0; } // ... sempre uguale public void makeEmpty()

{ vSize = 0; } // ... sempre uguale public String toString()

{ String s = "";

for (int i = 0; i < vSize; i++) s = s + v[i] + "\n";

return s;

}

public void insert(Comparable key, Object value)

{ if (key == null) throw new IllegalArgumentException();

try

{ remove(key); } //elimina elemento se gia` presente catch (DictionaryItemNotFoundException e)

{} //... ovvero sovrascrive elemento se gia` presente if (vSize == v.length) v = resize(2*vSize);

v[vSize++] = new Pair(key, value);

} //continua

La classe ArrayDictionary

//continua protected Pair[] resize(int newLength) //metodo ausiliario { ... } //solito codice

public void remove(Comparable key)

{ v[linearSearch(key)] = v[--vSize];

}

public Object find(Comparable key)

{ return v[linearSearch(key)].getValue();

}

private int linearSearch(Comparable key) //metodo ausiliario { for (int i = 0; i < vSize; i++)

if (v[i].getKey().compareTo(key) == 0)

//oppure if (v[i].getKey().equals(key)), se il //metodo equals e` stato realizzato correttamente return i;

throw new DictionaryItemNotFoundException();

}

//campi di esemplare protected Pair[] v;

protected int vSize;

protected final static int INITSIZE = 10;

49

Dizionario con array ordinato

Avendo usato un array non ordinato, i metodi remove e  find effettuano una ricerca lineare sulle chiavi

Esercizio: realizzare un dizionario con un array ordinato

 Il metodo insert deve mantenere ordinato l'array ad ogni  inserimento (usando insertionSort...)

 I metodi remove e find possono usare la ricerca binaria  per trovare una chiave

 Il metodo remove deve ricompattare l'array dopo la  rimozione, mantenendolo ordinato

public class SortedArrayDictionary extends ArrayDictionary { // realizzazione con array non ordinato. Eredita campi di // esemplare e variabili statiche, la classe Pair, i metodi // isEmpty, makeEmpty, resize. Deve sovrascrivere i metodi // insert, remove, find

}

import java.util.Scanner;

import java.io.*;

public class SimpleDictionaryTester

{ public static void main(String[] args) throws IOException { //creazione dizionario: leggo dati da file e assumo che //il file abbia righe nel formato <numero int> <stringa>

Scanner infile = new Scanner(new FileReader("file.txt"));

Dictionary dict = new ArrayDictionary();

// ... oppure = new SortedArrayDictionary();

while (infile.hasNextLine())

{ Scanner linescan = new Scanner(infile.nextLine());

int key = Integer.parseInt(linescan.next());

String value = linescan.next();

dict.insert(key,value); //inserisco chiave e valore }

infile.close();

//ricerca/rimozione dati nel dizionario Scanner in = new Scanner(System.in);

boolean done = false; // continua

Collaudo di un dizionario

51

Collaudo di un dizionario

while (!done) // continua { System.out.println("**** Stampa dizionario ****");

System.out.println(dict +"\nF=find,R=remove,Q=quit");

String cmd = in.nextLine();//ho sovrascritto toString if (cmd.equalsIgnoreCase("Q"))

{ done = true; }

else if (cmd.equalsIgnoreCase("F"))

{ System.out.println("Chiave da trovare?");

int key = Integer.parseInt(in.nextLine());

try{ //cerca key chiave e restituisce il valore String value = (String)dict.find(key);

System.out.println("Valore: " + value); } catch(DictionaryItemNotFoundException e)

{ System.out.println("Chiave non trovata");}

}

else if (cmd.equalsIgnoreCase("R"))

{ System.out.println("Chiave da rimuovere?");

int key = Integer.parseInt(in.nextLine());

try{//rimuove la coppia identificata da key dict.remove(key);

System.out.println("Chiave rimossa"); } catch(DictionaryItemNotFoundException e)

{ System.out.println("Chiave non trovata");}

} } } }

Dizionari a chiavi numeriche

L'ADT Tabella

53

Chiavi numeriche

Supponiamo per un attimo che le chiavi di un 

dizionario siano numeri interi appartenenti ad un  intervallo noto a priori

Allora si può realizzare molto semplicemente un 

dizionario con prestazioni O(1) per tutte le operazioni

 Si usa un array che contiene soltanto i riferimenti ai  valori delle coppie del dizionario

 Le chiavi delle coppie vengono usate come indici  nell’array

 Le celle dell’array che hanno come indice una chiave  che non è presente nel dizionario hanno il valore null

Tabella

Un dizionario con chiavi numeriche intere viene detto  tabella o tavola (table)

L’analogia è la seguente

 un valore è una riga nella tabella

 le righe sono numerate usando le chiavi

 alcune righe possono essere vuote (senza valore) chiave = 0 valore0

valore2null valore3

nullnull chiave = 2

chiave = 3

dato

dato

dato

55

L'interfaccia Table

Definiamo il tipo di dati astratto Table con un  comportamento identico al dizionario

 l’unica sostanziale differenza è che le chiavi non sono  riferimenti a oggetti di tipo Comparable, ma sono  numeri interi (che evidentemente sono confrontabili)

 Potremmo (non lo facciamo) realizzarlo usando array  (questa volta non riempiti solo in parte!)

public interface Table extends Container { void insert(int key, Object value);

void remove(int key);

Object find(int key);

}

Tabella

Una realizzazione dell'ADT tabella tramite array fornisce  prestazioni ottime

 tutte le operazioni sono O(1)

Prima limitazione: le chiavi devono essere numeri interi

Seconda limitazione (più pesante): la tabella non  utilizza la memoria in modo efficiente

 l’intervallo di variabilità delle chiavi deve essere noto a  priori per dimensionare la tabella

• la memoria richiesta per contenere n dati dipende dal loro  contenuto, in particolare dal valore della chiave massima

 Se le chiavi sono molto “disperse”, ovvero se il fattore di  riempimento è piccolo, si ha grande spreco di memoria

• fattore di riempimento di una tabella = (numero di dati 

57

Tabella con ridimensionamento

Se l’intervallo di variabilità delle chiavi non è noto a  priori e si inserisce una chiave di valore superiore alla  lunghezza dell’array bisogna ridimensionare l’array 

 Un inserimento richiede un tempo O(n) ogni volta che è  necessario un ridimensionamento

• Qui non si può utilizzare l’analisi ammortizzata perché  non si può prevedere il valore della nuova chiave

 il ridimensionamento può avvenire ad ogni inserimento,  e le prestazioni nel caso peggiore sono quindi O(n) 

Può essere necessario un array di milioni di elementi  per contenere poche decine di dati

La struttura dati

“tabella hash con bucket”

59

Tabella hash con bucket

Introduciamo una nuova struttura dati che ci permette  di superare entrambe le limitazioni di una tabella 

realizzata tramite array

Limitazioni della tabella: le chiavi devono essere  numeri interi in un intervallo prefissato

 Introdurremo una funzione di hash che assegna dei  valori numerici (interi in un intervallo prefissato) a delle  chiavi generiche

Seconda limitazione della tabella: la memoria non  viene utilizzata in maniera efficiente

 Useremo un array di bucket (“secchi”), cosicché ogni  indice dell'array possa essere associato a più elementi  del dizionario

Funzioni di hash

61

Chiavi generiche e codici hash

Prima limitazione della tabella: le chiavi devono  essere numeri interi

E se le chiavi non sono int ma sono invece oggetti  arbitrari di tipo Object?

 Esempio: contenitore di oggetti di tipo PersonaFisica, la  cui chiave è il codice fiscale (cioè è di tipo String)

Vogliamo realizzare il dizionario tramite una tabella  anche in questo caso

Dobbiamo “tradurre” le chiavi in valori numerici

 Dobbiamo cioè progettare un codice hash

 il codice hash è una funzione che ha come dominio  l’insieme delle chiavi generiche in esame e come  codominio un sottoinsieme dei numeri interi

Codice hash

Il codice hash è quindi una funzione così definita:

h₁: {Chiavi} → {Interi}

In Java

 la classe Object mette a disposizione il metodo 

hashCode che restituisce un int con buone proprietà  di distribuzione uniforme

 Se il metodo hashCode non viene ridefinito, esso  associa ad un oggetto un valore numerico calcolato in  base all’indirizzo dell’oggetto in memoria

 L’esistenza di questo metodo rende possibile l’utilizzo  di qualsiasi oggetto come chiave

63

Un codice hash per stringhe

Come si può trasformare una stringa in un numero  intero?

 Ricordiamo il significato della notazione posizionale  nella rappresentazione di un numero intero

 Ciascuna cifra rappresenta un numero che dipende dal  suo valore intrinseco e dalla sua posizione

Usiamo la stessa convenzione per una stringa, dove  ogni carattere rappresenta un numero che dipende

 Dal suo valore intrinseco come carattere nella codifica  Unicode

 Dalla sua posizione nella stringa

434 = 4·10² + 3·10¹ + 4·10⁰

Un codice hash per stringhe

Il valore numerico associato ad una stringa è quindi  calcolato in questo modo

Che valore utilizziamo per la base?

 Spesso si usa un numero primo come valore di base,  perché questo “mescola” bene i valori

• Ovvero stringhe diverse hanno con buona probabilità  codici hash diversi

 In alternativa la base sarà (come per la notazione  posizionale di interi) il numero di simboli diversi

• che per la codifica Unicode è 2¹⁶ = 65536

"ABC" ⇒ 'A'·base² + 'B'·base¹ + 'C'·base⁰

"ABC" ⇒ 'A'·65536 + 'B'·65536 + 'C'·65536

65

Mappe di compressione

C'è ancora un problema: l’intervallo di variabilità delle  chiavi deve essere noto a priori per dimensionare la  tabella

Affrontiamo il problema in questo modo

 Prefissiamo la dimensione della tabella in modo arbitrario

 Quindi definiamo di conseguenza l’intervallo di variabilità  delle chiavi utilizzabili: il valore massimo consentito è la  lunghezza della tabella

Bisogna modificare la funzione h₁ in modo che tutti i  valori numerici associati alle chiavi ricadano all’interno  dell’intervallo prefissato

 Si usa una ulteriore funzione di trasformazione delle  chiavi, detta mappa di compressione

Mappe di compressione

Abbiamo definito il codice hash h₁: {Chiavi} {Interi}→

 In Java la funzione h₁ è realizzata dal metodo hashCode 

Definiamo ora una funzione mappa di compressione:

 h₂ : {Interi}   [0, N ­ 1]→

 Il codominio di h₂ è il sottoinsieme [0, N ­ 1] dei numeri  interi, dove N coincide con la dimensione della tabella

Esempio di mappa di compressione

 resto della divisione intera tra il codice hash di un  oggetto e la dimensione N della tabella

 h₂(h₁(x)) = h₁(x) % N

 Il valore calcolato è un intero nell’intervallo [0, N­1] 

67

Funzioni di hash

Siamo ora in grado di definire una funzione di hash  h(x) come composizione delle funzioni h₁ (codice  hash) e h₂ (mappa di compressione)

 h : {Chiavi}   [0, N ­ 1]→ h(x) = h₂(h₁(x))

Una funzione di hash ha

 come dominio l’insieme delle chiavi che identificano  univocamente i dati da inserire nel dizionario

 come codominio l’insieme degli indici validi per  accedere ad elementi della tabella

• il risultato dell’applicazione della funzione di hash ad  una chiave si chiama chiave ridotta

Una tabella che usa chiavi ridotte si chiama tabella hash (hash table)

Funzioni di hash

La funzione di hash h(x) come composizione di h₁ e h₂

Chiavi arbitrarie Chiavi arbitrarie

Codice hash Codice hash

h h

Mappa di compressione Mappa di compressione

h h

      ­3  ­2   ­1    0    1     2     3­3  ­2   ­1    0    1     2     3

69

Bucket in una tabella hash

Collisioni in una tabella hash

Ora abbiamo un nuovo problema: Per come è definita,  una funzione di hash è generalmente non biunivoca

 chiavi diverse possono avere lo stesso valore per la  funzione di hash

• In generale non si può definire una funzione h biunivoca,  perché il dominio ha dimensione maggiore del codominio

Inseriamo nella tabella un elemento con chiave x₁

 Supponiamo che h(x₁) = h(x₂), dove x₂ != x₁ è la chiave  di un elemento già presente nella tabella

• Ovvero x₁ ed x₂ hanno la stessa chiave ridotta

 Il nuovo elemento sostituisce il vecchio nella tabella

• Questo non è corretto perché i due valori hanno, in realtà, 

71

Collisioni in una tabella hash

Se due elementi hanno chiavi diverse ma uguali  chiavi ridotte si verifica una collisione nella tabella

In presenza di una collisione, bisognerebbe inserire  il nuovo valore nella stessa cella della tabella 

(dell’array) che già contiene un altro valore

 ciascun valore deve essere memorizzato insieme alla  sua vera chiave, per poter fare ricerche correttamente

Possiamo risolvere il problema usando una lista  associata ad ogni cella dell’array

 L’array è quindi un array di riferimenti a liste

 Ciascuna lista contiene le coppie chiave/valore che  hanno la stessa chiave ridotta

Tabella hash con bucket

Questo sistema di risoluzione delle collisioni si  chiama tabella hash con bucket

 un bucket è una delle liste associate ad una chiave  ridotta

hash = 0 bucket0 bucket2null bucket3

nullnull hash = 2

hash = 3

coppia coppia coppia

coppia

coppia

73

Tabella hash con bucket: prestazioni

Le prestazioni della tabella hash con bucket non sono  più, ovviamente, O(1) per tutte le operazioni

Effettuiamo ad esempio una ricerca su una chiave x

 Il tempo per raggiungere il bucket di indice h(x) è O(1)

 Il tempo per raggiungere l’elemento con chiave x nel  bucket dipende dalla lunghezza della lista

Le prestazioni dipendono fortemente dalle  caratteristiche della funzione di hash

 Una “buona” funzione di hash minimizza le collisioni, cioè  fornisce chiavi ridotte distribuite in maniera uniforme  nella tabella

• In questo modo le liste in ogni bucket hanno tutte  approssivamente la stessa lunghezza (minima)

Tabella hash con bucket: prestazioni

Caso  peggiore

 La funzione di hash restituisce sempre la stessa  chiave ridotta, per ogni chiave possibile

 Allora tutti i dati vengono inseriti in un’unica lista

In questo caso le prestazioni della tabella hash  degenerano in quelle di una lista

• tutte le operazioni sono O(n)

bucket2null

hash = 2

coppia coppia coppia

null null

75

Tabella hash con bucket: prestazioni

Caso migliore: 

 La funzione di hash restituisce chiavi ridotte che si  distribuiscono uniformemente nella tabella

 Tutte le liste hanno la stessa lunghezza media

Se N è la dimensione della tabella

 La lunghezza media di ciascuna lista è n/N

 Tutte le operazioni sono O(n/N)

Per avere prestazioni O(1) occorre dimensionare la  tabella in modo che N sia dello stesso ordine di  grandezza di n

Tabella hash con bucket: prestazioni

Riassumendo, in una tabella hash con bucket si  ottengono prestazioni ottimali, ovvero O(1), se

 La dimensione della tabella è circa uguale al numero  di dati che saranno memorizzati nella tabella

• Ovvero se il fattore di riempimento è circa unitario  (così si riduce al minimo anche lo spreco di memoria)

 La funzione di hash genera chiavi ridotte che siano  uniformemente distribuite

• Ovvero produce liste di lunghezza quasi uguale alla  lunghezza media

• In particolare, se le chiavi vere sono uniformemente  distribuite la funzione di hash h(x) = h1(x) % N genera  chiavi ridotte uniformemente distribuite

Sotto queste ipotesi le liste hanno quasi tutte 

77

Insiemi

(capitolo 15 ­ ma la nostra 

trattazione è abbastanza diversa)

Il tipo di dati astratto Insieme (Set)

È un contenitore (eventualmente vuoto) di oggetti distinti  (cioè non contiene duplicati)

 Senza alcun particolare ordinamento o memoria dell’ordine  in cui gli oggetti sono inseriti/estratti

 Corrisponde alla nozione matematica di insieme

Definiamo la nostra astrazione di insieme tramite le  seguenti operazioni

 inserimento di un oggetto

• fallisce silenziosamente se l’oggetto è già presente

 verifica della presenza di un oggetto

 ispezione di tutti gli oggetti

• restituisce un array (in generale non ordinato) di riferimenti agli  oggetti dell’insieme

 Non definiamo un’operazione di rimozione

79

Operazioni sugli insiemi

Per due insiemi A e B, si definiscono le operazioni

 unione, A ∪ B

• appartengono all’unione di due insiemi tutti e soli gli oggetti  che appartengono ad almeno uno dei due insiemi

 intersezione, A ∩ B

• appartengono all’intersezione di due insiemi tutti e soli gli  oggetti che appartengono ad entrambi gli insiemi

 sottrazione, A ­ B (oppure anche A \ B)

• appartengono all’insieme sottrazione tutti e soli gli oggetti  che appartengono ad A e non appartengono a B

• non è necessario che B sia un sottoinsieme di A

Insieme con array non ordinato

Scriviamo innanzitutto l’interfaccia Set

La classe ArraySet ha questa interfaccia pubblica

 Abbiamo scritto enunciati return per metodi che non  restituiscono void

public class ArraySet implements Set { public void makeEmpty() { }

public boolean isEmpty() { return true; } public void add(Object x) { }

public boolean contains(Object x) { return true; } public Object[] toArray() { return null; }

}

public interface Set extends Container { void add(Object obj);

boolean contains(Object obj);

Object[] toArray();

}

81

La classe ArraySet

public class ArraySet implements Set { public ArraySet()

{ v = new Object[INITSIZE];

vSize = 0;}

public void makeEmpty() { vSize = 0; }

public boolean isEmpty() { return (vSize == 0); }

public void add(Object x)//prestazioni O(n) (usa contains) { if (contains(x)) return;

if (vSize == v.length) v = resize(2*vSize);

v[vSize++] = x; }

public boolean contains(Object x) //metodo con prestaz. O(n) { for (int i = 0; i < vSize; i++)

if (v[i].equals(x)) return true;//non si puo` usare

return false; //compareTo perche` x e` solo un Object public Object[] toArray() // metodo con prestazioni O(n).

{ Object[] x = new Object[vSize]; //Creiamo un nuovo array System.arraycopy(v, 0, x, 0, vSize);//altrimenti si viola return x; } //l’incapsulamento private Object[] resize(int n) { ... }//solito codice //campi di esemplare e var. statiche

private Object[] v;

private int vSize;

private static int INITSIZE = 100;

}

Operazioni su insiemi: unione

Prestazioni: se contains è O(n) (e, quindi, lo è  anche add), questa operazione è O(n²)

public static Set union(Set s1, Set s2) { Set x = new ArraySet();

// inseriamo gli elementi del primo insieme Object[] v = s1.toArray();

for (int i = 0; i < v.length; i++) x.add(v[i]);

// inseriamo tutti gli elementi del // secondo insieme, sfruttando le

// proprietà di add (niente duplicati...) v = s2.toArray();

for (int i = 0; i < v.length; i++) x.add(v[i]);

return x;

}

83

Operazioni su insiemi: intersezione

Prestazioni: se contains è O(n) l’operazione di  intersezione è O(n²)

public static Set intersection(Set s1, Set s2) { Set x = new ArraySet();

Object[] v = s1.toArray();

for (int i = 0; i < v.length; i++) if (s2.contains(v[i]))

x.add(v[i]);

// inseriamo solo gli elementi che // appartengono anche al secondo

// insieme, sfruttando le proprieta’

// di add (niente duplicati...) return x;

}

Operazioni su insiemi: sottrazione

Prestazioni: se contains è O(n) l’operazione di  intersezione è O(n²)

public static Set subtract(Set s1, Set s2) { Set x = new ArraySet();

Object[] v = s1.toArray();

for (int i = 0; i < v.length; i++) if (!s2.contains(v[i]))

x.add(v[i]);

// inseriamo solo gli elementi che // *non* appartengono al secondo

// insieme, sfruttando le proprieta’

// di add (niente duplicati...) return x;

}

85

Insieme con array non ordinato

Riassumendo, realizzando un insieme con un array  non ordinato

 le prestazioni di tutte le operazioni primitive  dell’insieme sono O(n)

 le prestazioni di tutte le operazioni che agiscono su  due insiemi sono O(n²)

Si può facilmente verificare che si ottengono le  stesse prestazioni realizzando l’insieme con una  catena (LinkedListSet)

Esercizio:

Insiemi di dati ordinabili

87

Insieme di dati ordinabili

Cerchiamo di capire se si possono avere prestazioni  migliori quando l’insieme contiene dati ordinabili

 Definiamo l’interfaccia “insieme ordinato”

Realizziamo SortedSet usando un array ordinato

 dovremo definire due metodi add, uno dei quali  impedisce l’inserimento di dati non ordinabili

public interface Set extends Container { void add(Object obj);

boolean contains(Object obj);

Object[] toArray();

} public interface SortedSet extends Set { void add(Comparable obj);

Comparable[] toSortedArray();

}

Esercizio: la classe ArraySortedSet

public class ArraySortedSet implements SortedSet { public ArraySortedSet()

{ v = new Comparable[INITSIZE]; vSize = 0; } public void makeEmpty()

{ vSize = 0; }

public boolean isEmpty() { return (vSize == 0); }

public void add(Object x) //metodo di Set { throw new IllegalArgumentException(); }

public void add(Comparable x) // prestazioni O(n)

{ ... } //Da completare: riordinamento per inserimento //E` O(n), perche' inseriamo in un array ordinato public boolean contains(Object x) //prestaz. O(log n)

{ ... } // da completare: usare ricerca binaria e compareTo public Comparable[] toSortedArray() // prestaz. O(n)

{ ... } //da completare (v e’ gia` ordinato...)

public Object[] toArray() //Sovrascritto: l'array non deve { return toSortedArray(); } //essere per forza disordinato private Comparable[] resize(int newLength) //solito metodo { ... } // da completare

//campi di esemplare e variabili statiche private Comparable[] v;

private int vSize;

89

Operazioni su insiemi ordinati

Gli algoritmi di unione, intersezione, sottrazione per  insiemi generici possono essere utilizzati anche per  insiemi ordinati

 infatti, un SortedSet è anche un Set

Quale è la complessità dell'algoritmo di unione?

 Rimane O(n²) perché il metodo add è rimasto O(n), a  causa del ri­ordinamento (con insertionSort) dell’array

Sfruttiamo ciò che sappiamo delle realizzazioni di add  e toSortedArray nella classe ArraySortedSet

 l’array ottenuto con il metodo toSortedArray è ordinato

 l’inserimento nell’insieme tramite add usa l’algoritmo di  ordinamento per inserzione in un array ordinato

SortedSet: unione

Per realizzare l’unione, osserviamo che il problema è  molto simile alla fusione di due array ordinati

 come abbiamo visto in mergeSort, questo algoritmo di  fusione (che abbiamo realizzato nel metodo ausiliario  merge) è O(n)

L’unica differenza consiste nella contemporanea  eliminazione (cioè nel non inserimento…) di  eventuali oggetti duplicati

 un oggetto presente in entrambi gli insiemi dovrà  essere presente una sola volta nell’insieme unione

91

SortedSet: unione

Quali sono le prestazioni di questo metodo union?

public static SortedSet union(SortedSet s1,SortedSet s2) { SortedSet x = new ArraySortedSet();

Comparable[] v1 = s1.toSortedArray();

Comparable[] v2 = s2.toSortedArray();

int i = 0, j = 0;

while (i < v1.length && j < v2.length) // merge if (v1[i].compareTo(v2[j]) < 0)

x.add(v1[i++]);

else if (v1[i].compareTo(v2[j]) > 0) x.add(v2[j++]);

else // sono uguali { x.add(v1[i++]);

j++; }

while (i < v1.length) x.add(v1[i++]);

while (j < v2.length) x.add(v2[j++]);

return x;

}

SortedSet: unione

Effettuando la fusione dei due array ordinati secondo  l’algoritmo visto in MergeSort, gli oggetti vengono via  via inseriti nell’insieme unione che si va costruendo

 Questi inserimenti avvengono con oggetti in ordine  crescente

Quali sono le prestazioni di add in questo caso?

 L’invocazione di contains ha prestazioni O(log n) per  ogni inserimento

 L’ordinamento per inserzione in un array ordinato, usato  da add, ha prestazioni O(1) per ogni inserimento!

In questo caso add ha quindi prestazioni O(log n)

Quindi complessivamente il metodo statico union ha  prestazioni O(n log n)