Hash table: differenze tra le versioni

Versione delle 12:36, 28 nov 2009

Versione delle 12:40, 28 nov 2009

Riga 7:

==Funzionamento e Implementazione==

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la ''funzione di hash'': il dato da indicizzare viene trasformato da un'apposita funzione di [[hash]] in un intero compreso tra 0 ed n-1 che viene utilizzato come indice in un [[array]] di lunghezza n. Una funzione hash stabilisce una corrispondenza tra l'universo <math>U</math> delle chiavi e le posizioni nella tabella hash, che possono essere indicate come <math>T[0 ... m-1]</math>, quindi:

<math>h:U \rightarrow {0,1,...,m-1}</math>

Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di [[hash]] ''perfetta'', ovvero totalmente [[iniettiva]], è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo.

Il caso in cui la funzione hash applicata a due chiavi diverse genera un medesimo indirizzo viene chiamato '''collisione''' e può essere gestito in vari modi. La scelta di una buona funzione di hash è indispensabile per ridurre al minimo le collisioni e garantire prestazioni sempre ottimali. Il risultato migliore si ha con funzioni pseudo-casuali che distribuiscono i dati in input in modo uniforme.

Molto spesso però, una buona funzione di hash non può bastare, infatti le prestazioni di una ''hash table'' sono fortemente legate anche al cosiddetto [[fattore di carico (Informatica)|fattore di carico]] (''load factor'') calcolato come Celle libere/Elementi presenti e che ci dice quanta probabilità ha un nuovo elemento di collidere con uno già presente nella tabella. Questa probabilità, in realtà, è più alta di quanto si possa pensare, come ci dimostra il [[paradosso del compleanno]]. È bene dunque mantenere il load factor il più basso possibile (di solito un valore di 0.75 è quello ottimale) per ridurre al minimo il numero di collisioni. Questo può essere fatto, ad esempio, ridimensionando l'array ogni volta che si supera il ''load factor'' desiderato.