Hash table: differenze tra le versioni

Versione delle 00:01, 7 mag 2024

Versione attuale delle 22:57, 1 ago 2025

(4 versioni intermedie di 2 utenti non mostrate)

Riga 29:

Di seguito vengono riportati i metodi più diffusi per la gestione delle collisioni.

* '''Open Hash''' (o indirizzamento aperto)

* '''Hash con 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 [[lista concatenata]]). In questo modo un elemento che collide viene aggiunto alla lista corrispondente all'indice ottenuto.

== Open Hash ==

Riga 50:

Quando si incontra una collisione non si fa altro che utilizzare l'indice successivo a quello che collide, sino a che non si trovi una casella libera.

===== Ispezione quadratica =====

<math>h(k,i) = (h^1 (k) + c_1 i + c_2 i^2)\pmod{m}</math>

Quando si incontra 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 trovi una casella libera.

===== Doppio Hashing =====

<math>h(k,i) = (h_1 (k) + i h_2 (k))\pmod{m}</math> dove, per esempio possiamo porre <math>h_1 (k) = k \pmod{m}</math> e <math>h_2 (k) = 1 + (k \pmod{m^1})</math>.

Riga 109:

|}

dove &<math>\alpha;</math> è il fattore di carico.

==Bibliografia==