关于布隆过滤器的概念性的介绍，我就不多做解释了，可以详细查看一下文章最后的那篇参考资料。

我实现这个布隆过滤器是从三个公式开始的，如下图所示

只有先处理好这些布隆过滤器的参数以后，才方便创建一个布隆过滤器。三个计算公式对应的实现代码如下：

下面我们开始定义布隆过滤器的类型

ElemNum表示布隆过滤器要加入的元素数量

BloomSize表示布隆过滤器使用的bitmap大小，单位是bit

HashFuncNum表示使用的哈希函数数量

ErrRate表示最大的容错率

bitMap用来指向存储bitmap数据的内存

keys用来存储哈希函数用到的随机数。

这里要详细说明一下，因为根据布隆过滤器的定义，把一个元素加入bitmap的过程中会用到多个哈希函数计算对应的多个哈希值，如果数量足够多，我也不可能编写多种哈希函数去处理（如md5，sha1，sha256等），所以我就采用取巧的方法，使用类似哈希加盐的方式来实现多种哈希函数。通过不同的盐，对同一个输入数据，同一个哈希函数，产生多个不同的哈希值。哈希函数实现如下：

接着增加布隆过滤器的三个方法：

分别表示初始化布隆过滤器，把元素加入布隆过滤器中，以及判断一个元素是否在布隆过滤器中。

最后增加布隆过滤器的New函数

一个简单的布隆过滤器就做好了，下面写几个测试用例测试一下：

完整代码可从github获得：https://github.com/lilianwen/bloomfilter

更多测试用例，后续可能会新增，如从大文件读取巨量测试数据进行测试。

参考资料：

https://mp.weixin.qq.com/s?__biz=Mzg3OTA1MTYzOQ==&mid=2247483700&idx=1&sn=44a9dac2c415b222fb9db5a09e4329a9&chksm=cf0b172cf87c9e3a9213325f5879f794754d601ce4bd7dff71b97da14379b0abafb42978bc9b&scene=27#wechat_redirect