2023-10-24 - hashmaps

universityin-classsubject-2101

2023-10-24

Algoritmi

Tabelle Hash

Nella scorsa lezione abbiamo visto come risolvere il problema delle collisioni delle chiavi mediante il metodo della concatenazione.
Di seguito un metodo alternativo.

Metodo Indirizzamento Aperto

A differenza del metodo d’indirizzamento diretto, qui gli elementi vengono conservati direttamente all’interno della tabella hash (e non in delle liste di cui si conserva solo l’indirizzo).
Ricordando stabiliamo: .
Dobbiamo trovare un modo di mettere elementi diversi in posizioni diverse.

• Finché non ci sono collisioni utilizzo la funzione hash per ottenere l’indice della cella.
• Se c’è una collisione, viene fatta una “seconda domanda” alla funzione hash, per ottenere un’altro indice. Questo metodo però non è sufficiente, potrebbero esserci ulteriori collisioni.
• Cambia allora la definizione di hash function: , dove è la chiave e è un indice che rappresenta il tentativo. Per far sì che funzioni, dev’essere implementata in modo che a valori diversi di corrispondano diversi indici in output.

La definizione di diventa

In altre parole, la funzione , al variare di deve ritornare una permutazione (diversa per ogni chiave). Tale permutazione è detta ricerca di scansione.
Tutte le permutazione sono .

Ipotesi di hashing uniforme: dato un indice “tentativo” e una chiave, la probabilità che questi ultimi vengano associati a una determinata sequenza di scansione è (la probabilità è uniformemente distribuita).

Ricerca di scansione

Posso vedere la funzione come una funzione che prende in input la chiave e restituisce un’array di elementi. L’indice indica l’indice dell’array a cui accedere per ottenere l’indirizzo.

Esempio:

Per la ricerca viene fatto un procedimento analogo. Man mano che scorro gli elementi della ricerca di scansione, mi assicuro che l’indirizzo specificato contenga lo stesso valore che sto cercando. Se finisco l’array allora l’elemento non esiste. Se trovo una cella vuota, allora l’elemento non c’è (perché non possiamo eliminare elementi, per ora).

Se , potrebbe capitare che più chiavi abbiano la stessa ricerca di scansione. Anche in questo caso però, finché la tabella non è piena, si potranno sempre inserire degli elementi.

Implementando la cancellazione, non è più possibile fermarsi durante la ricerca se si trova una cella vuota: si dovrebbe scorrere tutta la ricerca di scansione, ma si può ottimizzare con il seguente metodo:

• All’inizio la tabella hash conterrà un valore in ogni cella ( sta per vuoto).
• Quando un elemento viene eliminato, viene messo un valore ( sta per deleted).
• In fase di ricerca, mi fermo solo se trovo una cella che contiene (non se contiene ).

In generale, il metodo d’indirizzamento aperto è efficace quando non sono previste eliminazione (o comunque ne servono poche).

// non si considera la variante con valori 'd' ammessi
void insert(HashTable T, int k) {
	int i = 0;
	while (i < m && T[ h(k, i) ] != 'v')
		i++;
	
	if (i < m) {
		T[ h(k, i) ] = k;
	}
}
 
bool search(HashTable T, int k) {
	int i = 0;
	while (i < m && T[ h(k, i) ] != 'v') {
		if (T[ h(k, i) ] == k)
			return true;
		i++;
	}
	return false;
}

Se la tabella ha un fattore di carico , la ricerca senza successo ha complessità media .

• Supponendo (ovvero metà tabella è piena), l’operazione di ricerca, in media, è .
• Supponiamo (ovvero la tabella è piena al 90%), l’operazione di ricerca, in media, è .

Se la tabella ha un fattore di carico , la ricerca con successo ha complessità media .

• Supponendo (ovvero metà tabella è piena), l’operazione di ricerca, in media, è .
• Supponiamo (ovvero la tabella è piena al 90%), l’operazione di ricerca, in media, è .

Come implementare la funzione hash, che ricordiamo:

• deve ritornare una permutazione diversa per ogni chiave diversa
• dovrebbe rispettare l’ipotesi dell’hashing uniforme

Scansione Lineare

Definiamo una funzione ausiliaria: (può essere implementata con il metodo di divisione o moltiplicazione, ad esempio)
La funzione hash diventa quindi:
Prende il nome di Scan Lineare (perché appunto una volta presa la posizione viene effettuato uno shift di posizioni).
Le permutazioni sono però e non come quelle supposte dall’ipotesi dell’hashing uniforme.
Soffre del problema dell’agglomerazione primaria: la probabilità della singola cella si somma con quella delle celle occupate che la precedono. Si creano quindi dei blocchi di celle occupate. Esempio

Scansione Quadratica

Anche qui le permutazioni sono esattamente per chiave, siamo quindi ancora lontani dall’ipotesi di hashing uniforme.
Questa scansione soffre del problema dell’agglomerazione secondaria: simile a quella primaria ma con effetti inferiori.

Hashing Doppio

Si utilizzano due funzioni ausiliarie:

• 
  La definizione è la seguente:
  Le permutazioni sono , che è più accettabile.