Hash table: differenze tra le versioni

Versione delle 22:43, 3 dic 2009

Versione delle 19:41, 19 apr 2010

Riga 21:

* '''Scansione quadratica''': Quando viene incontrata una collisione non si fa altro che utilizzare l'indice che collide elevato al quadrato con normalizzazione rispetto alla grandezza della tabella dell'indice ottenuto, sino a che non si trova una casella libera.

* '''Hashing doppio''': se facendo l'hash di una chiave si incontra una collisione, allora si somma all'indice ottenuto il risultato di una nuova funzione hash (generalmente diversa dalla prima e che ha come parametro l'indice ottenuto precedentemente), e si tenta l'inserimento nel nuovo indice cosi' ottenuto, riapplicando la seconda funzione sino a che non si trova una casella libera.

* '''Concatenazione (o con lista di trabocco)''': per ogni cella della tabella di hash si fa corrispondere invece di un elemento, una [[Lista (informatica)|Lista]] (solitamente una [[LinkedList|lista concatenata]]). In questo modo un elemento che collide viene aggiunto alla lista corrispondente all'indice ottenuto.

== Hashing statico ==