Tabella di hash

Struttura dati usata per mettere in corrispondenza una chiave con un dato valore.
Viene usata per l'implementazione di strutture dati astratte associative.
Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare circa in tempo costante T(n) ～ O( 1 )
L'hashing è un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca nei quali le chiavi di ricerca non presentano questa proprietà.
Una ricerca basata sull'hashing cerca di accedere agli elementi della tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indici della tabella.

Le tabelle di hash sono caratterizzate da 3 operazioni:
  • insert: inserisce un nuovo elemento, con un certo valore (unico) di un campo chiave
  • search: determina se un elemento con un certo valore della chiave esiste e in tal caso lo restituisce
  • delete: elimina l'elemento identificato dal campo chiave, se esiste
Si vuole ottenere per le 3 operazioni fondamentali una complessità pari a
  • O( 1 ) nel caso più frequente
  • O( n ) nel caso peggiore

vettori associativi: vettori indicizzabili per contenuto (tramite funzione di hashing) anzichè per prosizione. Ad ogni elemento è associata una chiave. Ad ogni chiave è associato un indirizzo del vettore e viceversa.

Ogni elemento è memorizzato ad un certo indirizzo di un vettore.
L'indirizzo viene calcolato da un'opportuna funzione di hash in tempo O( 1 )
complessità: O( 1 )
occupazione: O( |U| ) numero di valori diversi assunti dal campo chiave

Nella maggior parte dei casi, il numero di elementi del dizionario |K| << |U|  numero di valori possibili delle chiavi.
Quando l'universo delle chiavi è vasto non è quindi possibile allocare il vettore T
Una tabella di hash è una struttura dati con un'occupazione di spazio O( |K| ) e tempi di accesso O( 1 ) nel caso medio

Funzione di hash h: U --> [0, m-1]    m size vettore
Ogni qualvolta h( ki ) = h( kj ) con ki != kj si verifica una collissione
Occorre:
  1. minimizzare il numero di collissioni ottimizzando la funzione di hash
  2. gestire le collissioni residue, quando avvengono,
    1. permettendo a più elementi di risiedere nella stessa locazione (chaining)
    2. ricercare un'altra posizione per insierire l'elemento (open addressing)

a. Ridurre le collissioni

Le funzioni di hash migliori sono quelle che distribuiscono il più uniformente possibile i |K| elementi tra gli m indirizzi a disposizione.
La funzione h(k) deve sembrare il più "casuale" possibile.
Solitamente si effettuano manipolazioni sui bit della chiave k, unitamente ad una scelta di un numero primo per il valore di m.
- usare tutti i bit della chiave e non sottosequenze di questi
- amplificare le differenze
  • hashing per divisione
    h(k) = k mod m
    m >= n/a  per garantire la complessità voluta (a fattore di carico della tabella di hash)
    Scelta di m:
    • lontano da potenze di 2: usa solo ultimi bit di k
    • lontano da potenze di 10 se numeri decimali
    • numero primo
  • hashing per moltiplicazion
    h(k) = floor( m * frac( k * C ) )
    0<C<1
    La moltiplicazione per C rimescola i bit di k, la moltiplicazione per m riespande l'intervallo [0,1] a [0,m-1]
    Scelta di m:
    • potenza di 2 per agevolare l'operazione di moltiplicazione ed estrazione parte intera
  • hashing universale
    Tutte le funzioni di hashing sono suscettibili di comportamenti degeneri nel caso di scelta cattiva delle chiavi.
    Si può pensare di randomizzare la scelta della funzione h(k) per proteggerla contro i casi peggiori
    Ad ogni esecuzione del programma si sceglie a caso una funzione di hash tra un insieme di funzioni predefinite.

b. Gestione delle collisioni residue

chaining: liste di collisioni
È permesso a più elementi di risiedere nella stessa locazione della tabella.
Ogni locazione  del vettore associativo è quindi un insieme di elementi implementato sotto forma di liste concatenate (lista non ordinata).
Complessità:
  • inserimento in testa: O( 1 )
  • ricerca:                     O( lunghezza lista )          O( 1 + a)
  • cancellazione:           O( lunghezza lista )
Se il numero m di slot cresce proporzionalmente ad n (a cost) e h(k) distribuisce uniformemente gli elementi allora la funzione di ricerca in una tabella di hash con chaining è O( 1+ a) = O( 1 )

open addressing
Ogni cella della tabella di hash può contenere 1! elemento e non è quindi necessario gestire le liste di collissione.
In caso di collissione si ricerca un'altra cella non ancora occupata.
Funzina solo con a < 1.