概述

什么是布隆过滤器？布隆过滤器作为一个过滤器，可以高效地解决元素“在不在”的问题。重点是在“不在”的问题

原理

布隆过滤器结合了数组和哈希函数来做实现。
在一个元素存入过滤器的时候，过滤器会先用多个哈希函数计算对应的哈希值和数组下标。得到下标后，把响应下标的数值由 0 置 1 表示该元素存在。原理很好理解，其实就是一个有多个 hash 函数的位图数组。

优点

• 内存消耗小。因为不用将整个元素存储在内存里面，所以内存消耗大大减小
• 快。hash 值的计算可以认为是 O(1) 的，所以对于元素存在性判断，整体来说也是 O(1) 的
• 安全。内存里面没有实际的数据，不用担心泄漏

缺点

• 有误差。hash 函数不可避免的存在误差。过滤器也没有使用类似 hashMap 的链表来解决冲突，所以误差总是存在。但是对于不存在的数据，布隆过滤器的判断总是准确的
• 不能删除数据。在有冲突的情况下，删除数据可能对其他的数据也产生影响。如果不使用位图，而是通过数组进行计数，可以删除数据吗？

误差可以通过计算得到，具体参看 Bloom filter