由于打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 回答题目的问题

1. 随便说说 bloom 过滤器有没有什么应用？（想到啥说啥）

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

2. bloom 过滤器有没有什么缺点，有什么方法可以解决呢？

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

写在最后：

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