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 c₀, c₁, c₂, ..., c_n, 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

suppponendo che S_i è il prefisso di lunghezza n della stringa S, la precedente funzione può essere definita per mezzo della seguente formula di ricorrenza:

La funzione di hashing può quindi essere definita come

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

-- StefanoGuerrini - 19 Apr 2005