Bloom过滤器
本文最后更新于 767 天前,内容如有失效请评论区留言。

由于打CNSS被虐自闭了,Crypto打不过别人,re/pwn/web又写不来,Dev/SA以后再看吧,便只好回来做凌睿题了

关于Bloom过滤器的算法原理不难理解,看懂原理后感觉似曾相识,我记得以前曾经就有过和bloom过滤器一样的idea来判断元素是否存在,但因为会出错所以是个naive的想法

感觉bitarray像C++ STL中的bitset

0x01 配置环境

根据网上的参考资料,java不会,只能选择用Python来实现

首先安装bitarray库

  • 第一次尝试:CMD
    pip install bitarray

    报错失败(;′⌒`)

  • 第二次尝试:Pycharm

    尝试搜索安装bitarray库,安装失败(;′⌒`)

  • 第三次尝试:

    pip install bitarray-2.3.4-cp39-cp39-win_amd64.whl

    从这个地方可以直接下载库:Python Extension Packages for Windows – Christoph Gohlke (uci.edu)

    image-20211006173957729

    莫名又失败了(;′⌒`)

  • 第四次尝试:

    Powershell管理员命令:pip install bitarray-2.3.4-cp39-cp39-win_amd64.whl

    终于成功了(o゚▽゚)o

    image-20211006174059434

再安装mmh3库

pip install mmh3

0x02 语法知识的简单学习

mmh3全程murmurhash3,是一种非加密的哈希算法,简单使用如下

image-20211006173803528

Python class()相关语法补充

参考资料:https://www.runoob.com/python/python-object.html

​ https://www.runoob.com/python3/python3-class.html

不太能理解面向对象,不过到是勉强看出来这个class定义后可以相当于C++的结构体使用,另外还需要类里面函数(好像称作’方法’)必须有一个额外的第一个参数名称self

类的方法与普通的函数只有一个特别的区别——它们必须有一个额外的第一个参数名称, 按照惯例它的名称是 self。

image-20211006174301719

0x03 Python代码实现

# Author: LRL52  Date: 2021.10.6
# BloomFilter(布隆过滤器)
import mmh3
from bitarray import bitarray

class BloomFilter():
    def __init__(self): #初始化位容量大小为m = 1000的BloomFilter
        self.capacity = 1000
        self.bit_array = bitarray(self.capacity)
        self.bit_array.setall(0) #初始室每个位置都置为0

    def insert(self, val):
        for i in range(16, 26): #取Hash函数个数k = 10, Hash的种子为[16, 25]的整数
            index = mmh3.hash(val, i, signed=False) % self.capacity #mmh3.hash()后为32 bit unsigned int, 正常情况hash值大小远大于1000
            self.bit_array[index] = 1

    def is_exist(self, val):
        res = True
        for i in range(16, 26):
            index = mmh3.hash(val, i, signed=False) % self.capacity
            res = res and self.bit_array[index] #每个位置对应的值都为1那么元素才可能存在
        return res

bloom = BloomFilter()
#下面是一个简单的测试
a = ['python', '凌睿', 'CNSS', 'DevOps', 'crypto', '网络安全']
for i in a:
    bloom.insert(i)
b = ['凌睿', 'C++', 'code', 'crypto', 'CNSS', 'RuntimeError', '微光']
for i in b:
    if bloom.is_exist(i):
        print("i like {}".format(i))
    else:
        print("Goodbye, {}".format(i))
#print(bloom.bit_array)

运行截图:

image-20211006175219976

参考资料:

https://zhuanlan.zhihu.com/p/50587308

https://juejin.cn/post/6844904007790673933

https://www.cnblogs.com/liyulong1982/p/6013002.html

0x04 回答题目的问题

  1. 随便说说 bloom 过滤器有没有什么应用?(想到啥说啥)

    一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时间,然而使用bloom过滤器可以快速判断某个Key对应的Value是否存在,因此可以避免很多不必要的磁盘IO操作只是引入bloom过滤器会带来一定的内存消耗

img

  1. bloom 过滤器有没有什么缺点,有什么方法可以解决呢?

    bloom过滤器可能会产生假阳性(False Positive),即查到元素存在,但实际上不存在,这个也很好理解,毕竟该元素产生的hash值可能与多个其它元素产生的hash值有重合,其它元素已经吧这些位置的bitarray设成了1,该元素就会被误判。关于解决办法,可以在计算置哪些位为1的时候同时确定一个特殊的位置,在该位置下面拉出一个链表,链表中存放该元素经过Hash函数后得到的一个64位无符号整数哈希值,这样在检索一个元素是否存在的时候,除了用原来方法检测k个位置是否都为1,如果都为1,还需要用样的算法算出该元素对应的那个特殊位置,检索对应位置的链表,查找是否有该元素的哈希值,如果有,才确定该元素存在。(以上是自己口胡的策略,相当于哈希表与布隆过滤器结合使用吧)

写在最后:

  • 本文由21-信软-LRL52原创撰写
  • 写于2021.10.6 下午
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇