由于打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)
莫名又失败了(;′⌒`)
-
第四次尝试:
Powershell管理员命令:
pip install bitarray-2.3.4-cp39-cp39-win_amd64.whl
终于成功了(o゚▽゚)o
再安装mmh3库
pip install mmh3
0x02 语法知识的简单学习
mmh3全程murmurhash3,是一种非加密的哈希算法,简单使用如下
Python class()相关语法补充
参考资料:https://www.runoob.com/python/python-object.html
https://www.runoob.com/python3/python3-class.html
不太能理解面向对象,不过到是勉强看出来这个class定义后可以相当于C++的结构体使用,另外还需要类里面函数(好像称作'方法')必须有一个额外的第一个参数名称self
类的方法与普通的函数只有一个特别的区别——它们必须有一个额外的第一个参数名称, 按照惯例它的名称是 self。
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)
运行截图:
参考资料:
https://zhuanlan.zhihu.com/p/50587308
https://juejin.cn/post/6844904007790673933
https://www.cnblogs.com/liyulong1982/p/6013002.html
0x04 回答题目的问题
- 随便说说 bloom 过滤器有没有什么应用?(想到啥说啥)
一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时间,然而使用bloom过滤器可以快速判断某个Key对应的Value是否存在,因此可以避免很多不必要的磁盘IO操作,
只是引入bloom过滤器会带来一定的内存消耗
- bloom 过滤器有没有什么缺点,有什么方法可以解决呢?
bloom过滤器可能会产生假阳性(False Positive),即查到元素存在,但实际上不存在,这个也很好理解,毕竟该元素产生的hash值可能与多个其它元素产生的hash值有重合,其它元素已经吧这些位置的bitarray设成了1,该元素就会被误判。关于解决办法,可以在计算置哪些位为1的时候同时确定一个特殊的位置,在该位置下面拉出一个链表,链表中存放该元素经过Hash函数后得到的一个64位无符号整数哈希值,这样在检索一个元素是否存在的时候,除了用原来方法检测k个位置是否都为1,如果都为1,还需要用样的算法算出该元素对应的那个特殊位置,检索对应位置的链表,查找是否有该元素的哈希值,如果有,才确定该元素存在。(以上是自己口胡的策略,相当于哈希表与布隆过滤器结合使用吧)
写在最后:
- 本文由21-信软-LRL52原创撰写
- 写于2021.10.6 下午
Comments | NOTHING