Originariamente inviato da YuYevon
[b]Una funzione hash è una funzione che, presa in input una chiave (che può essere un numero o magari una stringa che viene convertita in numero), restituisce un certo valore numerico[b] (chiamato valore hash, codice hash, hash e basta o in altri modi). Ad ogni chiave è associato un solo valore, ma un certo valore può corrispondere a più chiavi diverse (ed è per questo che poi ci sono le collisioni). Una buona funzione hash deve essere "uniforme", cioè deve fare in modo di distribuire le varie chiavi su tutto il range dei valori possibili; per intenderci, una pessima funzione hash sarebbe quella che per ogni chiave genera sempre lo stesso valore, perché se così fosse tutti gli elementi colliderebbero e di fatto si avrebbe un'unica enorme lista con tutti gli elementi possibili (rendendo di fatto inutile e anzi controproducente il ricorso alla tabella hash, perché ricorrendo direttamente alla lista concatenata almeno non si perderebbe il tempo ogni volta per il calcolo dell'hash ma solo per la ricerca nella lista).

Se una funzione hash può avere in input 500 chiavi diverse e i valori che assume sono 100, allora l'ideale sarebbe che, su ogni valore, siano mappate 500/100=5 chiavi. Questa sarebbe la funzione ideale, nella pratica si cerca di realizzare qualcosa che tenda a questo grado di uniformità.



Se il valore hash calcolato per questi elementi è stato generato già per altri elementi, allora si ha la collisione e un modo per gestire il problema è appunto la concatenazione, creando una lista. Poi ce ne sono altri come l'indirizzamento aperto, ma per quello che ne so nella gestione della memoria dei SO si ricorre sempre alla concatenazione.
Daccordo e questa funzione hash crea quindi una chiave che sia "facile da trovare" no? è questo lo scopo? creando un determinato algoritmo (basato su cosa? su che dati lavora che può ricreare più volte la stessa chiave?) che a seconda dei dati in input crea questa hash. Ma come fa a ricreare "eroneamente" chiavi hash uguali?