Un esempio di Funzione Hash

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

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

Supponiamo che c0, c1, c2, ..., cn, sia la sequenza dei codici ASCII dei caratteri che formano la stringa S (lunga n). Tenendo conto che un codice ASCII è compreso tra 0 e 255, possiamo associare pensare che la stringa sia la rappresentazione in base 256 del numero

ASCII(S) = c0 + c1 * 256 + c2 * 2562 + ... + cn * 256n
suppponendo che Si è il prefisso di lunghezza n della stringa S, la precedente funzione può essere definita per mezzo della seguente formula di ricorrenza:
ASCII(S0) = c0 ASCII(Si+1) = ASCII(Si) * 256 + ci+1

La funzione di hashing può quindi essere definita come

HASH(S) = ASCII(S) mod N
dove N è la dimensione della tavola hash.

Si osservi però 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à del modulo

(a + b) mod N = (a mod N + b mod N) mod N

-- StefanoGuerrini - 19 Apr 2005


This topic: Labprog2pz > WebHome > FunzioneHash
Topic revision: r3 - 2005-04-19 - StefanoGuerrini
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback