Dizionari

Hashtables

http://www.dia.uniroma3.it/~roselli/ roselli@dia.uniroma3.it

Credits

• Materiale a cura del Prof. Franco Milicchio

Introduzione

• I tipi di dato che abbiamo introdotto fino ad ora sono molto semplici

• Ad esempio liste, stringhe, sono essenzialmente mappe di interi

• In effetti, temperature[i], è una mappa N → R, cioè ad ogni intero viene associato un reale

• Analogamente una stringa associa un intero ad un carattere ASCII

• Una hashtable (o “dizionario”) è una mappa da un insieme in un altro, o in altre parole, è una lista di coppie chiave-valore

Hashtable

h = dict() h["ciao"] = 3.1415h["al"] = -1.2345h["mondo"] = 2.7182for i in h: print i, h[i]

h["ciao"] 3,1415

h["mondo"] 2,7182

h["al"] -1,2345

Memoria

ciao 3.1415 mondo 2.7182 al -1.2345

Operazioni

• Il layout in memoria è peculiare: ne vedremo a breve il perché

• È possibile iterare su un dizionario allo stesso modo di una lista, tenendo presente che l’iteratore è una chiave

• L’oggetto ha alcuni metodi utili, come d.keys() e d.values(), che rispettivamente ritornano una lista di chiavi e di valori

• La creazione di una hashmap è possibile inline, utilizzando la seguente sintassi: h = { key:value, key:value, … }

• L’accesso è costante nel tempo

Complessità

• Una lista in Python è una sequenza lineare: in altre parole in memoria, gli elementi adiacenti occupano spazi adiacenti

• Sappiamo che l’indice in una lista indica lo scostamento dall’inizio dell’array

• Il tempo per accedere ad un elemento è dunque costante, ovvero O(1)

• Anche una hashmap ha questa proprietà, grazie all’hashing

RAM

Array di 10 elementi

array[5] = -4

Altro Altro

Hashmap: Implementazione

• Una hashmap è una struttura dati complessa, noi ne introdurremo una versione molto semplificata

• Una hashmap dall’insieme K all’insieme V è costituita da due elementi fondamentali:

• Una funzione di hash: una funzione da un insieme nei naturali h : K → N

• Una lista i cui elementi sono liste di coppie nell’insieme K × V

Hashmap

0

1

2

3

4

5

6

7

8

Lista

d[“ciao”] = 42

h(ciao) = 3

42

Hashmap: Implementazione

• Nel modello precedente, la lista degli elementi contiene solo dei valori

• Cosa succede se più chiavi hanno lo stesso valore di hash?

• La lista, dunque, non può essere una lista di elementi, bensì una lista di liste

• Ogni elemento della lista viene chiamato bucket

• Ogni bucket contiene la lista di tutti i valori associati a chiavi con stesso hash

• In questo caso, si chiama collisione

Hashmap

0

1

2

3

4

5

6

7

8

Lista

d[“ciao”] = 42

h(ciao) = 3

[ [“lotr”, 9], [“ciao”, 42], ... ]

Complessità

• Calcoliamo la complessità asintotica della modifica di un elemento in una hashtable

• Abbiamo due casi fondamentali, con complessità diverse

• La hashtable contiene un elemento per bucket

• La hashtable contiene più elementi per bucket

• La prima è il caso medio, la seconda opzione è il caso peggiore

Complessità: Caso Medio

• Nel caso medio, la hashtable contiene un elemento per bucket

• Questo vuol dire che per raggiungere un elemento k e modificarlo, è necessario:

• Calcolare l’hash function con argomento k

• Accedere alla zona di memoria dell’elemento k

• Entrambe le operazioni sono a tempo costante, quindi la complessità è O(1)

Complessità: Caso Medio

Lista

d[“ciao”] = 42

h(ciao) = 3

42

Indipendente dal numero di bucket

Indipendente dal numero di bucket

Complessità: Caso Peggiore

• Nel caso peggiore, la hashtable contiene più elementi per bucket

• Calcolare l’hash function con argomento k

• Accedere alla zona di memoria degli elementi con lo stesso hash di k

• Scorrere la lista degli elementi fino a trovare k

• Le prime due operazioni sono a tempo costante, O(1)

• L’ultima operazione, al contrario, è lineare, quindi la complessità è O(n)

Complessità: Caso Peggiore

Lista

d[“ciao”] = 42

h(ciao) = 3

[ [“lotr”, 9], [“ciao”, 42], ... ]

Indipendente dal numero di bucket

Dipende dalla lunghezza, asintoticamente O(n)

Hash Function

h = dict() h["ciao"] = 3.1415h["al"] = -1.2345h["mondo"] = 2.7182for i in h: print i, "->", h[i], "hash:", hash(i)

ciao -> 3.1415 hash: 5473374298076946440 mondo -> 2.7182 hash: -8476132622090761128 al -> -1.2345 hash: 12416074593111949

Hash Function

print hash("aaaaaaaaaaa") print hash("baaaaaaaaaa") print hash("abaaaaaaaaa") print hash("aaaaaaaaaab") print hash("bbbbbbbbbbb")

-750267083661738860 4088303228596812247 4381175614841257793 -750267083661738857 -2039379427608295595

Hash Function

• L’hash function stabilisce in quale bucket una coppia chiave-valore debba risiedere

• È quindi critica nella costruzione di una buona hashmap

• Una buona hash function ha una distribuzione uniforme dei valori

• La distribuzione, ovviamente, dovrebbe essere indipendente dalla dimensione della hashtable

• Si pensa che le hash function crittografiche, i.e., difficili da invertire, siano delle buone funzioni candidate

Distribuzioni

Hashmap

h(k) := 1

Distribuzioni

Hashmap

h(k) :=�ke��

k!

Distribuzioni

Hashmap

h(k) :=1

�p2⇡

e�(k�µ)2

2�2

Distribuzioni

Hashmap

h(k) :=k �minK +1

maxK �minK +1

Esempio

• Una hashtable è una struttura dati fondamentale: fornisce un accesso veloce a valori (nel caso medio)

• È utile nei casi un cui si debba cercare un valore ripetutamente

• As esempio, è molto indicata per contare valori

• Sia come problema tipo il seguente: data una stringa possibilmente molto lunga, e.g., il testo di un libro intero, contare tutte le parole

• Con una lista, ad ogni parola dovremo cercare se esiste scandendola

• Con una hashtable, la ricerca in media è costante

Implementazione

• Le hashmap sono costrutti base, per questo sono spesso implementate nelle librerie base di vari linguaggi

• Ad esempio, Python ha dict, C++ unordered_map, Java HashMap

• Come già accennato le hash function giocano un ruolo fondamentale

• Creare una buona hash function è molto difficile

• Altrettanto difficile è scrivere una struttura dati efficiente

• È un esercizio molto complicato scrivere dunque una hashmap, si consiglia di utilizzare la struttura dati fornita dal linguaggio