由于打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 下午
