Dizionari mediante “Hashing”

Prendiamo in considerazione la generica algebra eterogenea “parti di A” così definita:
Parti di A = A, Subset(A), Bool, Membro, Inserisci, Elimina, \emptyset, a_1, a_2, \dots , a_n

Dove:

  • A è un insieme di elementi ( A = \{ a_1, a_2, \dots , a_n \} )
  • Subset(A) è una famiglia di sottoinsiemi di A
  • \emptyset è l’insieme vuoto
  • Bool è l’insieme composto dagli elementi “vero e falso” ( Bool = \{ vero, falso \} )

Mentre:

  • Membro(Y, x) = \{ vero se x \in Y; falso altrimenti \}
  • Inserisci(Y, x) = Y \bigcup \{ x \}
  • Elimina(Y, x) = Y- \{ x \}

Utilizziamo l’algebra appena definita per implementare un dizionario con tecniche di “Hashing”.
Una funzione di hashing è una funzione h:a \to \{ 0, 1, 2, \dots , m-1 \} , con h che può essere calcolata in tempo costante. Ogni elemento che implementa “parti di A” (quindi ogni insieme o sottoinsieme) è descritto da un vettore (V[0], V[1], \dots , V[m-1]) , ogni elemento V[k] rappresenta un puntatore alla lista (L_k = e_{k1}, \dots , e_{{ks}_{k}} ) che contiene tutti gli elementi di A appartenenti all’insieme (o al sottoinsime) k -esimo.

La funzione h è tale che h(e_{kj}) = k \cdot (1 \le j \le s_k) , essa restituisce l’indice di un insieme (o di un suo sottoinsieme) dato un elemento in esso contenuto.

In sintesi:

V = insieme dei sottoinsiemi
V[0] = uno dei sottoinsiemi
e_01 = elemento 1 del sottoinsieme 0

Complessità

Le varie procedure che vengono implementate sugli hashing possono essere così descritte:

  1. Calcola h(a) ;
  2. Appendi a alla lista L_{h(a)} / Elimina a dalla lista L_{h(a)} / Controlla se a è presente nella lista lista L_{h(a)} .

Consideriamo per esempio l’operazione di inserimento, l’analisi del suo caso peggiore non è molto incoraggiante, può avvenire infatti, che la funzione associ tutti gli n elementi al medesimo valore h(a) . In questi casi, il numero di operazioni che vengono svolte sulla lista puntata V[h(a)] sono nell’ordine di \sum_{k=1}^{n} k = 1/2 \cdot n \cdot (n+1) = \Theta (n^2) .

L’analisi del caso medio si dimostra però più vantaggiosa, supponendo che ogni valore h(x) abbia probabilità \frac{1}{m} di essere selezionato, allora ogni lista conterrà al più \frac{n}{m} valori, inoltre avrà tempo medio di esecuzione uguale a O( \frac{n}{m} \cdot n) .

Si possono costruire programmi molto efficiente in caso di esecuzione off-line, ovvero se il contenuto di S è già noto prima dell’esecuzione.