Ripasso

Indirizzamento diretto

Usa una struttura dati semplice (es: array, matrici, ecc) $T$ e un insieme universo $U$, $|U|=u$.

Ogni posizione di $T$ è una chiave dell’universo $U$, ogni posizione ha poi $i$ puntatori ai vari elementi (o direttamente l’elemento).

Se per una chiave $k \in U$ non ci sono elementi: $T[k]=nil$.

Accesso, elimina e inserimento di un elemento in $O(1)$-time, data la chiave $k$, l’input $x$ e la posizione $k[x]$ (o la posizione è direttamente $x$)

Problemi:

• Se l’universo $U$ è “grande” si possono avere problemi di memoria a memorizzare $T$
• dato l’insieme $K\subseteq U$ di chiavi utilizzate ($T[k] \neq nil$) si ha $|K| < |U|$

Soluzione: hash tables

• si richiede $\Theta(|K|)$-space
• operazioni in $\Theta(1)$-time

Funzioni di hash

Se con l’accesso diretto l’elemento con chiave $k$ era memorizzato in posizione $k$, con l’hash è memorizzato in $h(k)$.

Definizione: Funzione di hash

• $h$ funzione di hash t.c. $h:U\rarr\{0,..., m-1\}$
• dominio: insieme universo $U$, $|U|=u$
• codominio: insieme di posizioni $\{0, ..., m-1\}$ di una tabella hash $T$