Molte applicazioni richiedono un insieme dinamico che supporta le operazioni dizionario INSERT, SEARCH, DELETE.
Una struttura affidabile per implementare i dizionari sono le tabelle hash, che anche se nel caso pessimo performano come le linked list, nella pratica sono molto veloci, impiegando un tempo medio di
è una tecnica semplice che funziona quando l'insieme totale delle chiavi possibili (
![[direct-access.png|center]]
Le operazioni disponibili impiegano tutte
DIRECT-ACCESS-SEARCH(T, k):
return T[k]
DIRECT-ACCESS-INSERT(T, x):
T[x.key] = x
DIRECT-ACCESS-DELETE(T, x):
T[x.key] = NIL
Il problema delle [[#Tabelle Ad Accesso Diretto]] è che dipendono dalla dimensione di
Una tabella hash richiede molto meno spazio di una tabella ad accesso diretto, con un'utilizzo di memoria di
La "fregatura" consiste nel tempo di ricerca che rappresenta il caso __medio__, e non il __peggiore__
Nell'accesso diretto l'elemento con chiave k viene memorizzato nello slot k, mentre nelle tabelle hash si usa una funzione di hash (
In questo modo si riduce la dimensione dell'array, che invece di avere dimensione
Un esempio semplice, ma non molto buono, è la funzione: $$h(k) = k \mod m$$
C'è però un problema: due chiavi potrebbero puntare allo stesso slot, chiameremo questa situazione __collisione__
La soluzione ideale sarebbe di evitare le collisioni, scegliendo magari una funzione di hash adatta.
Un'altra idea è quella di far sembrare
Dato che
Una funzione ideale $h$, avrebbe, per ogni possibile $k$, un output che sia un elemento che sia scelto in modo casuale e indipendente nel range $\{0,1,...,m-1\}$, una volta scelto il valore ogni chiamata $h(k)$ ritorna sempre quel valore
Consiste nell'usare delle linked list per ogni slot dell'array, ogni volta che la funzione di hashing genera lo stesso risultato, l'elemento viene aggiunto alla linked list di quella chiave.
![[Pasted image 20230615165741.png|center]]
Quando le collisioni vengono risolte attraverso il concatenamento, le operazioni di dizionario sono semplici da implementare, e hanno un tempo di esecuzione di
- L'inserimento presuppone che l'elemento da inserire non sia nella lista, se lo è bisogna cercare a scapito di un costo aggiuntivo
- La ricerca nel tempo peggiore è proporzionale alla lunghezza della lista
- L'eliminazione impiega
$O(1)$ se prende come input l'elemento$x$ e non la sua chiave, rendendo non necessaria la ricerca.
title: Quanto impiega l'hashing con concatenamento?
Il tempo di esecuzione __peggiore__ è nell'ordine di $\Theta(n)$, e richiede che tutti gli $n$ elementi vadano sullo stesso slot creando una lista lunga $n$.
Il tempo di esecuzione __medio__ dipende da quanto bene la funzione $h$ distribuisce le chiavi tra gli slot, arrivando ad una possibilità che due chiavi collidano di $1/m$
Dato il fattore di caricamento $\alpha = n/m$
In una tabella hash le cui collisioni sono risolte tramite concatenamento, la ricerca in media impiega $\Theta(1 + \alpha)$, assumendo una funzione di hashing uniforme e indipendente
Descriviamo l'indirizzamento aperto come un metodo per risolvere le collisioni che non utilizza spazio al di fuori della tabella hash.
- Tutti gli elementi occupano la tabella stessa
- Ogni valore della tabella contiene un elemento dell'insieme dinamico oppure NIL
- Nessuna lista o altri elementi sono memorizzati fuori la tabella
- La tabella può essere riempita così che non possono essere inseriti altri elementi
- Una conseguenza è che il fattore di caricamento
$\alpha$ non può mai superare 1
Le collisioni sono gestite in questo modo: quando un elemento deve essere inserito, viene posizionato nella sua "prima-scelta" (first-choice) se possibile. Se non possibile (la posizione è occupata), il nuovo elemento viene inserito nella sua "second-choice", e così via fino a che non si trova uno spazio vuoto dove poter piazzare il nuovo elemento.
Per cercare un elemento bisogna esaminare il suo slot preferito per diminuire le preferenze fino a che non trovi l'elemento desiderato, oppure uno slot vuoto.
La procedura HASH-SEARCH richiede in input una tabella e una chiave, ritornando la posizione
Per inserire un elemento bisogna esaminare successivamente (probe) la tabella fino a che non troviamo uno slot vuoto in cui inserire la chiave.
Invece di utilizzare un ordine finito
L'indirizzamento aperto richiede che per ogni chiave $k$, la sequenza di probe $< h(k, 0), h(k, 1),..., h(k, m-1) >$ sia una permutazione di $\{0,1,...,m-1\}$, così che ogni posizione possa essere considerata come slot per una nuova chiave
HASH-INSERT(T, k):
i = 0
do:
q = h(k, i)
if T[q] == NIL:
T[q] = k
return q
else:
i++
while i != m
error "hash table overflow"
La procedura di inserimento assume che tutti gli elementi della tabella hash siano chiavi senza informazioni satellite, e da per scontato che l'elemento da inserire non sia già presente nella tabella.
Eliminare un elemento dalla tabella può essere complicato, perché se si imposta semplicemente come vuoto allora la ricerca potrebbe fermarsi prima di trovare un qualche elemento che è stato inserito quando lo slot era ancora occupato.
Per risolvere questo problema si segna lo slot come DELETED invece che NIL, così che HASH-INSERT lo possa trattare come slot vuoto in cui poter inserire un nuovo elemento, mentre HASH-SEARCH lo tratta come slot da saltare per controllare le posizioni successive.
Assumendo un hashing indipendente e uniforme, la sequenza di ogni chiave può essere una delle
Il doppio hashing offre uno dei migliori metodi per l'indirizzamento aperto, dato che le permutazioni prodotte hanno molte delle caratteristiche delle permutazioni scelte casualmente.
Il doppio hashing usa una funzione hash nella forma:
Dove
Dati una tabella di $m = 13$, $h_1(k) = k \mod 13$ e $h_2(k) = 1 + (k \mod 11)$
![[Pasted image 20230616123119.png|center]]
Linear probing è un caso speciale di doppio hashing, è il modo più semplice per risolvere le collisioni in indirizzamento aperto.
Se lo slot
è un caso speciale di doppio hashing in quanto si può scrivere che