Hash table: differenze tra le versioni

Versione delle 12:43, 28 nov 2009

Versione delle 12:44, 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 <math>0</math> ed n<math>m-1</math> che viene utilizzato come indice in un [[array]] di lunghezza n. Supponendo che <math>U</math> sia l'universo delle chiavi e <math>T[0 ... m-1]</math> una tabella hash, una funzione hash stabilisce una corrispondenza tra <math>U</math> e le posizioni nella tabella hash, quindi:

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

Riga 13:

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.

==Gestione delle collisioni==