一个空的布隆过滤器是一个具有m个比特的位数组（bit array），每个比特位都初始化为0。定义k个不同的符合均匀随机分布的哈希函数（hash function），每个函数都将集合中的元素映射到m个位置中的一个。假设有n个元素需要判断，那么k是一个正比于n而且远小于m的常数。需要选取的k的具体数值需要根据要求的误报率来决定。 

向集合中添加元素时，对于每个元素，将这个元素分别放到k个哈希函数中，因此可以在位数组中得到与这个元素相对应的k个位置，将这些位置在数组中对应的值设置为1。 

当要判断某一个元素是否属于一个集合时，同样将这个元素放入k个哈希函数中，获得k个位置。如果这k个位置中有一位为0，那么可以肯定的是，这个元素一定不在数组中。这是因为，如果这个元素在集合中，那么在向集合中添加该元素的时候，对应的位置肯定已经都被设置为1。如果这k个位置都是1，那么要么元素在集合里，要么所有这些位置都在其他元素插入的过程中被设为1了，导致一次“误报”。

假设每个哈希函数按照相同的概率选择位数组中的每个位置，也就是说每个元素等概率地哈希到位数组的m个比特位上。那么，在插入一个元素时，一个特定的比特没有被任意哈希函数设置为1的概率是：。插入n个元素后，这个比特仍然为0的概率是：。所以，这个比特位被设置为1的概率是：。因此，对于一个不在集合中的元素，经过哈希之后被判断为在集合中的概率（也就是误判率）是，这个值在m和n非常大时趋向于。 对于m和n确定时，如何选取k能够使得误判率最低? 如果不考虑k必须为正整数的约束条件，的极小值点在处取到。因此，给定了需要保证的误判率以及m和n，可以根据上述式子计算出k的取值。

如果允许误报，布隆过滤器相对于其他用于表示集合的数据结构来说具有很强的空间优势，例如自平衡二叉搜索树（self-balance BST）、字典树（tries）、哈希表（Hash table）（见散列表）或者简单的数组（array）、链表（linked list），它们中大多数至少都要存储元素本身，对于小整数需要少量的比特，对于字符串则需要任意多的比特（字典树是个例外，因为对于有相同前缀的元素可以共享存储空间）。对于一个有1%误报率和一个最优k值的布隆过滤器来说，无论元素的类型及大小，每个元素只需要9.6比特来存储。这个优点一部分继承自数组的紧凑性，一部分来源于它的概率性。如果对每个元素每增加4.8比特，就可将误报率降低为原来的1/10。添加元素和做出判断的时间复杂度都为，与集合中元素的多少无关，这是其他数据结构都不能完成的。如果可能元素范围不是很大，并且大多数都在集合中，则使用确定性的位数组远远胜过使用布隆过滤器。因为位数组对于每个可能的元素空间上只需要1比特，添加和判断的时间复杂度只有。注意到这样一个哈希表（位数组）只有在忽略冲突并且只存储元素是否在其中的二进制信息时，才会获得空间和时间上的优势，而在此情况下，它就成为k=1的布隆过滤器。而当考虑到冲突时，对于有m个位置的位数组或者其他哈希表（即k=1的布隆过滤器），如果想要保证1%的误判率，则该位数组只能存储m/100个元素，因而有大量的空间被浪费，同时也会使得空间复杂度急剧上升，这显然不具有空间有效性。解决的方法很简单，使用k＞1的布隆过滤器——即使用k个哈希函数将每个元素映射到k个比特，从而大幅降低误判率同时提高空间利用效率。