!
!
Introduzione
Algoritmi e Strutture Dati
✦
Dizionario (reloaded):
✦
!
Capitolo 7 - Tabelle hash
!
!
!
Alberto Montresor
✦
Università di Trento
!
!
!
✦
Il valore è un “dato satellite”
✦
Dati indicizzati in base alla chiave
✦
Operazioni: insert(), remove() e lookup()
Applicazioni:
✦
✦
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
1
© Alberto Montresor
Introduzione
u
a
int
La gestione della memoria nei sistemi operativi
b
double
2
© Alberto Montresor
Array
non ordinato
Array
ordinato
Lista
O(1)
O(n)
O(1)
Alberi
Performance
(abr, rb, ...)e
ideale
✦
U – Universo di tutte le possibili chiavi
✦
K – Insieme delle chiavi effettivamente memorizzate
✦
Possibili implementazioni
✦
O(log n)
O(1)
lookup()
O(n)
O(log n)
O(n)
O(log n)
O(1)
remove()
O(n)
O(n)
O(n)
O(log n)
O(1)
|U| corrisponde al range [0..m-1], |K| ~ |U| →
✦
✦
© Alberto Montresor
Le tabelle dei simboli di un compilatore
Notazione
Possibili implementazioni e relativi costi
insert()
Struttura dati per memorizzare insiemi dinamici di coppie (chiave, valore)
U è un insieme generico, |K| << |U| →
✦
3
tabelle ad indirizzamento diretto
© Alberto Montresor
tabelle hash
4
Tabelle a indirizzamento diretto
✦
Implementazione:
✦
✦
✦
✦
U
Basata su vettori ordinati
L'elemento con chiave k è memorizzato nel k-esimo “slot”del vettore
K
k0
k1
k3
k5
k2
3
k4
Se |K| ~ |U|:
✦
Non sprechiamo (troppo) spazio
✦
Operazioni in tempo O(1) nel caso peggiore
Se |K| << |U|: soluzione non praticabile
✦
0
Tabelle
(j + 1)/m, contro
unahash
probabilità di 1/m nel caso che la posizione precedente fosse anch’essa
libera! In particolare, quando il vettore è quasi Algoritmi
completamente
occupato,
122
e Strutture
di Dati diviene pressoché
U
✦ Tabelle hash:
nil
H(k1)
impossibile evitare il formarsi di agglomerati ed il tempo per inserimenti e ricerche di chiavi
k1tende a crescere ✦linearmente
con
la che
dimensione
mprecedente
del vettore.
Inoltre, se il vettore si riempie
Undivettore
A[0..m-1]
H(k4)
k1 fossekanch’essa
(j + 1)/m,
contro una probabilità
1/m nel
caso
la posizione
4
completamente,
non
è
ovviamente
più
possibile
alcuna
ulteriore
inserzione.
nil
libera! In particolare, quando
il vettore
è quasi
completamente
occupato, diviene
pressoché
k2
✦ Una
funzione
hash
K
Ricapitolando,
per
realizzare
efficientemente
un
dizionario
con
tabella hash:
k5una
impossibile
evitare
il
formarsi
di
agglomerati
ed
il
tempo
per
inserimenti
e
ricerche
di
chiavi
k
H(k ),H(k )
H: U → {0,..,m-1}
Esempio: studenti ASD con chiave “n. matricola”
2
5
k3
tende a crescere linearmente con la dimensione m del vettore. Inoltre, se il vettore
si riempie
collisione
nil
(1)
occorre
una
funzione
H,
detta
appunto
funzione
hash,
che
sia calcolabile velocemente
(in
completamente, non è ovviamente
più possibile
alcuna
ulteriore
inserzione.
✦ Indirizzamento
hash:
e che
distribuiscaunledizionario
chiavi uniformemente
nel vettore A, al fine di ridurre
k5 tempo
H(kil
Ricapitolando,
perO(1))
realizzare
efficientemente
con una tabella hash:
3)
Diciamo
H(k)diverse
è il valore
della
chiaveindirizzo
k
numero di collisioni
tra che
chiavi
che hash
hanno
lo stesso
hash;
✦
(1) occorre una funzione H, detta appunto funzione hash, che sia calcolabile velocemente (in
✦ Chiave
viene “mappata”
nello slot
A[H(k)]
(2) occorre un metodo
di kscansione,
per reperire
chiavi
che hanno trovato la loro posizione
tempo O(1)) e che distribuisca le chiavi uniformemente nel vettore A, al fine di ridurre il
m–1
chiave
che
permetta
di
tutto
il vettore
A e non
✦ Quando
numero dioccupata,
collisioni tra
chiavi
diverse
cheoesplorare
hanno
lo stesso
indirizzo
hash;
due
più chiavi
nel dizionario
hanno
lo provochi la formazione di
di stesso
chiavi;per
(2) occorre unagglomerati
metodo di scansione,
reperire
che che
hanno
trovato launa
lorocollisione
posizione
valore
hash,chiavi
diciamo
è avvenuta
occupata,
permetta dim
esplorare
tuttoAil deve
vettore
A e una
non sovrastima
provochi la formazione
(3) lache
dimensione
del vettore
essere
del numerodidi chiavi attese, onde
valore
Idealmente:
vogliamo funzioni hash senza collisioni
agglomerati
di chiavi;
evitare
di✦ riempire
A completamente.
(3) la dimensione m del vettore A deve essere una sovrastima del numero di chiavi attese, onde
evitare di riempire A completamente.
7.1 Funzioni hash
© Alberto Montresor
Problema delle collisioni
✦
Utilizzo di funzioni hash perfette
✦
Una funzione hash H si dice perfetta se è iniettiva, ovvero:
8u, v 2 U : u 6= v ) H(u) 6= H(v)
!
✦
✦
Si noti che questo richiede che m ≥ |U|
Esempio:
✦
Studenti ASD 2014/2015 - N. matricola in [131.578, 173.141]
✦
✦
✦
H(k) = k - 131.58, m = 41.563 (ancora troppo grande!)
7.1 Funzioni
hash
5
©una
Alberto Montresor
Trovare
buona funzione hash non è semplice; essa deve ricavare l’output (un numero
intero)
che sia
scorrelato
dalla
struttura essa
dell’input
(la chiave
stessa).
Da qui il termine “hash”,
Trovare
una buona
funzione
hash non
è semplice;
deve ricavare
l’output
(un numero
Funzioni
hashdell’input (la chiave stessa). Da qui il termine “hash”,
intero) che
sia
scorrelato
dalla
struttura
che in Inglese significa “tritare” o “polpetta”: si sminuzza la chiave in pezzettini che sono
che in Inglese
significain“tritare”
o “polpetta”:
sminuzza
chiave
in “casuale”
pezzettini che
sono Ovviamente l’alrimescolati
modo da
formare unsi intero
chelasia
il più
possibile.
✦
Se le collisioni
sono
rimescolati in modo da formare
che
siainevitabili
il più “casuale” possibile. Ovviamente l’algoritmo che calcola un
la intero
funzione
hash
non è casuale, in quanto se si ricalcola più volte H(k)
goritmo che calcola la funzione
hash
non
è
casuale,
quanto se siilricalcola
più volte H(k)
✦ almeno cerchiamo diin
minimizzare
loroma
numero
per
la
stessa
chiave
k
si
ottiene
sempre
lo
stesso
valore,
l’indirizzo
hash si comporta da un
per la stessa chiave k si ottiene sempre lo stesso valore, ma l’indirizzo hash si comporta da un
✦ vogliamo
punto
di vistacome
statistico
se fosseche
stato
davvero
unodile
ouna
più
lanci
casuali
distribuiscano
uniformemente
chiavi
negli
indicidi una
punto di vista
statistico
se fossecome
statofunzioni
davvero
prodotto
con uno prodotto
o più
lancicon
casuali
[0...m-1] della tabella hash
moneta. moneta.
Una buonaUna
funzione
deve minimizzare
numero di collisioni
presenti
nel sistema;presenti nel sistema;
buonahash
funzione
hash deveilminimizzare
il numero
di collisioni
✦ Uniformità semplice:
uno dei possibili
criteri
per
definire
questa
proprietà
è
detto
uniformità
semplice:
detta
P (k)semplice:
la
uno dei possibili criteri per definire questa proprietà è detto uniformità
detta P (k) la
✦sia
probabilità
che
una
chiave
k
inserita
nella
tabella,
sia
P(k) la
unatabella,
chiavesia
k sia inserita nella tabella
probabilità che unasia
chiave
k probabilità
sia inseritache
nella
✦
sia Q(i) =
!
6
P (k) la probabilità che una chiave finisca nella cella i.
Q(i) =
P (k)
k:H(k)=i
k:H(k)=i
Studenti ASD 2015/2016, nati nel 2015 - N. matricola in [163.714-174.832]
la probabilità che una chiave qualsiasi finisca nella cella i. Una funzione H gode della proprietà
✦ Una funzione H gode della proprietà di uniformità semplice se
✦ H(k) = k - 163.714, m = 11.118 (ancora troppo grande!)
la probabilità
nella cella i. Una funzione H gode della proprietà
di uniformità
semplice seche
⇤i ⇥una
{0,chiave
. . . , m qualsiasi
1} : Q(i)finisca
= 1/m.
Per definire
funzioni semplice
hash, è conveniente
considerare
rappresentazione
binaria bin(k)
di uniformità
se ⇤i ⇥ {0,
. . . , m la1}
: Q(i) = 1/m.
Problema: spazio delle chiavi spesso grande, sparso, non conosciutodella chiave k.Per
Se la
chiave kfunzioni
non è numerica,
è data dalla
concatenazione
della rappredefinire
hash, èbin(k)
conveniente
considerare
la rappresentazione
binaria bin(k)
sentazionedella
binaria
di
ciascun
carattere
che
la
compone.
In
tutti
i
linguaggi
di
programmazione
✦ E' spesso impraticabile ottenere una funzione hash perfetta
chiave k. Se la chiave k non è numerica, bin(k) è data dalla concatenazione della rappre-
© Alberto Montresor
esiste una funzione primitiva (chiamiamola ord) che applicata ad un carattere, restituisce un
sentazione binaria di ciascun carattere che la compone. In tutti i linguaggi di programmazione
intero che è il numero ordinale del carattere nell’insieme dei caratteri ammessi. È altresı̀ utile
primitiva
(chiamiamola
ord) che
applicata
ad un
carattere, restituisce un
7unail funzione
© Alberto Montresor
denotare esiste
con int(b)
numero
intero
rappresentato
da una stringa
binaria
b. In questo
modo,
8
Funzioni hash
✦
✦
Per poter ottenere una funzione hash con uniformità semplice, la distribuzione
delle probabilità P deve essere nota
✦
✦
✦
✦
✦
Nella realtà
✦
La distribuzione esatta può non essere (completamente) nota
✦
Si utilizzano allora tecniche “euristiche”
✦
bin(k): rappresentazione binaria della chiave k, concatenando i valori
ordinali dei caratteri che lo compongono
valore numerico associato ad un numero binario b
✦
Shortcut: int(k) = int(bin(k))
Esempio:
bin(“DOG”) → ord(‘D’) ord(“O”) ord(“G”) → 01000100 01001111 01000111
int(“DOG”)) → 68 ⋅ 2562 + 79 ⋅ 256 + 71
→ 4.476.743
10
© Alberto Montresor
Funzioni hash - Estrazione
✦
ord(‘a’) = 1, ord(‘b’)=2, ..., ord(‘z’)=26, ord(‘b’)=32
✦
valore ordinale del carattere c
int(b):
✦
9
ord(c):
✦
✦
Nei prossimi esempi
✦
E' possibile trasformare una chiave complessa in un numero
U numeri reali in [0,1] e ogni chiave ha la stessa probabilità di essere scelta,
allora H(k) = bkmc
soddisfa la proprietà di uniformità semplice
Funzioni hash
Assunzioni
✦
b rappresenta lo spazio
✦
Sono sufficienti 6 bit per rappresentare questi caratteri
Si considerino le seguente due stringhe: “weberb” e “webern”
✦
Rappresentazione binaria
✦
m=2p
Come calcolare H(k)
✦
✦
H(k) = int(b), dove b è un sottoinsieme di p bit presi da bin(k)
Esempio:
✦
m =28 = 256, bit presi dalla posizione 15 alla posizione 22
✦
bin(“weberb”) =
010111 000101 000010 000101 010010 100000
✦
bin(“weberb”) =
010111 000101 000010 000101 010010 100000
✦
bin(“webern”) =
010111 000101 000010 000101 010010 001110
✦
bin(“webern”) =
010111 000101 000010 000101 010010 001110
✦
✦
Le chiavi sono valori numerici non negativi
✦
© Alberto Montresor
✦
Assunzioni:
Esempio:
✦
✦
Funzioni hash
Rappresentazione intera
✦
✦
da cui si ottiene:
int(“weberb”) = 23·645 +5·644 +2·643 +5·642 +18·641 +32·640 = 24.780.493.984
int(“webern”) =
© Alberto Montresor
23·645
+5·644
+2·643
+5·642
+18·641
+14·640
= 24.780.493.966
11
✦
H(“weberb”) = bin(00100001) = 33
✦
H(“webern”) = bin(00100001) = 33
!
!
© Alberto Montresor
12
(1) Estrazione: H(k) = int(b), dove b è un sottoinsieme di p bit di bin(k), solitamente estratti
Funzioni hash: metodo della divisione
nelle posizioni centrali;
(2) Xor: H(k) = int(b), dove b è dato dalla somma modulo 2, effettuata bit a bit, di diversi
✦ Assunzioni:
sottoinsiemi di p bit di bin(k);
✦ m dispari, meglio
(3) Moltiplicazione:
H(k) se
= primo
⇤m(iC ⇤iC⌅)⌅, dove m è un numero qualsiasi (le potenze di
2 vanno bene, anzi sono consigliate), i è int(bin(k)) e C è un numero reale, 0 < C < 1;
✦ Procedimento di calcolo
(4)
Divisione: H(k) è uguale al resto della divisione di int(bin(k)) per m.
Funzioni hash: XOR
✦
Assunzioni
✦
✦
Come calcolare H(k)
✦
✦
m=2p
H(k) = int(b), dove b è dato dalla somma modulo 2, effettuata bit a bit, di diversi sottoinsiemi di p bit di bin(k)
Esempio:
✦
m =28 = 256, 5 gruppi di 8 bit, 40 bit ottenuti con 4 zeri di “padding”
✦
✦
H(“weberb”)
= int(01011100⊕01010000⊕10000101⊕01001010⊕00000000)
= int(11000011) = 195
H(“webern”)
= int(01011100⊕01010000⊕10000101⊕01001000⊕11100000)
= int(00100001) = 33
© Alberto Montresor
Funzioni hash
✦
✦
✦ H(k) = k mod m
Esempio
7.4 (Funzioni hash). Si supponga che le chiavi siano di 6 caratteri alfanumerici.
Chiavi più lunghe sono troncate, mentre chiavi più corte sono espanse a destra con spazi. Si
✦ Esempio:
assuma
ord(A) = 1, ord(B) = 2, . . ., ord(Z) = 26 e ord(b) = 32, dove b indica lo spazio,
✦ m =383
con rappresentazione
di ogni ordinale su 6 bit. Per le chiavi Weberb e Webern si ottengono
le seguenti
36 bit, dove si sono
✦ rappresentazioni
H(“weberb”) =su24.780.493.984
modevidenziati
383 = 260per chiarezza i 6 gruppi di 6 bit
che rappresentano i caratteri della chiave:
✦ H(“webern”) = 24.780.493.966 mod 383 = 242
bin(Weberb) = 010111 000101 000010 000101 010010 100000
✦
Nota: il valore
m deve essere
scelto
opportunamente
bin(Webern)
= 010111
000101
000010 000101 010010 001110
Calcoliamo gli indirizzi hash ottenuti con le funzioni definite sopra
(1) Sia m = 256 = 28 . Estraendo gli 8 bit dalla posizione 15 alla 22 di bin(k), H(Weber) =
H(Webern) = int(00100001) = 33. Le due chiavi danno quindi luogo ad una collisione.
(2)
Sia ancora m = 256 = 28 e si calcoli b raggruppando bin(k) in cinque gruppi di 8 bit,
13
© Alberto Montresor
dopo aver espanso a destra bin(k) con quattro zeri in modo che bin(k) sia formato da 40
CAPITOLO 7. TABELLE
HASH = int(11000011) = 195 mentre H(Webern) = int(00100001)
123
bit. H(Weberb)
= 33.
Funzioni
hash: Moltiplicazione
(Knuth)
Infatti, indicando con ⇥ la somma bit a bit modulo 2, si ottiene:
14
Quattro metodi
di generazione
hash
sono i seguenti.
I primi⇥due
presuppongono
✦ Assunzioni
11000011di=indirizzi
01011100
⇥ 01010000
⇥ 10000101
01001010
⇥ 00000000
m = 2p , per qualche p; il terzo lavora bene con tutti i valori di m; il quarto presuppone m
✦ m=2p :
✦ m numero
00100001
= 01011100
⇥ 01010000
⇥ 10000101 ⇥ 01001000 ⇥ 11100000
solo i p bit più significativi vengono considerati
qualsiasi
(potenze
2 consigliate)
dispari (meglio se primo):
p hanno ✦ m=2p-1 :
✦
Benché
H(Webern)
sia uguale
nel caso (a), la collisione è stata eliminata.
permutazione di stringhe con set di caratteri di dimensione 2(1)
costante
0 < Ca<33,
1 come
Estrazione: H(k) C
=una
int(b),
dove breale,
è un sottoinsieme
di p bit di bin(k), solitamente estratti
(3) Poiché si usano 6 bit per rappresentare ciascun carattere della chiave, int(bin(Webern)) è
lo stesso valore hash
nelle posizioni
centrali;
✦ Procedimento di calcolo
interpretato come un numero in base 26 = 64.
✦ Domanda: Dimostrazione
(2) Xor: H(k) = int(b), dove b è dato dalla somma modulo 2, effettuata bit a bit, di diversi
✦ i = int(k)
i = int(bin(Webern))
sottoinsiemi di p bit
di bin(k);
Vanno bene:
128
Algoritmi
e Strutture di Dati
5
4 m è un
1 potenze0di
(3) Moltiplicazione:✦ H(k) = ⇤m(iC
dove
numero
= 23 · 64⇤iC⌅)⌅,
+ 5 · 64
+ 2 · 643 +
5 · 642qualsiasi
+ 18 · 64(le
+ 14 · 64
✦ Numeri primi, distanti da potenze di 2 (e di 10)
2 vanno bene, anzi sono consigliate),
i è int(bin(k))
C è+un
reale,
0 < C < 1;
= 64(64(64(64(23
· 64 +e 5)
2) numero
+ 5) + 18)
+ 14.
✦ Esempio
(4) Divisione: H(k) è uguale al resto della divisione di int(bin(k)) per m.
⇧
Sia
e m = 256. Allora
✦ C = (
Esempio 7.4 (Funzioni hash).5 Si1)/2
supponga
che le chiavi siano di 6 caratteri alfanumerici.
Non vanno bene:
Chiavi più lunghe sono
troncate,
mentre
chiavi
più
corte
sono
espanse
a destra con.. .spazi.
Si
✦ H(Webern)
= bm(iC
biCc)c
==
b256
· 0.9996833801
255.
H(Webern)
=
⇤m(iC
⇤iC⌅)⌅
⇤256
· 0.9996833801
. .c
.⌅ = 255.
assuma ord(A) = 1, ord(B) = 2, . . ., ord(Z) = 26 e ord(b) = 32, dove b indica lo spazio,
H(Weberb)
= bm(iC
biCc)c
= b256 · 0.1242942810 . . .c = 31.
Il calcolo
di H(Weberb)
è lasciato
per esercizio.
con rappresentazione di ogni ordinale su 6 bit. Per le chiavi Weberb e Webern si ottengono
le seguenti rappresentazioni su 36 bit, dove si sono evidenziati per chiarezza i 6 gruppi di 6 bit
che rappresentano i caratteri della chiave:
© Alberto Montresor
Il calcolo di H(Weberb) è lasciato per esercizio.
15 Siabin(Weberb)
©m
Alberto
= 010111 000101
000101
010010il100000
(4)
=Montresor
383. H(Webern)
= 242000010
è ottenuto
prendendo
resto della divisione per 383 di16
Funzioni hash
✦
Funzioni hash - continua
Come implementare il metodo della moltiplicazione:
✦
✦
Si scelga un valore m=2p
✦
Sia w la dimensione in bit della parola di memoria: i, m ≤ 2w
Sia s =
✦
i⋅s può essere scritto come r1 ⋅2w+ r0
✦
✦
✦
⎣C⋅2w⎦
✦
✦
r1 contiene la parte intera di iC
✦
r0 contiene la parte frazionaria di iC
Non è poi così semplice...
Il metodo della moltiplicazione suggerito da Knuth non è poi così buono....
Test moderni per valutare la bontà delle funzioni hash
✦
Avalanche effect:
✦
w bit
i
Ritorniamo i p bit più significativi di r0
×
Se si cambia un bit nella chiave, deve cambiare almeno la metà dei bit del
valore hash
✦
Test statistici (Chi-square)
✦
Funzioni crittografiche (SHA-1)
s = ⎣C⋅2w⎦
r1
r0
estrai p bits
H(i)
© Alberto Montresor
17
Problema delle collisioni
✦
✦
✦
Liste di trabocco (chaining)
✦
Come gestire le collisioni residue?
✦
✦
Tecniche di risoluzione delle collisioni
Abbiamo ridotto, ma non eliminato, il numero di collisioni
✦
Dobbiamo trovare collocazioni alternative per le chiavi
Se una chiave non si trova nella posizione attesa, bisogna andare a cercare nelle
posizioni alternative
✦
Le operazioni possono costare Ө(n) nel caso peggiore...
✦
...ma hanno costo Ө(1) nel caso medio
✦
✦
Due delle possibili tecniche:
✦
Liste di trabocco o memorizzazione esterna
✦
Indirizzamento aperto o memorizzazione interna
© Alberto Montresor
18
© Alberto Montresor
✦
19
k1
k4
Si memorizza un puntatore alla testa della lista nello
slot A[h] della tabella hash
k5
k2
k7
k3
Operazioni:
✦
0
Gli elementi con lo stesso valore hash h vengono memorizzati in una lista
Insert: inserimento in testa
k6
k8
Lookup, Delete: m–1
richiedono di scandire la lista alla ricerca della chiave
© Alberto Montresor
20
rapporto tra il numero di chiavi memorizzate nella tabella e la dimensione della tabella stessa.
In altri termini, tabelle di dimensioni diverse presentano lo stesso tempo di ricerca qualora la
Liste di trabocco: complessità
percentuale di posizioni occupate sia la stessa. Siano:
!
!
I( )
=
=
=
=
!
S( )
=
n
m
!
! tabella hash
numero di chiavi memorizzate nella
dimensione della tabella hash
!
n/m (fattore di carico)
numero medio di accessi alla tabella
! per la ricerca di una chiave non
presente nella tabella (ricerca con insuccesso)
numero medio di accessi alla tabella
! per la ricerca di una chiave presente
nella tabella (ricerca con successo)
!
✦
Liste di trabocco: complessità
✦
Teorema:
✦
✦
Dimostrazione:
✦
!
Le grandezze I( ) ed S( ) possono adeguatamente rappresentare la complessità media
✦ Analisi
delle
operazioni
lookup
(), insert() e remove(). Infatti,
per inserire
un elemento
Analisi
del caso
pessimo:
del caso
medio: non presente
nella
tabella
occorre
innanzitutto
una
ricerca
con
insuccesso,
seguita
dall’inserimento vero
✦ Tutte le chiavi sono collocate in
✦ Dipende da come le chiavi
e proprio, mentre per cancellare un elemento presente nella tabella occorre una ricerca con
unica lista
vengono distribuite
successo, seguita dalla cancellazione vera e propria. Pertanto, i tempi medi di inserzione e
✦ Insert: Ө(1)
cancellazione
dipendono, a meno di costanti, da I( ) ✦ed Assumiamo
S( ).
hashing Le ✦grandezze
) ed S(
) sono state valutate matematicamente,
assumendo
Search,I(
Delete:
Ө(n)
uniforme semplice una distribuzione uniforme delle chiavi. Le funzioni ottenute al variare di per i vari metodi di scansione
✦ Costo calcolo funzione di ! con buona approssimazione, le seguenti:
sono,
In tavola hash con concatenamento, una ricerca senza successo richiede un tempo
atteso Ө(1 + α)
✦
✦
Una chiave non presente nella tabella può essere collocata in uno qualsiasi degli m
slot
Una ricerca senza successo tocca tutte le chiavi nella lista corrispondente
Tempo di hashing: 1 + lunghezza attesa lista: α → Θ(1+α)
1
k1
k4
α
hashing: θ(1)
I( )
S CANSIONE
© Alberto Montresor
0⇥ <1
Liste diLineare
trabocco: complessità
✦
Teorema:
✦
✦
✦
Hashing doppio
0⇥
<1
(1
)2 + 1
2(1
)2
1
S( )
1
1
1
21
/2
✦
ln(1
⇤0
Più precisamente: Ө(1 + α/2)
1+
22
Liste di trabocco: complessità
)
In tavola hash con concatenamento, una1ricerca con successo richiede un tempo
atteso di Ө(1 + α)
Liste di trabocco
© Alberto Montresor
1 + /2
Qual è il significato del fattore di carico:
✦
Influenza il costo computazionale delle operazioni sulle tabelle hash
✦
se n = O(m), α = O(1)
✦
quindi tutte le operazioni sono Ө(1)
Dimostrazione: idee chiave
✦
✦
Si assuma che l'elemento cercato k sia uno qualsiasi degli n elementi presenti nella
tabella
Il numero di elementi esaminati durante una ricerca con successo:
✦
1 (l'elemento cercato) +
✦
in media, dovrò scandire metà della lista (di lunghezza attesa α)
© Alberto Montresor
23
© Alberto Montresor
24
Indirizzamento aperto
✦
Problema della gestione di collisioni tramite concatenamento
✦
✦
Indirizzamento aperto
Struttura dati complessa, con liste, puntatori, etc.
Gestione alternativa: indirizzamento aperto
✦
Idea: memorizzare tutte le chiavi nella tabella stessa
✦
Ogni slot contiene una chiave oppure nil
✦
Sequenza di ispezione: La lista ordinata degli slot esaminati
✦
Funzione hash: estesa come
✦
✦
Si cerca nello slot prescelto, e poi negli slot “alternativi” fino a quando non si
trova la chiave oppure nil
25
Indirizzamento aperto
Compreso fra 0 e 1
✦
La tabella può andare in overflow
✦
✦
Può essere necessario esaminare ogni slot nella tabella
✦
Non vogliamo esaminare ogni slot più di una volta
26
La situazione ideale prende il nome di hashing uniforme
✦
Inserimento in tabella piena
✦
✦
linear hashing
✦
© Alberto Montresor
La sequenza di ispezione { H(k, 0), H(k, 1), …, H(k, m–1) } è una permutazione
degli indici [0...m-1]
© Alberto Montresor
✦
Esistono tecniche di crescita/contrazione della tabella
✦
n. sequenza indice array
Tecniche di ispezione
Cosa succede al fattore di carico α?
✦
H : U × [0 ... m-1] → [0 ... m-1]
✦
Se lo slot prescelto è utilizzato, si cerca uno slot “alternativo”
© Alberto Montresor
✦
✦
Ricerca:
✦
✦
Ispezione: Uno slot esaminato durante una ricerca di chiave
Inserimento:
✦
✦
✦
27
Ogni chiave ha la stessa probabilità di avere come sequenza di ispezione una
qualsiasi delle m! permutazioni di [0...m-1]
Generalizzazione dell'hashing uniforme semplice
Nella realtà:
✦
E' difficile implementare il vero uniform hashing
✦
Ci si accontenta di ottenere semplici permutazioni
Tecniche diffuse:
✦
Ispezione lineare
✦
Ispezione quadratica
✦
Doppio hashing
© Alberto Montresor
28
Ispezione lineare
✦
Funzione: H(k, i) = (H(k)+h⋅i) mod m
chiave
!
✦
✦
Ispezione quadratica
n. ispezione
✦
funzione hash base
!
Il primo elemento determina l'intera sequenza
✦
✦
H(k), H(k)+h, H(k)+2⋅h…, H(k)+(m-1)⋅h
✦
Solo m sequenze di ispezione distinte sono possibili
(tutti modulo m)
Lunghe sotto-sequenze occupate...
✦
... che tendono a diventare più lunghe:
✦
✦
✦
✦
chiave
✦
Solo m sequenze di ispezione distinte sono possibili
✦
Problema: agglomerazione secondaria (secondary clustering)
Se due chiavi hanno la stessa ispezione iniziale, le loro
sequenze sono identiche
30
© Alberto Montresor
n. ispezione
✦
funzioni hash base, ausiliaria
✦
✦
Le ispezione successive hanno un offset che dipende da una funzione quadratica
nel numero di ispezione i
Cancellazione
Funzione: H(k, i) = (H(k) + i ⋅H’(k)) mod m
!
L'ispezione iniziale è in H(k)
Problema: la sequenza così risultante non è una permutazione
✦
Doppio hashing
funzione hash base
✦
I tempi medi di inserimento e cancellazione crescono
29
n. ispezione
Sequenza di ispezioni:
✦
uno slot vuoto preceduto da i slot pieni viene riempito con probabilità (i+1)/m
© Alberto Montresor
chiave
✦
Problema: agglomerazione primaria (primary clustering)
✦
Funzione: H(k, i) = (H(k) + h⋅i2) mod m
Due funzioni ausiliarie:
Non possiamo semplicemente sostituire la chiave che vogliamo cancellare con un
nil. Perché?
Approccio
✦
Utilizziamo un speciale valore deleted al posto di nil per marcare uno slot come
vuoto dopo la cancellazione
✦
H fornisce la prima ispezione
✦
H’ fornisce l'offset delle successive ispezioni
✦
Ricerca:
✦
m2
✦
Inserimento: deleted trattati come slot vuoti
sequenze di ispezione distinte sono possibili
Nota: Per garantire una permutazione completa, H’(k) deve essere relativamente primo con m
✦
Scegliere m = 2p e H’(k) deve restituire numeri dispari
✦
Scegliere m primo, e H’(k) deve restituire numeri minori di m
© Alberto Montresor
31
deleted trattati come slot pieni
✦
Svantaggio: il tempo di ricerca non dipende più da α.
✦
Concatenamento più comune se si ammettono cancellazioni
© Alberto Montresor
32
H ASH
- Hashing doppio
ICodice
TEM [ ] A
I TEM[ ] V
H ASH
integer m
I TEM[ ] A
I TEMHash
[ ] V (integer capacità)
H ASH
H ASH m
t = new H ASH
integer
t.m
⇥ capacità
H
ASH Hash(integer capacità)
ASHnew
t = Item[0
new H ASH
t.AH⇥
. . . t.m 1]
t.m
⇥
capacità
t.V ⇥ new Item[0 . . . t.m 1]
⇥0new
Item[01. .do
. t.m
1] ⇥ nil
fort.A
i⇥
to t.m
t.A[i]
t.V
⇥
new
Item[0
.
.
.
t.m
1]
return t
for i ⇥ 0 to t.m 1 do t.A[i] ⇥ nil
integerreturn
scant(I TEM k, boolean insert)
integer j ⇥ H(k)
% Posizione attuale
for i ⇥ 0 to t.m 1 do t.A[i] ⇥ nil
Codice
doppio
while A[j] %
⇤= kTabella
and A[j]
nil and
ireturn
< m- Hashing
do
delle⇤=chiavi
t
if A[j] = %
deleted
and
c
=
m
then
c
⇥
j
Tabella dei valori integer scan(I TEM k, boolean insert)
j⇥
(j
+
H
(k))della
modtabella
m
% Dimensione
integer c ⇥ m
% Tabella delle chiavi
i⇥i+1
integer i ⇥ 0
% Tabella dei valori
if insert and A[j] ⇤= k and c < m then
j = jc ⇥ H(k)
integer
% Dimensione della tabella
return j
while A[j] ⇤= k and A[j] ⇤= nil and i < m do
% Prima posizione deleted
% Numero di ispezione
% Posizione attuale
if A[j] = deleted and c = m then c ⇥ j
I TEM lookup(I TEM k)
j ⇥ (j + H (k)) mod m
integer i ⇥ scan(k, false)
i⇥i+1
if A[i] = k then
if insert and A[j] ⇤= k and c < m then j = c
return V [i]
return j
else
return
nil posizione deleted I TEM lookup(I TEM k)
% Prima
integerscan
c⇥
m k, boolean insert)
integer i ⇥ scan(k, false)
integer
(I TEM
integer
i
⇥
0
%
Numero
di
ispezione
if A[i] = k then
integer c ⇥ m
%TEM
Primak,posizione
deleted
insert(I
I TEM v)
integer
% di
Posizione
attuale
return V [i]
integerj i⇥
⇥H(k)
0
%
Numero
ispezione
integer i ⇥ scan(k, true)
else
while
A[j]j ⇥
⇤= kH(k)
and A[j] ⇤= nil and i < m do
integer
% Posizione attuale
if A[i] = nil or A[i] = deleted or A[i] =return
k then
nil
if A[j]
and⇤=c nil
= and
m then
c⇥
while
A[j]=⇤=deleted
k and A[j]
i<m
do j
A[i]
⇥
k
if
A[j]
=
deleted
and
c
=
m
then
c
⇥
j
j ⇥ (j + H (k)) mod m
insert(I TEM k, I TEM v)
V [i] ⇥ v
j⇥
(j 1+ H (k)) mod m
33
© Alberto Montresor
© Alberto Montresor
i⇥
i+
integer i ⇥ scan(k, true)
else
i ⇥and
i +A[j]
1
if insert
⇤= k and c < m then j = c
if A[i] = nil or A[i] = deleted or A[i] = k then
if -insert
and A[j]
⇤= k and c < m then j = c
% Errore: tabella hash piena Indirizzamento
Codice
Hashing
doppio
aperto: Complessità hashing doppio
return j
A[i] ⇥ k
return j
V [i] ⇥ v
remove(I TEM k)
✦ Assunzioni
I TEM
(I(ITEM
I TEMlookup
lookup
TEM k)
k)
else
integer i ⇥ scan(k, false)
integer
integeri ⇥
i ⇥scan
scan(k,
(k, false)
false)
% Errore:
tabella hash piena
✦ Hashing
uniforme
if A[i]
==k kthen
if A[i]
then
if A[i] = k then
✦
cancellazione
returnVV[i]
[i]
return
removeNessuna
(I TEM k)
A[i] ⇥ deleted
else
integer
⇥ scancon
(k, successo,
false)
else
✦ Nellai ricerca
tutte le chiavi hanno la stessa probabilità di essere
return
nil
return nil
if A[i]
=
k
then
cercate
A[i] ⇥ deleted
insert(I TEM k, I TEM v)
insert(I
TEM k, I TEM v)
✦ Analisi
integer i ⇥ scan(k, true)
integer
i
⇥
scan(k, true)
if A[i] = nil or A[i] = deleted or A[i] = k then
✦ n chiavi inserite in una tabella di m slot
if A[i]A[i]
= nil
⇥ or
k A[i] = deleted or A[i] = k then
✦ n < m, ovvero il fattore di carico α < 1
A[i]
V [i]⇥⇥k v
V [i] ⇥ v
else
else % Errore: tabella hash piena
% Errore: tabella hash piena
✦
34
Analisi basata sul valore di α
remove(I TEM k)
integer i ⇥ scan(k, false)
remove(I TEM k)
if A[i] = k then
integer
i ⇥ scan(k, false)
A[i] ⇥ deleted
if A[i] = k then
© Alberto Montresor
35
© Alberto Montresor
36
zione uniforme delle chiavi. Le funzioni ottenute al variare di
sono, con
buona approssimazione,
le seguenti:
Complessità
- Riassunto
Indirizzamento aperto: Complessità hashing doppio
✦
✦
✦
✦
Esempio: α=0.5, I(α)=2; α=0.9, I(α) =10
A cosa tende queste valore per α → 1?
Il numero atteso di ispezioni S(α) per una ricerca con successo è O( - 1/α ln (1-α))
✦
Lineare
0⇥
<1
Hashing doppio
0⇥
<1
Esempio: α=0.5, S(α) =1.387; α=0.9, S(α) =2.559
Liste di trabocco
37
© Alberto Montresor
O 7. TABELLE
HASH
Confronto
complessità
131
2
1
1 − α/2
2(1 − α) 2
1−α
1−α
(1
)2 + 1
2(1
)2
⇤0
1
1
1+
© Alberto Montresor
S( )
1
1
1
/2
ln(1
)
1 + /2
38
Ristrutturazione
✦
(1 − α) + 1
I( )
S CANSIONE
Il numero atteso di ispezioni I(α) per una ricerca senza successo è O(1/(1-α))
per i vari metodi di scansion
5
Non è conveniente che α cresca troppo
✦
In particolare con la scansione interna
✦
Ma vale anche per le liste di trabocco
Lineare
Q uadratica,
p seudocasuale,
hashing dop p io
✦
4
Liste di trab occo
–
3
1
α
Sopra un soglia prefissata (tipicamente 0.5-0.75)
✦
Si alloca una nuova tabella di dimensione 2m
✦
Si reinseriscono tutte le chiavi presenti nella nuova tabella
ln (1 − α)
✦
1+α
Risultato
✦
Fattore di carico dimezzato (tipicamente 0.25)
✦
Nessun elemento deleted
2
1 + α/2
✦
1
0
0.2
0.4
0.6
0.8
1
α=
Figura 7.3: Numero medio di accessi per ricerche in tabelle hash.
© Alberto Montresor
Costi
n/m
39
✦
Costo O(m) per la ristrutturazione nel caso pessimo
✦
Costo ammortizzato costante (vedi dimostrazione per vettori)
© Alberto Montresor
40
Reality check
Java 7
HashMap
Java 8
HashMap
Java hashCode()
Liste di trabocco
Ristrutturazione O(n) nel caso pessimo
basate su LinkedList con α=0.75
Overhead: 16N + 4C byte
Nella documentazione di java.lang.Object
Liste di trabocco
Ristrutturazione O(log n) nel caso pessimo
con Red-Black Tree con α=0.75
Overhead: 48N + 4C byte
C++ SparseHash
Ind. aperto,
???
sparse_hash
scansione quadratica
✦
The general contract of hashCode is:
1.
Whenever it is invoked on the same object more than once during an execution
of a Java application, the hashCode method must consistently return the same
integer, provided no information used in equals comparisons on the object is
modified. This integer need not remain consistent from one execution of an
application to another execution of the same application.
2.
If two objects are equal according to the equals(Object) method, then
calling the hashCode method on each of the two objects must produce the
same integer result.
3.
It is not required that if two objects are unequal according to the
equals(java.lang.Object) method, then calling the hashCode
method on each of the two objects must produce distinct integer results.
However, the programmer should be aware that producing distinct integer
results for unequal objects may improve the performance of hash tables.
Overhead: 2 bit per entry
C++ SparseHash
Indirizzam. aperto, Ristrutturazione Overhead: X byte per chiave
dense_hash
scansione quadratica con α=0.50
+valore, 2-3X overhead
C++ STL
Liste di trabocco
unordered_map basate su liste
Python
Ristrutturazione Hashing basato su MurmurHash
configurabile
con α=1.00
Indirizzam. aperto, Ristrutturazione
scansione quadratica con α=0.66
41
© Alberto Montresor
Commenti finali
Java hashCode()
✦
In generale, per oggetti che ereditano da java.lang.Object ma non fanno
override di equals():
✦
✦
42
© Alberto Montresor
✦
x.equals(y) ritorna true se e solo se x == y
x.hashCode() converte l’indirizzo di memoria di x in un intero
✦
Problemi con hashing
✦
Scarsa “locality of reference” (cache miss)
✦
Non è possibile ottenere le chiavi in ordine
Interessanti estensioni
✦
Se fate ovveride di equals(), dovete fare ovverride anche di hashCode():
✦
Distributed Hash Table (DHT)
✦
Esempio: java.lang.String
✦
Bloom filters
✦
Ovveride di equals per controllare l’uguaglianza di stringhe
✦
hashCode in Java 1.0, Java 1.1
✦
✦
✦
Venivano utilizzati 16 caratteri della stringa per calcolare l’hashCode()
Problemi con la regola (3) - cattiva performance nelle tabelle
Java 1.2 e seguenti
h(s) =
n
X1
i=0
© Alberto Montresor
✦
s[i] · 31n
1 i
43
Una struttura per testare l’appartenenza ad un’insieme, con falsi positivi
✦
Test ritorna true: l’oggetto appartiene all’insieme, oppure no
✦
Test ritorna false: l’oggetto non appartiene all’insieme
✦
9.6 bit (1.2 byte) per item
→ 1% falsi positivi
✦
14.4 bit (1.8 byte) per item
→ 0.1% falsi positivi
✦
Utilizzati, e.g., in:
© Alberto Montresor
✦
Google Chrome
✦
Bitcoin
44