Bloom filter adalah struktur data yang memungkinkan komputer untuk melihat apakah elemen yang diberikan muncul dalam suatu set. Bloom filter menggunakan fungsi hash untuk melakukan ini. Untuk setiap elemen yang ditambahkan, nilai hash dihitung. Ketika sebuah elemen baru ditambahkan, nilai hash-nya dibandingkan dengan elemen-elemen lain dalam set. Bloom filter adalah struktur data probabilistik. Adalah mungkin untuk mendapatkan positif palsu, tetapi tidak untuk mendapatkan negatif palsu. Dengan kata lain, sebuah kueri mengembalikan "mungkin dalam himpunan" atau "pasti tidak dalam himpunan". Elemen dapat ditambahkan ke himpunan, tetapi tidak dapat dihapus. Untuk setiap elemen yang ditambahkan, probabilitas mendapatkan positif palsu bertambah.
Edward Bloom mengusulkan filter Bloom pada tahun 1970. Dalam artikel tersebut, Bloom mengandaikan adanya algoritma untuk memberi tanda hubung pada kata-kata di akhir baris. Menurut contoh, sebagian besar kata memiliki pola tanda hubung yang sederhana. Tetapi sekitar 10% dari kata-kata tersebut membutuhkan pencarian yang memakan waktu untuk mengambil aturan yang benar. Kasusnya adalah kasus penghubung sekitar 500.000 kata. Dia melihat bahwa dengan menggunakan teknik hashing bebas kesalahan "normal", menyimpan pola tanda hubung, akan memerlukan banyak memori. Dia menemukan bahwa dengan menggunakan tekniknya, dia bisa menghilangkan sebagian besar pencarian. Sebagai contoh, area hash hanya 15% dari ukuran yang dibutuhkan oleh hash bebas kesalahan yang ideal masih menghilangkan 85% dari akses disk.
Secara umum, kurang dari 10 bit per elemen diperlukan untuk probabilitas positif palsu 1%, terlepas dari ukuran atau jumlah elemen dalam himpunan.