Hash filter Bloom: lebih atau lebih besar?

Dalam menerapkan filter Bloom, pendekatan tradisional membutuhkan beberapa fungsi hash independen. Kirsch dan Mitzenmacher menunjukkan bahwa Anda sebenarnya hanya membutuhkan dua, dan dapat menghasilkan sisanya sebagai kombinasi liniernya.

Pertanyaan saya adalah: apa, sungguh, perbedaan antara dua fungsi hash dan satu dengan dua kali entropi?

Ini berasal dari melihat apa yang sebenarnya Anda lakukan dengan output dari fungsi hash Anda: Anda akan mengambil nilai hash 64-bit Anda dan skala ke ukuran vektor bit Anda, yang mungkin secara signifikan lebih kecil dari 2 ⁶⁴ . Ini jelas merupakan transformasi kehilangan entropi (kecuali dalam kasus yang jarang terjadi, ukuran hash Anda dan kapasitas filter persis bertepatan). Dengan asumsi filter saya memiliki kurang dari 2 ³² entri, apa yang menghentikan saya dari membagi nilai hash 64-bit saya menjadi dua hash 32-bit dan mengambil kombinasi linear dari itu? Atau menggunakannya untuk menaburkan PRNG?

Dengan kata lain, berapa banyak informasi yang sebenarnya perlu saya ketahui tentang setiap elemen yang saya masukkan ke dalam filter Bloom untuk memastikan standar tingkat false positive bertahan? Atau lebih umum, apa hubungan antara seberapa baik saya bisa membedakan elemen (berapa banyak bit yang saya gunakan untuk menggambarkannya) dan bagaimana kinerja filter Bloom saya?

Jelas sepertinya saya bisa lolos dengan bit untuk ukuran filter m , atau setara 2 ( lg ( - n ln p ) - 2 lg ( ln 2 ) ) bit untuk menyimpan n elemen dengan probabilitas positif palsu p ....$2\lg(m)$$m$$2(\lg(-n\ln{p}) - 2\lg(\ln2))$$n$$p$

Anda benar untuk memikirkan fungsi hash dalam hal "bit acak yang diproduksi". Jadi jika Anda memiliki fungsi hash yang menghasilkan hash 64 bit, Anda dapat memperlakukannya sebagai 4 hash 16-bit (dengan memisahkan), dan seterusnya.

Untuk skema yang dijelaskan di atas (yang seharusnya dikaitkan dengan Dillinger dan Manolios; Kirsch / Mitzenmacher baru saja menganalisisnya), itu berarti Anda benar; jika Anda memiliki fungsi hash tunggal dengan$2 \lg(m)$ bit, kamu harus baik-baik saja.