布隆过滤器是Burton Bloom 在1970年提出的，用于解决打标记的问题。对于每个字符串，利用k种不同的字符串hash算法，生成k个哈希值，然后把这k个值打入大小为m个bit的槽中，用以标记这个字符串已经出现。举个简单的例子，对于字符串”blog.vvbin.com”，利用k=4种不同的字符串哈希算法，产生4个哈希值：4216，3054，1017，2222。然后采用求模的方式打入m=31的bit槽中，结果如下图：
在查询时，只要查看对应的k个bit位是否为1，就可以知道当前字符串是否已经存在。
布隆过滤器通常只需传统哈希表1/8的存储空间，就可达到很好的哈希效果。假设我们有10万个字符串，鉴于hash表的存储效率大约是50%，这样我们需要20万个槽，每个槽是一个32位（8字节）的DWORD，这样我们需要160万字节空间来存储。而如果采用布隆过滤器，对于10万个字符串，我们采用160万个槽来存储，每个槽是一个bit，那么我们总共只需160万bit，也就是20万字节，即可达到比较理想的哈希效果。