Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Rappresentazione concreta di insiemi e
Hash table
Copyright © 2006-2009 by Claudio Salati.
Lez. 13
1
Rappresentazione di insiemi
• Si e' visto che sono possibili diverse rappresentazioni concrete per
realizzare insiemi di valori omogenei (dello stesso tipo):
• liste
• vettori
• alberi
• Diverse rappresentazioni concrete consentono di realizzare
modalita' di accesso all'insieme piu' o meno efficienti.
• In genere, per realizzare operazioni di accesso all'insieme
efficienti, e' necessario mantenere l'insieme ordinato
 questo consente ad esempio, in un vettore o in un albero
binario, di verificare la presenza di un elemento nell'insieme in
tempo O(log(n)).
• Naturalmente mantenere l'insieme ordinato ha un costo
 in una lista il costo dell'inserimento ordinato e' O(n) mentre
quello del semplice inserimento e' O(1)
2
Il tipo Unix fd_set
.1
• In Unix i file descriptor che rappresentano le handle di accesso
alle risorse del sistema da parte di un processo sono descritti
come interi non negativi di piccole dimensioni.
• Il valore massimo che puo’ assumere un file descriptor e’ cambiato
nel tempo, e in questo momento e’ di 1023.
• Cio’ consente ad un processo di accedere a 1024 risorse
contemporaneamente.
 L’universo U dei file descriptor e’ costituito dall’insieme {0 ..
1023}).
• Ci sono alcune system call (e.g. la system call select()) che
possono operare simultaneamente su piu’ file descriptor:
 per consentire cio’ Unix prevede di passare loro come
argomento un insieme di file descriptor, e per fare cio’ definisce
il tipo di dato astratto fd_set.
3
Il tipo Unix fd_set
.2
• Gli oggetti di tipo fd_set possono essere manipolati tramite le
seguenti operazioni:
• void FD_ZERO(fd_set *fdset);
azzera fdset, e quindi rende vuoto il set.
• void FD_SET(int fd, fd_set *fdset);
inserisce il file descriptor (di numero) fd nel set fdset.
• void FD_CLR(int fd, fd_set *fdset);
elimina il file descriptor (di numero) fd dal set fdset.
• int FD_ISSET(int fd, fd_set *fdset);
verifica se il file descriptor (di numero) fd e' presente (valore
ritornato !=0) o no (valore ritornato ==0) nel set fdset.
• Oltre a queste operazioni possiamo pensare anche a operazioni di
intersezione e unione di insiemi, e al complemento di un insieme
4
rispetto all’universo (vedi esercizi).
Il tipo Unix fd_set
.3
•
La rappresentazione concreta Unix del tipo fd_set e’ costituita da un
array di bit, tanti quanto grande e’ l’universo U dei file descriptor.
•
L’elemento k dell’array e’ associato all’elemento k di U:
•
se k e’ presente nell’insieme il valore del bit corrispondente e’ 1,
•
•
se k non e’ presente nell’insieme il valore del bit corrispondente
e’ 0.
Questa rappresentazione concreta e’ possibile per due motivi:
1. L’universo U e’ di dimensione limitata
 e’ ammissibile che la complessita’ spaziale della
rappresentazione sia proporzionale alla dimensione di
U(piuttosto che al numero di elementi effettivamente presenti
in un insieme).
 Poiche’ ad ogni elemento dell’universo e’ associato un solo
bit, la rappresentazione concreta risulta comunque anche
spazialmente efficiente.
2. Il valore degli elementi dell’insieme puo’ essere utilizzato come
indice nell’array di bit.
5
Il tipo Unix fd_set
.4
• La rappresentazione concreta di un fd_set puo’ essere ad esempio la
seguente:
typedef unsigned long long fd_set[16];
• Le operazioni su fd_set sono realizzate concretamente operando
(eventualmente su gruppi di bit, e.g. quelli che fanno parte di un
unsigned long long) tramite gli operatori <<, |, &, ~
• Gli operatori ~ , | e & operano parallelamente su tutti i bit di una
parola di memoria: per una macchina a 64 bit, su 64 bit per volta.
• Per implementare l’operazione di unione/intersezione su insiemi
basati su un universo di 1024 elementi sono percio’ necessarie 16
operazioni elementari.
6
Il tipo Unix fd_set
.5
La complessita’ delle operazioni su fd_set e’ la seguente:
• FD_ZERO, come unione e intersezione di fd_set
• sono formalmente lineari nel numero di elementi dell’universo
(non nel numero di elementi contenuti nell’insieme!),
• ma in pratica, per come sono implementate, possono essere
considerate di complessita’ O(1)
(sono costituite di un numero fisso e molto limitato di
operazioni, attualmente 16).
• FD_SET, FD_CLR, FD_ISSET sono di complessita’ O(1).
• Di complessita’ effettivamente lineare nel numero di elementi di U
sono invece operazioni come
• la ricerca dell’elemento minimo o massimo di un insieme,
•
la ricerca dell’elemento precedente o di quello successivo di
un elemento dato.
7
Il tipo Unix fd_set
.6
• L’operazione FD_ISSET() ha complessita’ O(1),
ma identificare tutti gli elementi di un insieme ha complessita’
effettivamente lineare nel numero di elementi dell’universo
(devo effettuare la verifica di appartenenza elemento per elemento,
per ogni elemento dell’universo).
• Una situazione analoga la si ha se si vogliono visualizzare tutti gli
elementi di un insieme: la complessita’ dell’operazione e’ O(#U).
• Per limitare la complessita’ dell’operazione di identificazione di tutti
gli elementi di un insieme la system call select() richiede come
primo parametro il valore dell’elemento massimo inserito
nell’insieme.
8
Tabelle hash
•
Una tabella hash consente di rappresentare insiemi (anche di elementi non
ordinabili) realizzando operazioni di
• inserimento di un elemento
• verifica di presenza/assenza di un elemento
• rimozione di un elemento (con qualche attenzione)
in tempo O(1) (quasi).
•
Non sono convenientemente supportate operazioni come:
• Ricerca dell'elemento minimo o di quello massimo.
• Ricerca dell'elemento successivo o precedente.
• Enumerazione ordinata degli elementi di un insieme.
• Unione /intersezione.
•
Applicazioni:
• tavole simboli
• servizi di directory
• ricezione di messaggi duplicati o corrotti
9
Tabelle hash
• In un albero la ricerca di un elemento avviene tramite una
successione di confronti.
• Si e’ visto pero’ che e’ possibile ordinare senza confronti, per
distribuzione.
• La rappresentazione a stringa di bit per un insieme di numeri
naturali di piccole dimensioni si basa sul principio di distribuzione.
• Questa rappresentazione pero’ ha una complessita’ spaziale
che e’ proporzionale non al numero di elementi presenti
nell’insieme ma alle dimensioni dell’universo dal quale sono
tratti gli elementi dell’insieme.
• Sarebbe possibile utilizzare la stessa tecnica ma con una
complessita’ spaziale molto minore (nel caso di universi
grandi o infiniti), piu’ vicina alla cardinalita’ del singolo
insieme che a quella dell’universo?
Anche nel caso in cui il valore degli elementi dell’universo
non e’ utilizzabile come indice in un array?
10
Tabelle hash
• In una rappresentazione a stringa di bit la locazione dell’elemento x
nella stringa e’ identificata dal valore stesso di x.
• In una tabella hash (HT) la locazione dell'elemento x nella tabella
e' identificata tramite il calcolo di una opportuna funzione hash(x)
che dice a quale indice si dovrebbe trovare l'elemento.
• L'elemento x deve essere inserito nella HT all'indice hash(x)
• Se l'elemento x e' presente nella HT, esso si trova all'indice
hash(x)
• Da cio' discende che una HT deve essere costituita da una struttura
contigua di memoria indicizzabile (un array di celle, o bucket) e
accedibile in modo random
 una HT e' costituita da b bucket consecutivi
• Ogni bucket della HT puo' in generale contenere s elementi, con
s1
 il numero s puo' essere limitato a priori o illimitato
11
Dimensioni e loro relazioni
• Perche' si considera che debba/possa essere s>1?
• La funzione hash() mappa l'insieme di tutti i possibili elementi
dell'universo U considerato (e.g. gli identificatori utilizzabili in un
programma C) sul range di interi 0..b-1.
• Sia #U la dimensione di questo universo. Di norma:
• #U e' molto grande, o addirittura infinito
• il numero n di elementi di U effettivamente considerati ogni
volta e' molto minore di #U
• #U >> b (conseguenza dei punti precedenti)
• Notazione:
• il rapporto n / #U e' chiamato densita' degli elementi
• il rapporto  = n / (s*b) e' chiamato densita' o fattore di
carico della tabella
• in caso s sia illimitato si definisce  = n / b
12
Collisione e overflow
• Poiche' #U>>b la funzione hash() sara' necessariamente tale da
mappare molti elementi di U sullo stesso bucket.
• Due elementi i1 e i2 tali per cui hash(i1)=hash(i2) sono detti essere
sinonimi.
• Non si puo' ovviamente forzare nessuna disciplina che impedisca
l'utilizzo di elementi sinonimi.
 in effetti di norma e’ impossibile sapere a priori se due elementi
sono sinonimi.
• Quando capita effettivamente che due elementi utilizzati siano
mappati sullo stesso bucket si dice che c'e' stata una collisione.
• In caso di collisione gli elementi possono essere comunque registrati
nel bucket purche' il loro numero non ecceda s.
• Nel caso piu' di s elementi effettivamente utilizzati siano mappati su
uno stesso bucket si dice che c'e' stato overflow.
• Ovviamente perche' ci possa essere overflow s non deve essere
illimitato.
13
• Se s=1 c'e' overflow tutte le volte che c'e' collisione.
Requisiti per un accesso efficiente
• perche' l'accesso ad una HT sia efficiente bisogna che il numero di
collisioni sia limitato.
 infatti se ci sono molte collisioni su un bucket, quando cerco un
elemento in quel bucket non mi basta un semplice confronto.
 Le operazioni non sono piu’ O(1)!
• se anche s e' molto grande o illimitato, il fattore di carico della
tabella deve essere contenuto.
 infatti, se il fattore di carico e' elevato, e' piu' probabile che ci
siano collisioni.
• la funzione hash() deve essere tale da minimizzare la probabilita' di
collisione a parita' di fattore di carico.
 ma dato che il rapporto b/#U e' di solito molto piccolo e' chiaro
che non e' possibile evitare collisioni.
• la funzione hash() deve anche essere semplice da calcolare.
14
Dimensioni di una HT
• Il fattore di carico puo’ essere minimizzato aumentando b, il numero
di bucket dell’HT.
• Gli unici vincoli a questo aumento sono:
• il costo in termini di spazio
• l’aumento del tempo per creare e distruggere l’HT.
• Le HT non prevedono infatti operazioni che possano richiedere una
scansione di tutti i bucket.
• Non e’ ad esempio pensabile una operazione di enumerazione
degli elementi contenuti in una tabella.
Infatti gli elementi non sono recuperabili in forma ordinata.
• E’ una differenza significativa rispetto al caso dei bidoni
utilizzati per radix sort, dove l’algoritmo prevedeva una loro
scansione, e poneva quindi un limite alla convenienza di un
loro aumento.
15
Funzione hash()
• Deve avere le seguenti proprieta':
• dipendere dall'intero valore dell'elemento e non solo da una
sua parte.
e.g. se gli elementi sono identificatori, non deve dipendere
solo dai primi o dagli ultimi caratteri ma da tutta la stringa.
• se x e' un elemento a caso di U allora la probabilita' che
hash(x)=k deve essere 1/b per tutti i b bucket k (0kb-1).
• in questo modo ogni elemento x di U ha uguale probabilita' di
essere mappato su ciascuno dei b bucket della HT.
Una funzione hash che abbia questa proprieta' e' detta
essere uniforme.
• Esistono diverse funzioni hash ben definite:
• MD4, MD5 (RFC 1321) e SHA-1 (NIST - FIPS PUB 180)
utilizzati nella network security
• funzioni non-standard piu' semplici basate su XOR (o
somma), modulo di numeri primi, quadrati, . . .
16
Funzione hash() e dimensioni della tabella
• Fra funzione hash() e dimensione b della tabella c'e'
evidentemente una relazione, dato che la funzione hash() deve
ritornare un intero k tale che 0k<b.
• Le proprieta' computazionali della funzione hash() possono quindi
imporre dei limiti sul valore di b.
• se hash(x) = x % b, allora
• e' conveniente che b sia un numero primo
• se fosse una potenza di 2 l'operazione di modulo
equivarrebbe a considerare solo i bit piu' leggeri di x
• se hash(x) = x2 / 2m % 2k, allora
• b = 2k, cioe' b risulta essere una potenza di 2
• Esercizio: come e’ fatto x2 / 2m % 2k?
17
Gestione dell'overflow: linear open addressing
• In ogni caso deve essere definita una politica per la gestione
della condizione di overflow.
• Nel caso s sia illimitato si considera convenzionalmente come
situazione di overflow l'evento di collisione.
• Consideriamo il caso s limitato, e per comodita' sia s=1.
• Una prima condizione per riconoscere l'evento di collisione/
overflow e' che un bucket/slot sia riconoscibile come (non) vuoto:
si assume che questo sia possibile.
• In caso di collisione nell'inserire l'elemento x la politica di linear
open addressing specifica:
1. Si cerca sequenzialmente e circolarmente nella HT, a partire
da hash(x), il primo bucket vuoto.
2. Li' si inserisce x.
3. Se non si riesce a trovare un bucket vuoto prima di riscandire circolarmente il bucket hash(x) cio' significa che la
HT e' piena e non piu' utilizzabile.
18
Gestione dell'overflow: linear open addressing
• Come e' in questo caso l'algoritmo di ricerca di un elemento nella
HT?
elemento HT[b];
boolean HTcontains(elemento e) {
int baseScan = hash(e);
if (!isEmpty(HT[scan] && HT[baseScan]==e)
return (TRUE);
else {
for (int scan = (baseScan+1) % b;
scan!=baseScan; scan = (scan+1) % b) {
if (isEmpty(HT[scan])) return (FALSE);
if (HT[scan]==e) return (TRUE);
}
return (FALSE);
}
}
19
Gestione dell'overflow: linear open addressing
• Quando si utilizza questa politica nella HT tendono a formarsi
gruppi (cluster) di elementi.
• I gruppi di elementi tendono anche ad auto-alimentarsi e a
fondersi tra di loro, cosi' che il numero di confronti eseguiti dalla
funzione di ricerca tende a crescere.
• Il numero di confronti necessario a verificare la presenza di un
elemento non e' piu' quindi O(1) come desiderato.
• In effetti risulta che il numero medio atteso di confronti tra
elementi per verificare la presenza di un elemento (che e’
effettivamente presente) e':
2
22*
• Questo nell'ipotesi di scelta casuale degli elementi che sono
presenti nella HT e di uniformita' della funzione hash.
• Non solo la complessita' media e' elevata; il caso peggiore e'
O(n)!
20
Gestione dell'overflow: linear open addressing
• Sono stati utilizzati vari metodi per cercare di risolvere i problemi del
linear open addressing pur continuando a gestire l'overflow all'interno
della HT:
• quadratic probing: anziche' inserire/cercare in bucket
consecutivi si cerca in bucket distanziati successivamente di k2 in
modo da limitare il fenomeno del raggruppamento.
• rehashing: i bucket successivi sono cercati utilizzando una
sequenza di diverse funzioni hash.
• La politica di open addressing presenta anche un altro problema:
 Come e' possibile cancellare elementi dalla HT?
• E' evidente che non e' sufficiente dichiarare empty un bucket:
•
quel bucket potrebbe essere stato "saltato" perche' pieno
durante l'inserzione con overflow di un altro elemento, e
•
settarlo vuoto farebbe fallire la funzione HTcontains()
definita prima.
21
Gestione dell'overflow: chaining o external clash list
• Il problema fondamentale della politica di open addressing e' che
la ricerca di un elemento puo' implicare il coinvolgimento anche di
elementi che non sono sinonimi di quello cercato.
• Questo problema viene eliminato se creiamo bucket di
dimensione s illimitata.
• Questo puo' essere fatto facilmente realizzando il bucket tramite
una lista (chaining o external clash list):
 un bucket della HT e' effettivamente costituito solo della
testata della lista degli elementi sinonimi mappati su quel
bucket.
• Nella ricerca di un elemento e' necessario confrontarlo con gli
elementi che sono contenuti nel bucket su cui esso e' mappato
dalla funzione hash, cioe’ con elementi che sono suoi sinonimi.
• L'inserimento nella lista del bucket non richiede alcuna speciale
disciplina:
 la lista puo essere una lista LIFO semplicemente linkata.
22
Gestione dell'overflow: chaining o external clash list
• In questo caso il numero medio atteso di confronti tra elementi per
verificare la presenza di un elemento risulta essere (nell'ipotesi di
scelta casuale degli elementi che sono presenti nella HT e di
uniformita' della funzione hash):
• per un elemento presente in tabella:
• per un elemento non presente in tabella:

 1
2

dove, come gia' detto, e' =n/b.
(infatti in ogni lista sono presenti in media  elementi, che devono
essere scanditi tutti nel caso di elemento non presente in tabella,
in media solo meta' nel caso di elementi presenti in tabella)
• Nota che un ulteriore vantaggio di questo metodo e' che, e' vero
che richiede l'allocazione dei link per la gestione delle liste, ma
richiede l'allocazione all'interno della HT solo delle testate di lista,
in genere di dimensione molto minore di quella degli elementi.
• Anche l'operazione di cancellazione non presenta difficolta'.
23