Dinamica hashing perfetto e universale, funzioni di hash - spiegazione per favore?

Question

Quindi sto leggendo su tabelle di hash, funzioni hash, etc.Ero curioso di leggere su wikipedia su come "dynamic perfetta hashing" comporta l'uso di una seconda tabella hash in quanto la struttura dati per memorizzare più valori all'interno di un secchio.

Dove mi sono perso, però, è quando si tratta di come un universale funzione di hash è scelto di eseguire l'hashing per il secondo la tabella di hash.Qualcuno può spiegare come questo universale funzione di hash è determinato dai valori memorizzati nel secchio?Ho vagamente seguendo il ragionamento e la logica, wikipedia universale "funzione di hash" pagina, ma sto lottando per avere qualche intuizione su di esso.In particolare, in che modo queste funzioni di garanzia senza scontri?O almeno, se sono smaltiti e ne viene generato uno nuovo se un scontro è rilevato, come facciamo a sapere che questo può essere fatto in un realistico quantità di tempo, se non del tutto?

Coccinella libro spiegazione per favore?

Answer 1

Perfetto hashing significa che l'accesso in lettura richiede tempo costante, anche nel caso peggiore.

Per l'inserimento di chiavi non ci sono il peggior caso di garanzie, il tempo, i limiti sono solo vere in media (o forse ammortizzato).

Per fare l'inserzione abbastanza veloce il secondo livello di tabella hash è scelto molto grande per il numero di chiavi (k²), abbastanza grande in modo che le collisioni diventare sufficientemente improbabile.Questo non è un problema di w.r.t.dimensioni, dato che il primo livello di hash distribuisce le chiavi in modo uniforme in modo che, in media, di secondo livello, le tabelle hash sono ancora piccoli.

La funzione di hash per il secondo livello di tabelle sono scelti a caso da un insieme di con parametri funzioni di hash.

Answer 2

Come di guardare alcune lezioni del MIT? :)
Introduzione del MIT agli algoritmi, conferenze 7 e 8: hashing