Tabelle hash

Si è sempre assunto che i nodi fossero numerati da 1 a N. Nel mondo reale, però, possono assumere anche stringhe, come ad esempio nomi di città.

Serve quindi un dizionario che implementa una relazione univoca $r:D\to C$ tra gli elementi del domino D (chiavi) e quelli del codominio C (valori).

Primitive

• new_dictionary(): restituisce un dizionario vuoto
• lookup(D, k): restituisce il valore associato in D a k se esiste, nil altrimenti
• insert(D, k, v): inserisce l’associazione k, v
• remove(D, k): rimuove l’associazione chiave-valore.

Per salvare queste coppie si possono utilizzare varie strutture dati, tra cui array, liste ecc, ma sarebbero tutte un po’ costose rispetto alle tabelle hash.

Tabelle hash

Le coppie (k, v) sono memorizzate in un array, e la posizione della coppia dipende da k, che è processata da una funzione hash.

Le tabelle ad accesso diretto funzionano solo se l’insieme universo è relativamente piccolo. Se le chiavi usate sono poche, c’è un grande spreco di memoria, perché la tabella è grande quanto l’insieme universo.

Una funzione hash si dice perfetta se $\forall k_1,k_2\in U:k_1\ne k_2,h(k_1)\ne h(k_2)$. Questo tipo di funzione è piuttosto complicata da implementare.

Problema

Può capitare che $k_1\ne k_2$, eppure $h(k_1)=h(k_2)$. Come si possono salvare entrambe le chiavi? Una funzione hash si dice uniforme, se distribuisce uniformemente le chiavi di U in M.

$P(k)$ è la probabilità che k sia inserita nella tabella. $Q(i)$ è la probabilità che una chiave venga inserita nella cella i della tabella. $Q(i)={\sum }_{kinU:h(k)=i}P(k)$.

Si vuole raggiungere $Q(i)=\frac{1}{m}\text{mbox}\forall i=0,...,m-1$

Le collisioni non vanno eliminate, ma si cerca di ridurle al minimo. Se comunque si verificano collisioni, si devono prevedere posizioni alternative, stabilire come cercare le chiavi in queste nuove posizioni e tenere bassi i costi.

Esistono due alternative:

1. liste di trabocco
2. indirizzamento aperto

Liste di trabocco

Si usa una lista per memorizzare tutte le chiavi che finiscono nella stessa cella, e le nuove chiavi vengono inserite in testa a H[h(k)].

Il caso peggiore è quello in cui tutte le chiavi sono in un’unica lista. Questo ovviamente ha il costo delle liste, che è $O(1)$ per l’insert di un nuovo elemento in testa, e $O(n)$ per il lookup e la remove, con n numero di chiavi memorizzate.

Il fattore di carico $\alpha =\frac{n}{m}$ se è > 1, allora nella tabella c’è sicuramente una collisione. n: numero chiavi m: capacità tabella hash

Se h è una funzione uniforme semplice, allora la lunghezza attesa delle liste di trabocco è $\alpha$. Per una funzione uniforme semplice, in media la ricerca della chiave per lookout e remove, costa $\Theta (1)+\alpha$ se è senza successo, mentre $\Theta (1)+\frac{\alpha }{2}$ con successo. Se $n\in O(m)$, allora $\alpha \in O(1)$, e quindi i costi sopra diventano $O(1)$.

Indirizzamento aperto

Non si utilizzano le liste per salvare le collisioni, ma piuttosto si cerca un’altra cella, partendo dall’indice h(k) e cercando anche in tutte le posizioni alternative.

h(k, 0), h(k, 1), h(k, 2), ..., h(k, m-1) con $h(k,i)\ne h(k,j),\forall i\ne j$.

Quando si cancella un elemento, si inserisce un valore speciale DEL, per capire che in quella cella c’era effettivamente un elemento, e di continuare la ricerca se ancora non si è trovato l’elemento cercato.

Hashing uniforme Ogni chiave ha la stessa probabilità di avere come sequenza di ispezione una qualunque delle $m!$ permutazioni di $[\mathrm{0..}m-1]$. Questo concetto è però di difficile implementazione.

Ispezione lineare

$h(k,i)=(h^{\prime }(k)+c\cdot i)\mathrm{mod}m$, con h(k, i) è l’ispezione i-esima per la chiave k, h'(k) è la funzione hash da applicare a k, c è la costante e i è il numero di ispezione.

Questa ispezione lineare tende a creare agglomerati.

• Il fattore di carico, però, è tra 0 e 1, $0\le \alpha \le 1$.
• La tabella di può riempire e andare in overflow

Per evitare l’overflow, quando il fattore di carico arriva a 0.5-0.75, si alloca una nuova tabella di dimensione 2m, e si spostano tutti i dati. Questa nuova tabella non ha DEL, $\alpha$ viene dimezzato e il costo per farlo è di $O(m)$.

asd_42