Hashing
argomenti

Hashing





Tabelle hash
Funzioni hash e metodi per generarle
Inserimento e risoluzione delle collisioni
Eliminazione
Funzioni hash per file


Hashing estendibile
Hashing lineare
Hashing
2
Implementazione di un
dizionario



Insieme di coppie del tipo <elemento, chiave>
Le chiavi appartengono a un insieme totalmente
ordinato
Operazioni:





insert(el, key)
delete(key)
search(key)
Indirizzamento diretto: si associa ad ogni valore della
chiave un indice di un array – ricerca in tempo O(1)
Problemi?
Hashing
3
Indirizzamento diretto



0
2
Ogni chiave
corrisponde a
el. diverso
dell’array
Può portare a
spreco di
memoria
Es.: 10000
studenti e
matr.= No.
decimale a 5
cifre
No. chiavi
|N|-1
Hashing
4
Obiettivi




0
2
N ~ No. Chiavi
effettivamente
usate
Tempo di ricerca
O(1)
D.: possibile?
Nota: No. Chiavi
possibili può
essere >> |T|
No. chiavi
|T|-1
Hashing
5
Tabella hash
Dato l’insieme base di un dizionario:
 <T, h>
 T è una tabella
 h: K  {0,...,|T|-1}


K insieme delle possibili chiavi
{0,...,|T|-1} insieme delle posizioni nella
tabella
Hashing
6
asd_library.hash.HashTable
public class HashTable implements Dictionary_adt{
public HashTable() {
this(DEFAULT_TABLE_SIZE);
}
public HashTable(int size) {
allocateTable(size);
makeEmpty();
isRehashable = false;
}
Hashing
7
Funzioni hash perfette e
collisioni

Funzione hash perfetta:




In generale |T| < |K| (spesso |T| << |K|)


k1!=k2  h(k1) != h(k2)
Richiede |T| >= |K|
Raramente ragionevole in pratica
Conseguenza: k1!=k2 ma h(k1) == h(k2) è possibile
 Collisione
Es.: proporre una funzione hash perfetta nel
caso in cui le chiavi siano stringhe di lunghezza
3 sull’alfabeto {a, b, c}
Hashing
8
Requisiti di una funzione hash

Uniformità semplice: Pr[h(k)=j] ~ 1/|K|




La probabilità è calcolata rispetto alla
distribuzione delle chiavi
Intuitivamente, si desidera che gli elementi si
distribuiscano nell’array in modo uniforme
Difficile costruire funzioni che soddisfino la
proprietà
D.: perché?
Hashing
9
Requisiti di una funzione
hash/2

Esempio: sia |T|=5 e h(k)=k mod 5
{1, 7, 10, 14}
• Non è nota la
distribuzione
delle chiavi
• Può aversi
agglomerazione
degli elementi
{1, 6, 11, 16}
0
1
2
3
4
0
1
2
3
4
In pratica: si cerca di avere indipendenza dai dati
Hashing
10
Interpretazione delle chiavi


Tra gli elementi di K è definito un
ordinamento totale ma:
Le chiavi non sono necessariamente
numeri naturali (o persino numeri)



Es.: stringhe
Soluzione: associare a ciascuna chiave un
intero
Modalità dipendono da insieme delle chiavi e
applicazione
Hashing
11
Esempio: stringhe


Possibile metodo: associare a ciascun carattere il
valore ASCII e alla stringa il numero intero
ottenuto in una base scelta
Esempio: base 2, posizioni meno significative a
destra
Stringa = “p t”  chiave = 112*21+116*20=240
Ascii(‘p’)=112
Ascii(‘t’)=116
Hashing
12
Derivazione di funzioni hash

Molti metodi







Divisione
Ripiegamento
Mid-square
Estrazione
...........
Obiettivo: distribuzione possibilmente uniforme
Differenze:


Complessità
Fenomeni di agglomerazione
Hashing
13
Divisione


h(k)=k mod |T| - Bassa complessità
Attenzione ai fenomeni di agglomerazione




No potenze di 2: se m=2p allora tutte le chiavi con i p
bit meno significativi uguali collidono
No potenze di 10 se le chiavi sono numeri decimali
(motivo simile)
In generale, la funzione dovrebbe dipendere da tutte
le cifre della chiave (comunque rappresentata)
Scelta buona in pratica: numero primo non troppo
vicino a una potenza di 2 (esempio: h(k)=k mod 701
per |K|=2048 valori possibili)
Hashing
14
Ripiegamento



Chiave k suddivisa in parti k1,k2,....,kn
h(k)=f(k1,k2,....,kn)
Esempio: la chiave è un No. di carta di
credito. Possibile funzione hash:
1. 4772 6453 7348  {477, 264, 537, 348}
2. f(477,264,537,348) =
(477+264+537+348)mod 701 = 224
Hashing
15
Estrazione


Si usa soltanto una parte della chiave per
calcolare l’indirizzo
Esempio: 6 cifre centrali del numero di
carta di credito
4772 6453 7348  264537


Il numero ottenuto può essere ulteriormente manipolato
L’indirizzo può dipendere da una porzione della chiave
Hashing
16
HashTable.hash()
public static int hash( String key, int tableSize ){
int hashVal = 0;
for( int i = 0; i < key.length( ); i++ )
hashVal = 37 * hashVal + key.charAt( i );
hashVal %= tableSize;
if( hashVal < 0 )
hashVal += tableSize;
}
return hashVal;
Hashing
17
Risoluzione delle collisioni



I metodi si distinguono per la collocazione
degli elementi che danno luogo alla
collisione
Concatenazione: alla i-esima posizione
della tabella è associata la lista degli
elementi tali che h(k)=i
Indirizzamento aperto: tutti gli elementi
sono contenuti nella tabella
Hashing
18
Concatenazione
h(k1)= h(k4)=0
h(k5)= h(k7)=h(k2)=4


0
1
2
3
4



k1
k4
k7
k5
Es.: h(k)=k mod 5
k1=0, k4=10
k5=9, k7=14, k2=4
Hashing
k2
k2
19
Concatenazione/2



insert(el, k): inserimento in testa alla lista
associata alla posizione h(k) – costo O(1)
search(k): ricerca lineare nella lista
associata alla posizione h(k) – costo
O(lungh. lista associata a h(k))
delete(k): ricerca nella lista associata a
h(k), quindi cancellazione – costo O(lungh.
lista associata a h(k))
Hashing
20
Indirizzamento aperto


Tutti gli elementi sono memorizzati nella tabella
Le collisioni vanno risolte all’interno della tabella




Se la posizione calcolata è già occupata occorre
cercarne una libera
I diversi metodi ad indirizzamento diretto si
distinguono per il metodo di scansione adottato
La funzione hash dipende anche dal numero di
tentativi effettuati
Indirizzo=h(k, i) per l’i-esimo tentativo
Hashing
21
Inserimento
insert (el, k) {
/* T denota la tabella */
i=0;
while (h(k, i) <occupata> && (i<|T|))
i++;
if (i < |T|)
<inserisci el in pos. i>
else <overflow>
}
Hashing
22
HashTable.insert()
public Object insert(Comparable key ){
int collisionNum = 0;
int initialPos = hash( key.toString(),table.length );
int currentPos=initialPos;
while((collisionNum<=table.length)&& table[ currentPos ] !=
null &&
!table[ currentPos ].equals( key ) ){
currentPos = initialPos + k * ++collisionNum; //
Compute ith probe
currentPos = currentPos % table.length; // Implement
the mod
}
if (collisionNum > table.length){
System.out.println("Insertion impossible: hash table full");
return null;
Hashing
23
}
HashTable.insert()
else if (table[ currentPos ] != null &&
table[ currentPos ].equals( key ) ){
System.out.println("Element "+ key +" is alredy in
the hash table.");
return key;
}else{
table[ currentPos ] = key;
++currentSize;
System.out.println("Insertion: ok!");
return key;
}
}
Hashing
24
Ricerca
search (k) {
/* T denota la tabella */
i=0;
while ((k!=key(T[h(k, i)])) && (i<|T|))
i++;
if (i < |T|)
<restituisci T[h(k, i)]>
else <elemento assente>
}
Hashing
25
Cancellazione
delete (k) {
/* T denota la tabella */
search(k);
if (<trovato>)
<elimina elemento con chiave k>
}
Hashing
26
HashTable.remove()
public Comparable remove(Comparable key ){
int collisionNum = 0;
int initialPos = hash( key.toString(),table.length );
int currentPos=initialPos;
while( !table[ currentPos ].equals( key )&&
(collisionNum<=table.length)){
currentPos = initialPos + k *
++collisionNum; // Compute ith probe
currentPos = currentPos % table.length; //
Implement the mod
}
Hashing
27
HashTable.remove()
if (!table[ currentPos ].equals( key )){
System.out.println("Element "+ key +" isn't in the
hash table.");
return null;
}else{
System.out.println("Element "+ key +" isn't in the
hash table.");
table[currentPos]=null;
return key;
}
}
Hashing
28
Scansione


La funzione h(k, i) deve essere tale che tutte le
posizioni della tabella siano esaminate
Sono possibili diverse forme per la funzione
h(k,i)




Scansione lineare
Scansione quadratica
Hashing doppio
Si differenziano per complessità e
comportamento rispetto a fenomeni di
agglomerazione
Hashing
29
Scansione lineare



h(k, i) = (h’(k)+i) mod |T|, dove h’(k) è
una funzione di hashing
Si scandiscono tutte le posizioni nella
sequenza T[h’(k)], T[h’(k)]+1, .... T[|T|],
0, 1, ...., T[h’(k)]-1
Possibilità di agglomerazione primaria: gli
elementi si agglomerano per lunghi tratti
Hashing
30
Agglomerazione primaria

h(k, i) = (h’(k)+i) mod 101, h’(k)=k mod 101
{2, 103, 104, 105,....}
Caso estremo, ma il problema
Esiste
0
1
2
Prob[cella succ. gruppo]=
dim(gruppo + 1)/|T|
Prob[cella isolata]= 1/|T|
100
Hashing
31
Scansione quadratica




h(k, i) = (h’(k)+c1i+c2i2) mod |T|, dove
h’(k) è una funzione di hashing, c1 e c2
sono costanti
Es.: h(k, i) = h’(k)+i2, h(k, i+1) = h’(k)-i2,
i=1,..., (|T|-1)/2
Possibilità di agglomerazione secondaria:
se h’(k1)= h’(k2)  h’(k1,i)= h’(k2,i)
Descrivere h(k, i) quando h’(k)=k mod |5|
Hashing
32
Hashing doppio




h(k, i) = (h1(k)+ih2(k)) mod |T|, dove
h1(k) e h2(k) sono funzioni di hashing
Es.: h(k, i) = h’(k)+i2, h(k, i+1) = h’(k)-i2,
i=1,..., (|T|-1)/2
Anche la modalità di scansione dipende
dalla chiave
L’hashing doppio riduce i fenomeni di
agglomerazione
Hashing
33
Universal Hashing/1



Nel caso peggiore possono essere scelte n
chiavi tali che h(k1)= h(k2)= …. h(kn). In
questo caso il tempo di retrieval è O(n)
Qualsiasi funzione hashing deterministica puo’
incontrare questo caso peggiore.
Nell’Universal Hashing si definisce una
famiglia di funzioni hash. Una delle funzioni è
selezionata a priori, in modo indipendente
dalle chiavi degli elementi.
Hashing
34
Universal Hashing/2

H e’ una famiglia di funzioni hash

H e’ universale se per ogni coppia x,y:
#hH:h(x)=h(y)=|H|/|T|

La probabilità di collisione tra due chiavi è simile ad
una scelta casuale di h(x):
E[cxy ]  1 / | T |
Hashing
35
Universal Hashing/3
Come costruire una famiglia universale H di funzioni
hash?
m=|T| primo
x = <x0, x1 , .., xr > r+1 bytes
a = <a0, a1 , .., ar > r+1 elementi random in {0,…,m-1}

r
ha =
 a x mod m
i 0
H   ha
i i
a
H contiene mr+1 funzioni
Hashing
36
Universal Hashing/4
Thm:H è una famiglia universale di
funzioni hash
Fissati <a1 , .., ar > esiste un solo valore a0
r
a0 ( x0  y0 )   a i ( xi  yi )(mod m)
i 0
Percio’ ogni coppia di x e y collide esattamente per un
mr valori della sequenza a
Poiche’ vi sono mr+1 valori possibili per la sequenza a, la
collisione avviene con probabilita’ 1/m
Hashing
37