Apakah filter mekar sebenarnya lebih cepat daripada hash, bahkan dengan mengambil cache akun?

Filter Bloom terlihat sangat hebat ketika Anda mempertimbangkan Anda dapat menentukan apakah Int berada di set dengan 99% kepastian dalam waktu yang konstan. Tapi begitu juga hash, dengan satu-satunya perbedaan itu, dalam hash, sebagian besar waktu Anda mengakses memori hanya sekali. Dengan filter bloom, Anda perlu mengaksesnya ~ 7 kali per permintaan di tempat yang sangat jauh , sehingga Anda akan memiliki beberapa cache yang hilang per permintaan.

Apakah saya melewatkan sesuatu?

Anda kehilangan bagaimana kedua struktur data berurusan dengan benturan hash. Filter bloom tidak menyimpan nilai aktual, sehingga ruang yang dibutuhkan adalah ukuran konstan dari array yang ditunjuk. Alih-alih jika Anda menggunakan hash tradisional, ia mencoba untuk menyimpan semua nilai yang Anda berikan, sehingga tumbuh seiring waktu.

Pertimbangkan fungsi hash yang disederhanakan (hanya untuk contoh saja!) f(x) = x % 2. Sekarang Anda masukan bilangan bulat berikut: 2, 3, 4, 5, 6, 7.

Standard Hash: nilai yang diberikan akan di-hash, dan kita berakhir dengan banyak tabrakan karena f(2) = f(4) = f(6) = 0dan f(3) = f(5) = f(7) = 1. Namun demikian, hash menyimpan semua nilai-nilai ini dan itu akan dapat memberi tahu Anda bahwa 8tidak disimpan di dalamnya. Bagaimana cara melakukannya? Ini melacak tabrakan dan menyimpan semua nilai dengan nilai hash yang sama, kemudian ketika Anda menanyakannya, itu juga membandingkan permintaan Anda. Jadi mari kita query peta untuk 8:, f(8) = 0jadi itu akan melihat ke ember di mana kita telah memasukkan 2, 4, 6dan perlu membuat 3 perbandingan untuk memberi tahu Anda bahwa 8itu bukan bagian dari input.

Filter Bloom: Biasanya, setiap nilai input hash terhadap kfungsi hash yang berbeda. Sekali lagi, untuk kesederhanaan, anggap saja kita hanya menggunakan fungsi hash tunggal f. Kita memerlukan array 2 nilai lalu dan ketika kita menemukan input 2itu berarti bahwa karena f(2) = 0kita mengatur nilai array pada posisi 0ke nilai 1. Hal yang sama terjadi untuk 4dan 6. Demikian pula, input 3, 5, 7masing-masing mengatur posisi array 1ke nilai 1. Sekarang kita kueri apakah 8itu bagian dari input: f(8) = 0dan array pada posisi 0adalah 1, sehingga filter bloom akan mengklaim bahwa 8itu memang bagian dari input.

Agar lebih realistis, mari kita tambahkan fungsi hash kedua g(x) = x % 10. Dengan itu, nilai input 2mengarah ke dua nilai hash f(2) = 0dan g(2) = 2dan dua posisi array yang sesuai akan diatur ke 1. Tentu saja, array sekarang harus berukuran paling tidak 10. Tetapi ketika kami meminta 8kami akan memeriksa array pada posisi 8karena g(8) = 8, dan posisi itu akan tetap 0. Itu sebabnya fungsi hash tambahan mengurangi false positive yang akan Anda dapatkan.

Perbandingan: Filter bloom menggunakan kfungsi hash yang berarti hingga kposisi array acak sedang diakses. Namun angka itu tepat. Sebaliknya, hash hanya menjamin Anda waktu akses konstan yang diamortisasi, tetapi dapat membatalkan pembuatan tergantung pada sifat fungsi hash Anda dan memasukkan data. Jadi biasanya lebih cepat, kecuali untuk kasus yang dihasilkan.

Namun, setelah Anda memiliki tabrakan hash hash standar harus memeriksa kesetaraan nilai yang disimpan terhadap nilai kueri. Pemeriksaan kesetaraan ini mungkin mahal dan tidak akan pernah terjadi dengan filter bloom.

Dalam hal ruang, filter bloom konstan, karena tidak pernah perlu menggunakan lebih banyak memori daripada array yang ditunjuk. Di sisi lain, hash tumbuh secara dinamis dan mungkin menjadi jauh lebih besar karena harus melacak nilai-nilai yang bertabrakan.

Trade-off: Sekarang Anda tahu apa yang murah dan apa yang tidak dan dalam situasi apa, Anda harus dapat melihat trade-off. Filter Bloom sangat bagus jika Anda ingin mendeteksi dengan cepat bahwa suatu nilai telah terlihat sebelumnya, tetapi dapat hidup dengan positif palsu. Di sisi lain, Anda dapat memilih peta hash jika Anda ingin benar kebenarannya dengan harga tidak bisa menilai secara tepat runtime Anda, tetapi dapat menerima kasus-kasus degenerasi sesekali yang mungkin jauh lebih lambat daripada rata-rata.

Demikian pula, jika Anda berada di lingkungan memori terbatas, Anda mungkin ingin memilih filter bloom untuk jaminan penggunaan memori mereka.

Kasus penggunaan untuk filter mekar dan hash berbeda dan sebagian besar terpisah, sehingga perbandingan langsung tidak masuk akal. Selain itu akan tergantung pada detail teknis dari implementasi karena ada banyak cara untuk menangani tabrakan hash dengan trade-off yang berbeda.

Filter bloom dapat menjawab apakah elemen dalam set untuk set besar , dengan probabilitas yang masuk akal, tetapi tidak tepat, menggunakan jumlah memori yang sederhana. Besar, seperti, triliunan elemen. Tetapi mereka tidak pernah tepat. Anda hanya dapat mengurangi jumlah positif palsu dengan menggunakan lebih banyak memori atau lebih banyak fungsi hash.

Di sisi lain tabel hash tepat, tetapi mereka perlu menyimpan set. Jadi triliunan elemen akan membutuhkan memori terrabytes (dan itu hanya triliunan Amerika). Mereka juga dapat menyimpan data tambahan untuk setiap elemen, yang tidak bisa disaring oleh filter bloom.

Jadi filter bloom digunakan ketika Anda memiliki metode lambat untuk mendapatkan data untuk beberapa anggota (yang melibatkan server query, membaca dari disk dan semacamnya) dari satu set besar (yang tidak sesuai dengan memori atau tidak praktis untuk mentransfernya ke klien atau semacamnya) dan ingin menghindari operasi yang lambat untuk objek yang tidak diatur.