布隆过滤器
概念
布隆过滤器用类似HashMap的实现方式, 可以在大数据量下进行高效的插入和查询操作(时间复杂度近似O(1)). 但是只能判断某个数据不存在而不能断定其存在.
至于为什么会这样, 其实是因为布隆过滤器的实现方法所限制的.
优点
在Java 的 HashMap 中,存储数据是用的数组-链表的形式,每一个 Key 都对应着一个 Value.
而布隆过滤器用 bit 代替了其中的数组和链表, 并使用多次映射来降低误判率,相当于用多个 Key 对应一个 Value.
之所以这么实现, 是因为 HashMap 这样的数据结构在面对大量数据的时候会花费海量内存.
而布隆过滤器可以用很小的代价(较低的误判率)来达到目的(减少内存开销)
缺点
不支持删除
因为是多Hash值对应的同一个Value,所以可能会存在某些数据的部分Hash值重叠的情况.
这时候如果删除的话,会使其他数据被波及
误算率
随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用Hash表足矣。
应用场景
布隆过滤器通常用在过滤Web请求方面.
比如说一个个人搭建的网站,其URL用的是 https://bestsort.cn/id 的形式,在遭到爬虫爬取的时候,很多人看到id会想到直接爬取 id 为$1-n$的所有内容.
但是问题是很多 id 可能都是无效的.这时候如果按照$1-n$爬取就会造成大量浪费服务器资源. 这种场景下,就可以使用布隆过滤器,对于非法请求直接返回错误页面,
不再进行数据库查询等一系列操作.
大Value拆分
因为通常来说使用布隆过滤器都是在数据量极大的情况下,所以即使是 bit, 也会使用较大的空间来减少误算率(空间越大,碰撞可能性就越少).而对于redis来说可能就成了一个不得不拆分的大Value.
通常来说，一般会把一个 bit 数组拆分成多个数组，同时使得计算出来的多个Key尽可能均匀的分布在各个bit数组上，最后查询的时候分别查询即可
