Hash table

Con array/liste è facile implementare tante operazioni da fare.

Con ciascuna di queste strutture certe operazioni hanno complessità O(N)

Le tabelle hash hanno solo operazioni di base, ma ciascuna di queste ha costo

costante!

Tavola a indirizzamento diretto

è una idea preliminare rispetto alla tabella hash.

Immaginiamo di avere U come universo delle chiavi U = {0, 1, ..., m − 1}

💡 se le chiavi non sono degli interi consecutivi allora bisogna

trasformarle con qualche funzione

L’insieme dinamico viene rappresentato con un array T di dimensione m in cui

ogni posizione corrisponde ad una chiave.

Per questo motivo viene chiamata tavola a indirizzamento diretto, accedere a

ciascun elemento è una operazione infatti che costa O(1)

Esempio:

Siccome l’universo delle chiavi va da 0 a 9, abbiamo 10 elementi nell’array T e

ciascuno di questi può puntare ad un dato che ha una chiave corrispondente oppure

Hash table 1
 ad un NIL (elemento nullo).
Le operazioni in una tavola a indirizzamento diretto sono semplicissime!

💡 Ovviamente tutte le operazioni hanno tempo costante O(1)

💡 La ricerca di un elemento con chiave k restituisce semplicemente

l’elemento T[k] che può essere nil oppure contiene l’elemento desiderato

Sembra una struttura molto efficiente, ma dal punto di vista dello spazio può
non risultare efficiente!

Infatti la quantità di memoria occupata dalla struttura dati dipende dai contesti in
cui viene utilizzata, se la tabella è molto grande rispetto alla quantità di dati
memorizzati realmente, la struttura non sarà efficiente.

Ad esempio, ipotizziamo di usare una tabella a indirizzamento diretto per

rappresentare studenti identificati da una matricola di 6 cifre, quindi abbiamo 106
possibili chiavi.

Quindi, ipotizzando che un puntatore occupi 8 byte, T occuperà 8 ∗ 106 byte di

memoria

Di ogni studente inoltre si memorizza 105 byte di dati, ossia 100kb

Immaginiamo di avere 20000 studenti

Lo spazio occupato ma non usato (ossia i nil) :

8 ∗ (106 − 20000) = 7840000B = 7.84MB

La percentuale di spazio sprecato rispetto allo spazio totale sarebbe:

Hash table 2
 Ossia circa lo 0.4%

💡 Quindi in questo esempio specifico lo spazio sprecato è accettabile, e la

struttura può essere implementata.

Ma se memorizzassi soltanto 1kb di dati per ciascuno studente:

Quindi il 28% della memoria è occupata inutilmente!

E se abbasso il numero di studenti da 20000 a 200

Ossia il 95.6% della memoria è occupata inutilmente!

💡 In questi due ultimi casi , la struttura dati non è ragionevole come scelta, è
troppo costosa dal punto di vista dello spazio per implementarla!

Tavole hash
Quindi, l’indirizzamento diretto non è realizzabile se l’universo delle chiavi è troppo
grande

in ogni caso non è efficiente dal punto di vista della memoria utilizzata, può
capitare che troppa memoria sia usata per i puntatori nil.

L’idea è quella di utilizzare una tabella T con dimensione m con dimensione

molto più piccola di ∣U∣

Hash table 3
 Non c’è più una corrispondenza diretta tra la posizione della tabella T e una
chiave di U , ma la posizione della chiave k è determinata usando una funzione:

Che viene chiamata funzione hash.

Esempio di tavola hash

💡 La funzione hash è definita come h(k) = k mod 5 ossia ogni posizione

nella tabella è determinata dal resto della chiave k con 5, perchè l’array ha
5 posizioni

Quindi nel caso delle tavole hash l’indirizzamento non è più diretto.

L’elemento con chiave k si trova nella posizione h(k)

Come conseguenze della tabella hash abbiamo:

riduciamo lo spazio utilizzato.

ma si perde la diretta corrispondenza fra chiave e posizioni, e l’universo ha un

numero di elementi maggiore della lunghezza di T, di conseguenza due chiavi
possono corrispondere alla stessa posizione nell’array T.

quindi possono esserci delle collisioni!

Hash table 4
 💡 Nell’esempio precedente, le coppie (0, 5), (1, 6), (2, 7), (3, 8) sono in
collisione! infatti il resto della divisone per 5 è uguale per i due elementi
della coppia!

Una buona funzione di hash cerca di tenere al minimo il numero di collisioni,

posiziona le chiavi in 0, 1, ..., m − 1 in modo uniforme, per ridurre al minimo le
collisioni!
L’hash perfetto sarebbe una funzione che non crei mai collisioni, ossia una funzione
iniettiva:

= k2 ⟹ h(k1 ) 
k1  = h(k2 )

Ma se ∣U∣ > m allora l’hash perfetto si può realizzare solo se l’insieme da

rappresentare non è dinamico! In tutti gli altri casi non esiste l’hash perfetto.

Gestione delle collisioni

Come si gestiscono le collisioni?
Una possibile soluzione è concatenare gli elementi in collisione in una lista!

Esempio:

💡 Sicuramente le chiavi 2 e 7 andranno in collisione tra loro, perchè il resto

di questi due numeri per 5 è 2!

Ogni volta che un elemento va in collisione, si inserisce nella lista puntata dall’hash
dell’elemento, ma l’inserimento viene sempre effettuato in testa! In questo modo non
devo scorrere tutta la lista e ho O(1)

Hash table 5
 Operazioni nelle tavole hash con concatenamento:
Inserimento:

💡 La funzione ListInsert fa riferimento ad un inserimento in testa

dell’elemento x nella lista L!

💡 Con la funzione di hash h andiamo ad individuare la posizione nella

tabella T della lista che dovrà contenere l’elemento da inserire.

Ricerca:

Cancellazione:

💡 Le tre operazioni di base sono molto semplici , ma cosa si può dire

relativamente alla loro complessità?

Complessità delle operazioni in una tabella hash

Per individuare la lista, bisogna calcolare il valore hash di una chiave, e assumiamo
che il tempo di calcolo di hash sia costante, O(1)

Hash table 6
 La ricerca di un elemento di chiave k richiede del tempo proporzionale alla
lunghezza della lista ∣T (h(k))∣

Il costo della ricerca dipende quindi dal numero di elementi e dalle caratteristiche
della funzione hash.
Mentre per quanto riguarda la cancellazione, essa richiede O(1) perchè assumiamo
di aver già individuato l’elemento.

Costo di una ricerca:

Notazione:

m indica il numero di celle in T

N indica il numero di elementi memorizzati
N
α= m indica il fattore di carico della tabella hash.
Qual’è il caso peggiore per una ricerca in una tabella hash?
Immaginiamo di avere come universo delle chiavi tutte le matricole di 6 cifre, m =
200 e come funzione hash h(k) = k mod 200
Un possibile elenco di inserimento che rende successivamente pesante la ricerca è:

000123, 100323, 123723, 343123, 333123, ...

Infatti tutte queste chiavi sono associate alla stessa cella di T

Nel caso peggiore quindi la ricerca costa θ(N)

Mentre il caso migliore?

Quando la lista T (h(k)) è vuota oppure contiene un solo elemento, la ricerca in

questo caso ha costo O(1)

Mentre quale sarebbe il caso medio?

In realtà non possiamo dire nulla senza sapere come è fatta la funzione hash.

Assumiamo di avere una funzione che è facile da calcolare e gode della

proprietà di uniformità semplice, ossia la funzione hash distribuisce in modo
uniforme le chiavi tra le celle, tutte le posizioni della tabella hash sono
equiprobabili!

Ad esempio, questa funzione di hash è uniformemente semplice?

Hash table 7
 Il resto di una divisione per 10 corrisponde sempre all’ultima cifra della chiave.

l’ultima cifra appartiene a {0, 1, 2..., 9}

Ognuno di questi numeri appare 10 volte come ultima cifra, quindi in questo caso la
funzione è uniforme!
In questo caso invece:

La funzione hash è uniforme semplice?

La funzione di hash in questo caso calcola la somma delle cifre della chiave

h(k) = 0 per k = 0
h(k) = 1 per k = 1, k = 10
h(k) = 2 per k = 2, k = 11, k = 20
Quindi la funzione non è uniforme semplice! Ci sono infatti delle posizioni della
tabella T con più elementi rispetto ad altre!

💡 Se la funzione di hash fosse uniforme semplice, la successione

rappresentata nel grafico sarebbe piatta.

Caso medio con hashing uniforme semplice

In media, quanti elementi ci sono in una lista?

Hash table 8
 chiamiamo ni il numero di elementi nella lista T [i] con i = 0, 1, .., m − 1
Il numero medio di elementi in una lista è

Tempo medio per cercare un elemento che non c’è:

Il tempo per individuare la lista è θ(1)

Ogni lista ha la stessa probabilità di essere associata con la chiave

la lista ha in media α elementi, quindi per percorrere tutta la lista θ(α)

Il tempo richiesto mediamente da una operazione di ricerca di un elemento assente

nella tabella è θ(1) + θ(α) = θ(α)

💡 Attenzione! il valore di α non è costante! infatti dipende dal numero di

elementi presenti nella tabella, questo valore è variabile! (siccome le
nostre strutture dati sono dinamiche)

💡 Però possiamo immaginare che m sia scelto in modo che α sia quasi
costante

Tempo medio per cercare un elemento presente nella lista:

In questo caso, a differenza di prima, non necessariamente dobbiamo percorrere

completamente la lista, il numero di elementi da esaminare dipende da dove si trova
l’elemento cercato, ad esempio se l’elemento cercato è in prima posizione dobbiamo
valutare solo un elemento, se invece si trova in ultima posizione dobbiamo scorrere
l’intera lista!

Assumiamo che la ricerca riguardi un elemento scelto a caso:

Il tempo per individuare la lista è sempre θ(1)

Assumiamo che la ricerca riguarda l’i-esimo elemento inserito, xi

per trovare xi dobbiamo esaminare xi stesso e tutti gli elementi che sono stati
inseriti dopo xi e hanno una chiave con stesso valore di hash di xi !

Hash table 9
 Quanti elementi tali ci sono?

Dopo xi si inseriscono N − i elementi

ma quanti di questi finiscono nella stessa lista di xi ?

Siccome la funzione è uniforme semplice, ogni elemento viene inserito nella

1
lista xi con probabiltà m

In media abbiamo Nm−i elementi nella stessa lista di xi

Quindi il tempo di ricerca per xi è proporzionale a

💡 il valore 1 indica il tempo per individuare la lista esatta.

Se generalizziamo il nostro ragionamento e al posto di xi prendiamo un elemento a

caso, il tempo per ricercare un elemento scelto a caso è:

💡 1
La sommatoria è moltiplicata per N per far si che ciascun elemento a
caso sia equiprobabile nella somma totale!

Se elaboriamo la quantità precedente, in particolare scomponendo le somme nella

parentesi:

La prima e la seconda sommatoria contiene termini che non dipendono da i, quindi

sommiamo lo stesso termine N volte.
1

Hash table 10
 1
La prima sommatoria vale quindi N ∗N =1
1 N N
La seconda vale N ∗N∗ m = M
Mentre la terza , essendo una serie aritmetica diventa

In definitiva otteniamo:

E dividendo l’ultima frazione otteniamo:

α α
1+ −
2 2N
Il tempo di calcolo può essere scritto come
α α
θ(1) + θ(1 + 2
− 2N
) = θ(1 + α)
Quindi esattamente come nel caso in cui l’elemento non è presente, il tempo di
calcolo della ricerca nel caso migliore è proporzionale al valore α

Ma cosa vuol dire nella pratica θ(1 + α)?

Se il numero di celle in T è proporzionale a N , allora N = O(m) e quindi

α = O(1), la ricerca in questo caso richiede tempo costante!
E, facendo l’ipotesi di prima, tutte e tre le operazioni costano O(1)

Come trovare una buona funzione hash

Il significato della parola hash, per quanto riguarda gli algoritmi, è combinare /
utilizzare tutte le informazioni della chiave!
Inanzitutto una buona funzione hash è uniforme semplice.

Ma questa proprietà è difficile da verificare, perchè dipende da quali chiavi saranno

usate.

Hash table 11
 Finora abbiamo interpretato le chiavi sempre come numeri naturali ed effettivamente
ogni chiave è una sequenza di bit!
E nella funzione hash si cerca di far si che ogni bit della chiave entri “in gioco”

Una buona funzione hash sceglie le posizioni da assegnare in modo da eliminare

eventuale regolarità nei dati

Metodo della divisione

Il metodo della divisione assegna alla chiave k la posizione:

h(k) = k mod m
è molto veloce, ma bisogna fare attenzione a m!
Esempio:

immaginiamo di assegnare la posizione tramite il metodo della divisione a delle

stringhe, rappresentato con il codice ascii, ad esempio possiamo trasformare la
parola oca in un numero nel seguente modo:

In questa maniera traduciamo ogni stringa in un numero

Ma, da questa tabella si evince che il valore di m conta molto:

💡 Tutte le parole scelte terminano con “le” , e avendo m

parole sono associate alla posizione 1637
= 2048 tutte le

💡 Mentre con m = 1583 le 4 parole vanno tutte in posizioni diverse!

Hash table 12
 Infatti, se si usa m= 2p , entrano in gioco solo le due ultime lettere della parola,
quindi si può scegliere m in questo modo soltanto se si ha la certezza che gli ultimi
bit hanno una distribuzione uniforme , per le parole italiane non va certamente bene!

Invece un numero primo non vicino ad una potenza di 2 è spesso una buona scelta (
m = 1583)

Metodo della moltiplicazione

Avendo 0 < A < 1

h(k) = [m(Ak mod 1)]

Con x mod 1 che indica la parte frazionaria di x.

Con questa tecnica il valore di m non è critico e di solito viene scelta una potenza di
2.

La scelta ottimale di A dipende dai dati, ma secondo alcune stime e ricerche A =

5 −1
2
Esempio con 4 parole:

Avendo 4 parole piuttosto simili tra loro abbiamo 4 valori differenti di hash!

Indirizzamento aperto
Rispetto a prima, con l’indirizzamento aperto tutti gli elementi sono memorizzati nella
tavola T
In generale, l’elemento con chiave k viene inserito nella posizione h(k) se essa è
libera
Se invece la posizione h(k) non è libera, allora si cerca una posizione libera in base
ad uno schema di ispezione, che esamina altre posizioni fino a quando non si trova
una cella libera.

Hash table 13
 Lo schema di ispezione più semplice è la cosiddetta ispezione lineare: a partire
dalla posizione h(k) l’elemento con chiave k viene inserito nella prima cella
libera!

Esempio

💡 Ad esempio, la chiave 2 va in
collisione con la chiave 12,
quindi il valore 2 viene
inserito tramite l’ispezione
lineare, e viene scelta la
posizione 3 visto che è libera!
Anche 22 va in collisione
siccome la posizione 2 è
occupata, e siccome anche la
3 è occupata la chiave 22
viene inserita in posizione 4.

Si osserva che con questa tecnica anche chiavi con hash diversi possono andare in
collisione, non è detto che una chiave si trovi nella posizione indicata dalla tabella
hash

Estensione della funzione hash

In generale l’indirizzamento aperto può essere descritto tramite una funzione hash
estesa con l’ordine di ispezione:

h : U ∗ {0, 1, 2, ..., m − 1} → {0, 1, 2, ..., m − 1}

Infatti un elemento al massimo può subire m − 1 collisioni

Hash table 14
 In generale, un elemento con chiave k viene inserito:

Nella posizione h(k, 0) se questa è libera

altrimenti nella posizione h(k, 1) se questa è libera

e cosi via…

L’ispezione è lineare se

h(k, i) = (h′ (k) + i) mod m

Dove h′ (k) è la funzione di hash “normale”

💡 il mod m serve per rendere la lista “circolare”, ossia per riuscire a

ricomincare a ispezionare la lista dal primo elemento quando gli elementi
sono finiti.

Inserimento in tabella hash con indirizzamento aperto

💡 l’indice i ci serve per tenere conto delle collisioni “subite”

💡 L’algoritmo, oltre a effettuare l’inserimento, ritorna anche la posizione in

cui è stato inserito l’elemento di chiave k

Hash table 15
 Ricerca in tabella hash con indirizzamento aperto

💡 Come prima, l’indice i ci serve per tenere conto delle collisioni

💡 La ricerca da esito nil quando l’elemento con chiave k non è presente

nella tabella, questo accade quando troviamo nella posizione cercata una
casella vuota, oppure quando i supera m
Se invece viene trovato l’elemento con chiave k in posizione j, si ritorna
T[j]

💡 Per questo motivo, dobbiamo assumere che non ci siano buchi nella
tabella e che non sia possibile la cancellazione di un elemento!

Problema della cancellazione in una tabella hash a

indirizzamento aperto
Nel caso in cui permettessimo la cancellazione in una tabella hash a indirizzamento
aperto, andremo a rovinare l’operazione di ricerca, quindi per cancellare un
elemento non possiamo marcare la posizione con un nil.
L’idea per risolvere questo problema è implementare una costante deleted per
indicare che un elemento è stato cancellato cancellato.

Ma per fare questo bisognerebbe cambiare la funzione di inserimento.

Hash table 16
 💡 Nella pratica, l’indirizzamento aperto si usa quando non c’è necessità di
cancellare.

Possibili schemi di ispezione

Il problema dell’ispezione lineare è che si creano delle file di celle occupate, questo
fenomeno viene chiamato addensamento primario, ed è un problema per gli
inserimenti!
Un altro schema di ispezione è l’ispezione quadratica:

h(k, i) = (h′ (k) + c1 i + c2 i2 ) mod m

Come prima, i è il numero di collisioni già subite, ma in questo caso l’ordine di

ispezione delle celle dipende soltanto dalla chiave k , se due elementi hanno h′ (k)
uguale , allora verranno restituiti due valori uguali! questo è il cosidetto
addensamento secondario
Per evitare questo problema , si introduce il cosidetto doppio hashing:

h(k, i) = (h1 (k) + ih2 (k)) mod m

In questo caso, due chiavi con stesso valore di h1 non avranno in generale stesso
valore di h(k, i)!

Complessità di ricerca con indirizzamento aperto

Consideriamo il caso ottimale dal punto di vista della funzione hash e lo schema di
ispezione:

Assumiamo che la posizione di una chiave scelta a caso abbia distribuzione

uniforme.

Inoltre, qualunque sequenza di ispezione ha la stessa probabilità (nella pratica si

può ottenere questo solo con il doppio hashing)

Consideriamo, dal punto di vista della ricerca, il caso in cui l’elemento sia assente ,
che corrisponde al caso peggiore!

Denotiamo quindi con X il numero di celle esaminate durante una ricerca senza
successo
Assumendo che la chiave assente sia scelta a caso, è ovvio che X sia casuale
(variabile aleatoria), e ovviamente vale almeno 1 , quindi P (X ≥ 1) = 1.

Hash table 17
 Qual’è la probabilità di esaminare almeno due celle? questo accade quando la
prima cella non è un nil, ma questo è N/m , infatti nella tabella sono occupate N
celle su m totali.
N
quindi P (X ≥ 2) = m
E la probabilità di esaminare almeno tre celle?
N N −1
P (X ≥ 3) = m
∗ m−1
In generale, la probabilità di esaminare almeno i celle è :

N N −1 N −i+2
P (X ≥ i) = ∗ ... ∗
m m−1 m−i+2
Siccome a noi interessa porre un limite superiore e ciascun elemento del prodotto è
minore di α, possiamo dire che

P (X ≥ i) ≤ ai−1
Ora, ci interessa il valor medio della variabile aleatoria X che indico con E[X]

💡 infatti la sommatoria infinita di ai−1 corrisponde ad una serie geometrica,

che converge a 1−α
1

Ad esempio, se α = 0.5 ossia metà dell’array è pieno, in media servono 2

confronti!

se invece α = 0.75, allora in media serviranno 4 confronti.

Ovviamente, nel caso di una ricerca con successo vengono esaminate meno celle.

💡 più α assume valori vicini ad 1 e più confronti dovrò fare.

Anche l’inserimento si analizza con lo stesso approccio.

Hash table 18