本文共 1725 字，大约阅读时间需要 5 分钟。
布隆过滤器与布谷鸟过滤器：从误判到高效存储的进化之路
在计算机领域，IO操作一直是性能瓶颈的主要原因。无论是框架、技术还是硬件，降低IO操作的开销一直是优化的重点。今天我们聊一聊过滤器，先从一个实际场景入手。
在业务后端开发中，通常我们会先检查缓存是否有相关数据。如果有，则直接返回；如果没有，则需要从数据库查询。这时候一个问题就出现了：如果有很多请求是针对数据库根本不存在的数据，那么数据库就会频繁处理这些毫无意义的查询。这种情况下，效率会显著下降。如何解决这个问题？过滤器的出现为这个问题提供了一个解决方案。
布隆过滤器的基本思想是，当一个数据请求来时，首先检查是否存在缓存。如果存在，则将请求转发给数据库；如果不存在，则直接返回。具体实现方法是：使用一个位数组（bitmap）记录数据存储情况。当数据存入系统时，用三个不同的哈希函数计算其哈希值，并将对应的位数组位置设置为1。之后，当数据请求来时，同样用这三个哈希函数计算哈希值，如果所有对应的位数组位置都是1，则说明数据存在；如果有任何一个位置是0，则说明数据不存在。
尽管布隆过滤器能够有效地减少不必要的数据库查询，但它也存在一些明显的缺陷：
误判率高
例如，当存入数据包1时，设置位数组的1、3、6位置为1；存入数据包2时，设置3、6、7位置为1。如果一个新的数据请求3，计算得到的位数组位置为1、6、7，由于7位置是0，理论上可以判断数据不存在。但这种误判的可能性随着存储数据量的增加而增加。无法删除数据
删除数据时可能会遇到以下问题：为了解决布隆过滤器的这些问题，论文《Cuckoo Filter：Better Than Bloom》提出了布谷鸟过滤器。相比布隆过滤器，布谷鸟过滤器有以下优势：
查询性能优化
布隆过滤器需要使用多个哈希函数探测位数组中的多个位点，这会导致CPU缓存行命中率较低，从而降低查询性能。布谷鸟过滤器通过巧妙的设计，将查询性能提升到更高水平。空间利用效率
在相同的误判率下，布谷鸟过滤器的空间利用效率要高于布隆过滤器，通常可以节省40%以上的空间。同时，布谷鸟过滤器要求位数组的长度必须是2的指数，这使得其空间伸缩性相对布隆过滤器更强。支持反向删除操作
最大的优势是布谷鸟过滤器能够支持动态系统中数据的反向删除操作。布隆过滤器由于存储的是哈希值的组合，无法准确判断数据是否存在，这使得反向删除操作成为一个难题。布谷鸟过滤器通过巧妙的哈希设计和数组管理，解决了这一问题。布谷鸟哈希的核心思想是将元素映射到数组的两个位置。如果这两个位置中有一个为空，则可以直接存入；如果两个位置都满了，则需要进行“鸠占鹊巢”，随机挤走一个元素，然后自己占据该位置。
为了提高布谷鸟哈希的效率，需要对其进行优化：
增加哈希函数数量
将每个元素映射到三个或四个位置，可以显著降低碰撞概率，提高空间利用率。增加数组的多维度存储
在每个数组位置上挂上多个座位，这样即使两个元素被映射到同一个位置，也不必立即进行挤占。只有当多个座位都被占据时，才需要进行挤占操作。这种方法可以显著降低挤占次数。结合多个优化策略
例如，使用四个哈希函数，每个位置上放置两个座位。这种组合可以在时间和空间效率之间取得平衡，同时提高整体性能。布谷鸟过滤器与布谷鸟哈希结构类似，但它只存储元素的指纹信息（几个bit），这使得它在空间利用上有显著优势。它通过两个特殊的哈希函数实现对偶性，确保每个位置都有一个对应的“兄弟”位置，这样即使一个位置被占据，另一个位置仍然可以用于存储其他元素。
布隆过滤器和布谷鸟过滤器各有优势，但布谷鸟过滤器在反向删除操作和查询性能上更胜一筹。它通过巧妙的哈希设计和数组管理，解决了布隆过滤器的诸多局限性，成为现代高性能过滤器的重要选择。
转载地址：http://ziqfk.baihongyu.com/