详解布隆过滤器的原理，使用场景和注意事项
2021-07-24 22:06:08
布隆过滤器是一种高效且空间占用较少的概率型数据结构，其特点在于能够高效地插入和查询元素，但返回的结果是概率性的，即可以告诉你“某样东西一定不存在或者可能存在”。相比于传统的List、Set、Map等数据结构，布隆过滤器在存储效率和查询速度上具有显著优势，但牺牲了结果的精确性。
实现原理HashMap的问题：
在讲述布隆过滤器的原理之前，我们先思考一下通常判断某个元素是否存在的方法。很多人会想到HashMap，它可以在O(1)的时间复杂度内返回结果，效率极高。然而，HashMap也有其缺点，如存储容量占比高，考虑到负载因子的存在，通常空间不能被完全利用。当数据量非常大时，HashMap占据的内存会变得非常可观。此外，如果数据集存储在远程服务器上，本地服务接受输入，而数据集无法一次性读入内存构建HashMap时，也会存在问题。
布隆过滤器数据结构：
布隆过滤器是一个bit向量或bit数组。当我们要映射一个值到布隆过滤器中时，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的bit位置1。例如，对于值“baidu”和三个不同的哈希函数，分别生成了哈希值1、4、7，则bit数组中的这些位置会被置为1。
值得注意的是，由于多个值的哈希函数可能返回相同的bit位，因此这些bit位会被覆盖。当我们查询一个值是否存在时，哈希函数会返回多个哈希值，我们检查这些哈希值对应的bit位是否都为1。如果有一个bit位为0，则说明该值一定不存在。然而，如果所有bit位都为1，我们只能说该值可能存在，因为可能存在其他值的哈希函数也返回了这些bit位，导致它们被置为1。
使用场景布隆过滤器常用于减少磁盘IO或网络请求。一旦一个值必定不存在，我们可以避免进行后续昂贵的查询请求。例如，在数据库查询、缓存穿透、垃圾邮件过滤等场景中，布隆过滤器都能发挥重要作用。
注意事项不支持删除操作：传统的布隆过滤器不支持删除操作。如果需要删除元素，可以考虑使用Counting Bloom Filter等变种。
哈希函数的选择：哈希函数的选择对布隆过滤器的性能有很大影响。推荐使用性能较好的哈希函数，如MurmurHash、Fnv等。
布隆过滤器长度和哈希函数个数的选择：布隆过滤器的长度和哈希函数个数需要权衡。过小的布隆过滤器会导致误报率过高，起不到过滤的目的；而过大的布隆过滤器和过多的哈希函数会降低效率。可以使用公式来计算适合业务的布隆过滤器长度和哈希函数个数。
大Value拆分：在使用Redis等内存数据库作为布隆过滤器时，需要注意大Value的问题。布隆过滤器的不当使用极易产生大Value，增加Redis阻塞风险。因此，建议对体积庞大的布隆过滤器进行拆分，将Hash(Key)之后的请求分散在多个节点的多个小bitmap上，但确保对一个Key的所有哈希函数都落在同一个小bitmap上。
以下是布隆过滤器在插入和查询过程中的示意图：
插入值“baidu”后的示意图：
再插入值“tencent”后的示意图：
布隆过滤器是一种高效且空间占用较少的概率型数据结构，适用于需要快速判断元素是否存在的场景。然而，由于其返回的结果是概率性的，因此在使用时需要权衡误报率和效率之间的关系。同时，需要注意哈希函数的选择、布隆过滤器长度和哈希函数个数的选择以及大Value拆分等问题。
热门标签
