FunzioneHash < Labprog2pz

---+++ Un esempio di Funzione Hash

Una buona regola per la definzione di una funzione hash &egrave; che tutti i bit della chiave siano utilizzati per calcolare il risultato della funzione.

Nel caso in cui la chiave &egrave; una stringa, una semplice funzione che soddisfa il precedente requisito &egrave; la seguente.

Supponiamo che c<sub>0</sub>, c<sub>1</sub>, c<sub>2</sub>, ..., c<sub>n</sub>, sia la sequenza dei codici ASCII dei caratteri che formano la stringa S (lunga n). Tenendo conto che un codice ASCII &egrave; compreso tra 0 e 255, possiamo associare pensare che la stringa sia la rappresentazione in base 256 del numero
<div align=center>
ASCII(S) = c<sub>0</sub> + c<sub>1</sub> * 256 + c<sub>2</sub> * 256<sup>2</sup> + ... + c<sub>n</sub> * 256<sup>n</sup>
</div>
suppponendo che S<sub>i</sub> &egrave; il prefisso di lunghezza n della stringa S, la precedente funzione pu&ograve; essere definita per mezzo della seguente formula di ricorrenza:
<div align=center>
<table width="600">
<tr><td align="center">
ASCII(S<sub>0</sub>) = c<sub>0</sub>
</td>
<td align="center">
ASCII(S<sub>i+1</sub>) = ASCII(S<sub>i</sub>) * 256 + c<sub>i+1</sub>
</td></tr>
</table>
</div>

La funzione di hashing pu&ograve; quindi essere definita come
<div align=center>
HASH(S) = ASCII(S) mod N
</div>
dove N &egrave; la dimensione della tavola hash.

Si osservi per&ograve; che un calcolo diretto di ASCII(S) porta sicuramente (per n maggiore del numero di byte degli interi) ad un overflow. Per evitare che durante il calcolo si superi il valore di INT_MAX occorre sfruttare la seguente propriet&agrave; del modulo
<div align=center>
(a + b) mod N = (a mod N + b mod N) mod N 
</div>




-- Users.StefanoGuerrini - 19 Apr 2005
This topic: Labprog2pz > WebHome > FunzioneHash
Topic revision: r3 - 2005-04-19 - StefanoGuerrini