Hash table: differenze tra le versioni

Versione delle 12:13, 12 set 2017

Versione delle 03:55, 5 gen 2018

Riga 34:

Il vantaggio dell'indirizzamento aperto sta nel fatto che esclude completamente i puntatori, ''calcoliamo'' la sequenza delle celle da esaminare ('''''ispezione''''').

Un concetto importante al riguardo è il cosiddetto '''hashing uniforme.''' Rappresenta l'hashing ideale, ovvero ogni cella della tabella ha la stessa probabilità di contenere un dato elemento.

Esistono diverse tecniche di ispezione, le tre tecniche più comunemente utilizzate sono: ispezione lineare, ispezione quadratica e doppio hashing. Tuttavia, nessuna di queste tecniche soddisfa l'ipotesi di hashing uniforme, in quanto nessuna di esse è in grado di generare più di <math>m^2</math> sequenze di ispezione differenti (anziché <math>m!</math>, come richiede l'hashing uniforme).