基础

高效，基于概率的数据结构

快速判断一个元素是否在集合中

原理是创建一个位数组，将元素通过哈希函数计算其在位数组中所占用的位都是哪些然后进行标记。当下次判断这个元素时，如果哈希后的每一位在位数组中都已存在标记，那么就可以说明这个元素已经存在

优点：高效

采用位数组，空间占用极低

时间复杂度低，基本能快速定位到

缺点：会误判

如果返回元素不在，那么元素一定不在，但是如果返回元素已经存在，那么是有一定概率误判的。因为哈希可能会出现冲突

变更麻烦，如果想要移出元素就没办法做到了，只能根据集合重建过滤器

误判的概率取决于位数组的大小和哈希函数的个数

对于误判的处理：

1、可以对判断后的元素进行二次验证，这个要看误判的代价如何

适用场景

1、垃圾邮件过滤

2、缓存穿透防护