布隆过滤器原理和仿写

发布于:2023-01-15 ⋅ 阅读:(275) ⋅ 点赞:(0)

1、作用

布隆过滤器是一个防止黑客恶意攻击的宝器,布隆过滤器可以与redis结合使用,能够有效地防止redis缓存穿透。

先将全数据,存放到过滤器中。当黑客访问时,会携带访问数据,去访问过滤器,如果过滤器校验可以通过,就会放行,没有通过就会把请求阻断在这个位置。这样就可以避免大量不存在的数据去请求redis,从而造成数据库的大量IO请求。

2、原理

1.无论是什么类型数据,每个数据最小也要8bit,那么都存储到过滤器中,那么就会占用太大的内存空间,所以,我们想一个办法,用一个bit数组来标识都有哪些数据。

2、向bit数组中存数据标识的时候,选择hash方法,将bit数组中索引为计算的hash值,改为1。

3、当有数据请求时,如果在bit数组中,请求数据的hash值位置是1,就能够放行,说明存在。

------------------------------------------

4、因为查找索引使用的是hash方法,所以就有一个结论:

  • 如果布隆过滤器告诉你存在那么这个数据不-定存在
  • 但是布隆过滤器告诉你不存在,那么这个数据一定是不存在的

5、减小误差的方法

  • 使用多个hash函数,比较的时候,这几个hash位置都为1
  • 增大bit数组,尽量避免hash索引冲突

6、请求数据,经过hash函数组运算出hash值,逐个遍历索引位置的布隆数组值是否为1,如果是的话,就说明可能存在这个值,然后放行。但是如果有一个索引位置的值不是1,那就说明总的数组中并不包含这个数据,直接拒绝访问。

3、java实现

GitHub - GingerFih/BoolmFilterContribute to GingerFih/BoolmFilter development by creating an account on GitHub.https://github.com/GingerFih/BoolmFilter


网站公告

今日签到

点亮在社区的每一天
去签到