Hash table: differenze tra le versioni

Versione delle 23:52, 22 ago 2011

Versione delle 23:55, 22 ago 2011

Riga 12:

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ò non bastare,: infatti le prestazioni di una ''hash table'' sono fortemente legate anche al cosiddetto [[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==