布隆过滤器容量如何评估？

作者：程序员马丁

note

大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。

回答话术

创建布隆过滤器时有两个核心参数，一个是布隆过滤器的容量，另一个是误判率。

布隆过滤器的容量取决于系统数量需求。以用户名全局唯一不能重复功能举例，我们需要把已经注册的用户名放到布隆过滤器中，这样就可以直接通过布隆过滤器来判断用户名是否存在，而不需要和数据库交互。

在这种场景下，布隆过滤器的容量就取决于系统的用户数量，需要产品去评估系统已有用户的数量，以及未来很长一段时间的增长量，得出一个经验值，然后设置为布隆过滤器的容量。

建议可以适当设置大一些，不然的话，当用户数量接近布隆过滤器容量时，会出现较大可能性误判问题。当然也不能设置太大，会造成一定空间的浪费。最终设置的值需要在误判和空间之间做一个取舍。

误判率参数，意味着布隆过滤器判断某个元素存在时的错误概率。误判率越低，通常需要更大的位数组容量以及新增和查询元素时性能的降低。布隆过滤器增加和查询元素的时间复杂为 O(N)，N 取自于布隆过滤器的 Hash 函数数量，误判率越低，就需要更多复杂的 Hash 函数，那新增和查询操作时自然就会变慢。

如果初始化一个 1 亿元素误判率在千分之一的布隆过滤器，大概占据内存 171M 左右。

另外在对布隆过滤器进行初始化的时候，会一次性申请对应的内存，这个需要额外注意下，避免初始化超大容量布隆过滤器时内存不足问题。