[Algoritmi] Correttezza funzioni hash.

[iggy]

Quindi per avere un'idea, come la faresti una funzione del genere? Una semplice, che rispetti solo l'uniformità sulla tabella.

[apatriarca]

Ti ho già fornito diversi esempi. Ci sono diverse proprietà che si possono desiderare da una funzione di hash a seconda dell'utilizzo. Selezionare 10 bit a caso dei 100 è ad esempio suriettiva e ogni valore dell'immagine ha la stessa probabilità di essere scelto. Tuttavia dipende da solo 10 bit dei valori e non è adatta a situazioni in cui i valori di input sono scelti in modo da variare poco tra di loro. Un'altra possibilità è ad esempio di calcolare \( \bigoplus_{i=0}^{10} v[10\,i .. (10\,(i-1)-1)] \) dove \(\oplus\) è l'operazione XOR e \(v[a..b]\) è il numero intero la cui rappresentazione binaria è data da i bit da \(a\) a \(b\) inclusi di \(v\). Anche questa è suriettiva e l'immagine è uniforme, ma dipende da tutti i valori. Un'alternativa simile è quella di usare la somma in modulo invece dello XOR.

Esistono tantissime funzioni possibili e quale è meglio usare dipende molto da quali proprietà si desiderano dalla funzione di hash.

[iggy]

Ok, grazie.