Hash dinamico perfetto e funzioni hash universali - spiegazione per favore?

Question

Quindi sto leggendo su hash tables, hash, ecc. Sono stato incuriosito di leggere su wikipedia su come "dynamic perfect hashing" implica l'uso di una seconda hash table come struttura dati per memorizzare più valori all'interno di un particolare bucket.

Tuttavia, dove mi perdo, è il modo in cui viene selezionata una funzione di hash universale per eseguire l'hashing per la seconda tabella hash. Qualcuno può spiegare come viene determinata questa funzione di hash universale dai valori memorizzati nel bucket? Seguo vagamente il ragionamento e la logica nella pagina "funzione di hash universale" di wikipedia, ma sto lottando per avere intuito su di esso. In particolare, in che modo queste funzioni non garantiscono scontri? O almeno, se vengono eliminati e ne viene generato uno nuovo se viene rilevato uno scontro, come facciamo a sapere che questo può essere fatto in un lasso di tempo realistico se non del tutto?

spiegazione libro coccinella per favore?

Answer 1

Hash perfetto significa che l'accesso in lettura richiede un tempo costante anche nel caso peggiore.

Per l'inserimento di chiavi non ci sono garanzie del caso peggiore, i limiti di tempo sono veri solo in media (o forse ammortizzati).

Per rendere l'inserimento abbastanza veloce, la tabella hash di secondo livello viene scelta molto grande per il numero di tasti (k), abbastanza grande da rendere le collisioni sufficientemente improbabili. Questo non è un problema w.r.t. dimensione perché l'hash di primo livello distribuisce le chiavi in ​​modo uniforme in modo che le tabelle hash medie di secondo livello siano ancora piccole.

La funzione di hash per le tabelle di secondo livello viene scelta casualmente da un set di funzioni hash parametrizzate.

Answer 2

Che ne dici di guardare alcune conferenze del MIT? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing