布隆过滤器初步学习

布隆过滤器

概念

布隆过滤器用类似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数组上,最后查询的时候分别查询即可

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/09/18/918/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------