Sto leggendo l'implementazione del filtro Bloom scritta in ruby. Dovrebbe avere k funzioni hash, ma sembra che la stessa funzione di hash venga utilizzata con valori di seme diversi. È un modo comune per implementare questa struttura dati o è solo un esercizio in questo caso?
def make_mask(key)
@__mask.clear
0.upto(@num_hashes.to_i - 1) do |i|
hash = Zlib.crc32(key, i + @seed)
@__mask.set(hash % @size, 1)
end
return @__mask
end
Sì, la letteratura indica che è ok, e comune, riutilizzare una funzione hash per produrre k hash functions , in particolare se la funzione hash assume un valore seme. Questo è apparentemente il caso nell'esempio Ruby che hai fornito. Per k grandi, la ricerca di funzioni hash uniche può essere difficile. Certo, questo suppone una buona funzione di hash, in primo luogo.
Non solo è possibile riutilizzare una funzione di hash, ma un singolo valore di hash può essere suddiviso in campi di bit separati. Ciò aiuta l'efficienza del runtime in quanto riduce il numero di chiamate hash effettive e poiché sappiamo che k domina le prestazioni dell'algoritmo, questa potrebbe essere una valida ottimizzazione. Per una buona funzione di hash, le regioni di bit di un singolo valore di hash dovrebbero essere chiavi hash indipendenti a sé stanti. In altre parole, posso chiamare hash (i) per produrre un risultato a 64 bit, quindi suddividerlo in 4 sottochiave a 16 bit che possono produrre un k di 4. Molto più efficiente dell'iterazione tramite 4 chiamate di hash . Se consideri di solito mod il valore hash di una piccola dimensione del bucket, spesso non utilizziamo tutto il potenziale di una chiave hash per una tabella hash e i filtri Bloom ci danno un modo migliore per farlo.
Leggi altre domande sui tag data-structures ruby