Quali sono le "nuove funzioni hash" nell'hash cuckoo?

sto leggendo di cuculo hashing da Pagh e Rodle e non riesco a capire il significato di questo paragrafo:.Quali sono le "nuove funzioni hash" nell'hash cuckoo?

Può accadere che questo processo loop, come mostrato in figura 1 (b). Pertanto il numero di iterazioni è limitato da un valore "MaxLoop" a specificato nella Sezione 2.3. Se viene raggiunto questo numero di iterazioni, , riutilizziamo le chiavi nelle tabelle utilizzando nuove funzioni di hash e proviamo ancora una volta a per inserire la chiave nestless. Non è necessario per allocare nuove tabelle per il rehashing: è possibile eseguire semplicemente le tabelle da eliminare ed eseguire la normale procedura di inserimento su tutti i tasti rilevati non nella posizione prevista nella tabella.

Cosa significa per utilizzando le nuove funzioni di hash?
Nell'algoritmo di inserimento la tabella viene ridimensionata. Dovremmo avere un "pool" di funzioni hash da usare in qualche modo? Come creiamo questo pool?

fonte

2015-05-31 Jim

Sì, si aspettano nuove funzioni di hash, proprio come si suol dire. Fortunatamente, non richiedono una pila di nuovi algoritmi, solo un comportamento di hashing leggermente diverso sul set di dati corrente.

Dai un'occhiata alla sezione 2.1 del documento, quindi all'Appendice A. Si discute la costruzione di un numero casuale universal hash functions.

Un semplice esempio, si spera, illustrativo, è supporre di avere una normale funzione di hash che ti piace, che funziona su blocchi di byte. Lo chiameremo H(x). Si desidera utilizzarlo per produrre una famiglia di nuove funzioni hash leggermente diverse H_n(x). Bene, se H(x) è buono e le tue esigenze sono deboli, puoi semplicemente definire H_n(x) = H(concat(n,x)). Non hai buone garanzie riguardo ai comportamenti di H_n(x), ma ti aspetteresti che la maggior parte di loro sia diversa.

fonte

2015-05-31 16:09:32

Se ho capito correttamente, a) ottenere una nuova funzione di hash da questo set che si menziona e mantenere fissa la dimensione della tabella o b) ridimensionare la tabella utilizzando le stesse 2 funzioni di hash e non cambiandole mai? – Jim

Entrambe le opzioni interromperanno quasi certamente il ciclo corrente. Se non ti preoccupi della quantità di spazio che occuperai, il ridimensionamento potrebbe essere più utile, poiché ridurrà le probabilità di un altro ciclo (fino a quando non avrai più chiavi memorizzate, comunque). Tieni presente che il ridimensionamento è una specie di modifica della funzione di hash, perché probabilmente stai usando la funzione di hash modulo la dimensione delle tabelle; aumenta le dimensioni e cambierai dove finiscono le cose. –

Quindi, se usiamo (a), cioè un nuovo hash che mantiene fissa la dimensione della tabella, come viene determinata la dimensione della tabella? Dal giornale non mi è chiaro. Se il numero di chiavi da inserire è sconosciuto, come è possibile ricavare alcune dimensioni della tabella per l'algoritmo del cuculo? – Jim

Quali sono le "nuove funzioni hash" nell'hash cuckoo?

risposta

Problemi correlati