[数据结构与算法]海量数据去重hash与布隆过滤器

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

背景

• 在使?word?档时，word如何判断某个单词是
• 否拼写正确？
• ?络爬?程序，怎么让它不去爬相同的url??？允许有误差
• 垃圾邮件（短信）过滤算法如何设计？允许有误差
• 公安办案时，如何判断某嫌疑?是否在?逃名单中？控制误差 假阳率
• 缓存穿透问题如何解决？允许有误差

缓存穿透

• 描述缓存场景，为了减轻落盘数据库（mysql）的访问压?，在server端与mysql之间加??层缓冲数据层（?来存放热点数据）；
• 缓存穿透发?的场景是server端向数据库请求数据时，缓存数据库（redis）和落盘数据库（mysql）都不包含该数据，数据请求压?全部涌向落盘数据库（mysql）。
• 数据请求步骤：如上图 2 的描述；
• 发?原因：?客利?漏洞伪造数据攻击或者内部业务bug重复?量请求不存在的数据；
• 解决?法：如上图 3 的描述；

需求

• 从海量数据中查询某字符串是否存在。

set和map

• c++标准库（STL）中的set和map结构都是采?红?树实现的
• 图结构示例
  
• 对于严格平衡?叉搜索树(AVL)，100w条数据组成的红?树，只需要?较20次就能找到该值；对于10亿条数据只需要?较30次就能找到该数据；也就是查找次数跟树的?度是?致的；
• 对于红?树来说平衡的是?节点?度，所以研究?较次数需要考虑树的?度差，最好情况某条树链路全是?节点，假设此时?度为h1，最差情况某条树链路全是?红节点间隔，那么此时树?度为2*h1;
• 在红?树中每?个节点都存储key和val字段，key是?来做?较的字段；红?树并没有要求key字段唯?，在set和map实现过程中限制了key字段唯?。我们来看nginx的红?树实现：

// 这个是截取 nginx 的红?树的实现，这段代码是 insert 操作中的?部分，执?完这个函数还需要检测插?节点后是否平衡（主要是看他的?节点是否也是红?节点）
// 调? ngx_rbtree_insert_value 时，temp传的参数为 红?树的根节点，node传的参数为待插?的节点
void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t
                             *node,
                             ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t **p;
    for ( ;; )
    {
        p = (node->key < temp->key) ? &temp->left : &temp->right;// 这?很重要
        if (*p == sentinel)
        {
            break;
        }
        temp = *p;
    }
    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}
// 不插?相同节点 如果插?相同 让它变成修改操作 此时 红?树当中就不会有相同的key了定时器 key 时间戳
// 如果我们插?key = 12，如上图红?树，12号节点应该在哪个位置？ 如果我们要实现插?存在的节点变成修改操作，该怎么改上?的函数
void ngx_rbtree_insert_value_ex(ngx_rbtree_node_t *temp, ngx_rbtree_node_t
                                *node,
                                ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t **p;
    for ( ;; )
    {
// {-------------add-------------
        if (node->key == temp->key)
        {
            temp->value = node->value;
            return;
        }
// }-------------add-------------
        p = (node->key < temp->key) ? &temp->left : &temp->right;// 这?很重要
        if (*p == sentinel)
        {
            break;
        }
        temp = *p;
    }
    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}

• 另外set和map的关键区别是set不存储val字段；
• 优点：存储效率?，访问速度?效；
• 缺点：对于数据量?且查询字符串?较?且查询字符串相似时将会是噩梦；

我们知道了第一个流程呢我们是要找到这个位置，然后呢把它设置为红色节点，找到红色节点之后呢我们就需要重新着色，如果我们的节点是一样的，颜色是一样的话都是红色的话，如果我们插入的节点跟它的父节点都是红色的话，那么我们就不需要重新着色，可能如果这个树黑节点的高度不一致，呢我们还需要进行左旋转右旋转对不对？
好，那么在这里呢是插入找到代理你们这一段代码，它主要是找到我们带插入的节点的位置，找到这个位置并着色。大家看到了最后一行呢就是给我们这个节点进行着色。
**这个函数的作用？**我们主要是做了两个工作，第一，找到待插入节点的位置，然后呢我们就将这个节点设置为红色，
好，当然后面当然不是我们这个函数，啊接着还需要就是预父节点判断，对不对？颜色比较如果都是红色，那么我们就需要重新着色，对不对？好，重新着色之后，如果引起数的不平衡，重新着色，如果引起了不平衡，就是黑色节点不平衡，那么还需要通过旋转来达到平衡的作用。
现在我们这个函数是这两点，就是1和2，我们这个功能的作用呢就是1和2。
我们这个函数的作用它就是我们的1和2这个操作。
那么我们来看一下，那么我们是怎样查找这个节点呢我们来看一下这个判断。

大家看一下这个判断这个判断呢就是告诉我们，首先跟我们的这个节点比较，如果
大于它，大家看一下，如果这个诺的呢我们来跟大家说一下我们这个 temp，
这个 temp他传的参数呢是我们红色的根节点，这是红黑树的根节点，是我们的根节点，
而我们的node呢是我们待插入的节点，待插入的节点。
好，大家记住一下大家记住一下对双目运算这里，

也就是说我们待插入的节点，比如说我们来插入一个12，大家来思考一下，我们插入12，怎么来找这个节点？
首先8我们跟8节点进行比较，它大于我们8，所以呢它往右边查找，往右边边查找。
大家看一下这个是小于temp是我们的根节点对不对？根节点。
如果我们小于它的话，现在我们是大于它这个点大于8这个节点，
大于8这个节点大于8这个节点是不是往右边走？那么就是15对不对？15，好，然后呢这个 temp会变成15这个节点，这个 temp会变成15号节点，
这个时候呢我们的12会跟15比较，它是不是小于我们的15, 12小于15，它往左边走，
是不是到12了？
大家注意这个时候我们待插入的节点是12，这个 temp也是指向12，我们现在待插入的节点是12，
而且跟我们比较的节点呢也是12，那么我们现在应该往怎么应该怎么走应该怎么走？
大家来看一下我们应该怎么走？
我们是往左边走还是往右边走？大家看一下这这张代码我们是往左边走还是往右边走？我们这个node等于temp key，这个是等于的，那么我们应该往哪边走？
往左边走还是往右边走？我们这个是等于它的是不是往右边走对不对？对，是往右边走。
我们的node,node就是我们代插入的节点是12，这个12小于12 12会小于12吗？显然是不成立的对不对？成立才往左边走，不成立往右边走，所以呢就是往14这边走对不对？好，那么现在12跟14比较了，那么我们往左边走还是往右边走？现在我们跟14号节点进行比较好，对我们往左边走，好我们到达13这个节点是往左边走还是往右边走？
是不是小于它是不是往左边走？是不是接着往左边走？那么我们现在插入的如果我们要插插入node等于12号节点的话，那么我们是不是插入这个位置？

我们12应该要插入在这里，所以这个告诉我们什么呢这段代码告诉我们什么呢?
我们可以插入相同的key，
那这个的结论呢就是我们可以插入相同的node，就是红黑树当中我们可以插入相同的节点，
我们可以插入相同的节点，那么插入相同的节点的
第一句是什么？就是我们这个运算是怎么做的，好，那么我们现在想要实现，
现在我们想要实现不能插入相同的节点，我们要实现一个不能插入相同的节点应该怎么做？
我们不插入相同的节点应该怎么做？我们是不是可以约定一下，如果插入相同的节点，让它变为赋值操作，这是修改操作。
对不对？那么如果相同的话，那么我们就变成修改的操作，那么我们应该怎么做？
大概改了一个版本，那么我们是不是可以在这个二目运算之前做一个判断？
如果相等的话，如果我们当前的t跟我们现在比较的k相等的话，那么我们是不是直接进行赋值就行了？
我们把这个值修改就行了。

我们加入了这一个代码之后，我们就会只是变成修改操作，那么我们此时
此时大家注意了，此时我们这个红黑树当中就不会有相同的key了。
好，在这里呢也跟大家讲解一下就是我们的红黑树呢它可以用来实现我们的定时器，
定时器大家都知道我们如果用t做时间戳的话，
k存储我们的时间戳的话，我们是不是不能保证这个时间戳是否相同相同，我们可能会插入一个相同的时间戳进来，
也就是说我们的红黑树呢它可以存储相同的key，好在这里呢就跟啊这个颜色是需要改变的，我们刚刚在这里12需要重新着色的，
我们这个10号插入的时候它是一个红色节点，需要重新着色

那么呢我们来看一下我们的set跟map它的关键区别，什么叫关键区别？就是最重要的区别。
刚刚跟大家写了，我们红黑树的节点呢,它既存储我们的key也存储我们的value，是不是？我们的map就不存储这个 Value字段就行了。
就是这个呢就是在我们平常开发过程中呢,大家如果对红黑树很了解的话，我们就会
知道怎么去分析它我们的map，第二个字段的value值是不是不需要存储，因为我们
是跟map的key是我们比较的关键元素，这个 Key value这个key呢是我们用来比较的用来排序的对不对？用来比较的。
好，我们来看一下他们的优点和缺点，
如果呢大家思考一下我们的红黑树它是不是没有浪费空间，没有浪费空间，我们的key和value都是存储在我们的这个节点当中，它并没有额外的浪费空间去存储我们的元素，
这个应该能够理解吧？我们的红黑树呢它并没有浪费我们的格外的空间来存储我们的节点**，而且呢访问速度高效，当然这个访问速度高效呢**
是相对的对不对？如果我们存储一个整数那当然会很快对不对？
那么如果100万条数据比较20次，如果我们是整数作为key的话，那么20次是不是很很快啊几乎可以忽略不计对不对？那么1亿条数据是不是也可以忽略不计，就是我们去查询的时候，
那么它的缺点呢大家想想，如果我们的数据量，因为我们这个呢它会存储的key和value都需要存储，
如果数据量大且我们查询字符串比较长的时候，我们比较的它是比较麻烦的。
如果我们这个字符串像我们的邮件跟短信作为key的话，那么我们比较起来呢会非常耗时，它的效率呢是非常低的，如果我们的查询字符串相似的时候，什么叫相似？
字符串相似的时候，它的比较次数,比较呢就会越耗时，这个大家应该能理解吗？就是字符串相似，那么我们比较起来呢也会耗时间，那么如果字符串比较长，它也会耗时间，数据量大，我们存储的也比较多。
那么我们来思考一下另外一种数据结构，也就是我们的STL当中那个unordered_map

unordered_map

• c++标准库（STL）中的unordered_map<string, bool>是采?hashtable实现的；

• 构成：数组+hash函数；

• 它是将字符串通过hash函数?成?个整数再映射到数组当中；它增删改查的时间复杂度是o(1);

• 图结构示例：

• hash函数的作?：避免插?的时候字符串的?较；hash函数计算出来的值通过对数组?度的取模能随机分布在数组当中；

• hash函数?般返回的是64位整数，将多个?数映射到?个?数组中，必然会产?冲突；

• 如何选取hash函数？

  1.选取计算速度快；
  2.哈希相似字符串能保持强随机分布性（防碰撞）；

• murmurhash1，murmurhash2，murmurhash3，siphash（redis6.0当中使?，rust等?多数语?选?的hash算法来实现hashmap），cityhash都具备强随机分布性；测试地址如下：
  https://github.com/aappleby/smhasher

• 负载因?：数组存储元素的个数/数组?度；负载因?越?，冲突越?；负载因?越?，冲突越?；

• hash冲突解决?案：

  • 链表法
    引?链表来处理哈希冲突；也就是将冲突元素?链表链接起来；这也是常?的处理冲突的?式；但是可能出现?种极端情况，冲突元素?较多，该冲突链表过?，这个时候可以将这个链表转换为红?树；由原来链表时间复杂度 o(n) 转换为红?树时间复杂度 ；那么判断该链表过?的依据是多少？可以采?超过256（经验值）个节点的时候将链表结构转换为红?树结构；
    -开放寻址法
    将所有的元素都存放在哈希表的数组中，不使?额外的数据结构；?般使?线性探查的思路解决；
  1. 当插?新元素的时，使?哈希函数在哈希表中定位元素位置；
  2. 检查数组中该槽位索引是否存在元素。如果该槽位为空，则插?，否则3；
  3. 在 2 检测的槽位索引上加?定步?接着检查2；
     加?定步?分为以下?种：
     1. i+1,i+2,i+3,i+4 … i+n
     2. i- ,i+ ,i- ,1+ …

这两种都会导致同类hash聚集；也就是近似值它的hash值也近似，那么它的数组槽位也靠近，形成hash聚集；第?种同类聚集冲突在前，第?种只是将聚集冲突延后；
另外还可以使?双重哈希来解决上?出现hash聚集现象：

在.net HashTable类的hash函数Hk定义如下：
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %
(hashsize – 1)))] % hashsize
在此 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))) 与 hashsize
互为素数（两数互为素数表示两者没有共同的质因?）；
执?了 hashsize 次探查后，哈希表中的每?个位置都有且只有?次被访问到，也就是说，对于给定的 key，对哈希表中的同?位置不会同时使? Hi 和 Hj；
具体原理：https://www.cnblogs.com/organic/p/6283476.html

• 同样的hashtable中节点存储了key和val，hashtable并没有要求key的??顺序，我们同样可以修改代码让插?存在的数据变成修改操作；
• 优点：访问速度更快；不需要进?字符串?较；
• 缺点：需要引?策略避免冲突，存储效率不?；空间换时间；

也就是我们的c++标准库（STL）中的unordered_map<string, bool>。
好，大家应该使用过对不对？它是不是使用起来，使用起来跟我们的map没什么多大差异，对不对？跟我们的map使用起来呢没有多大的差异对不对？
那么他呢是如何来实现，啊有的朋友没有使用过他们呢 unordered_map跟我们的map使用起来没什么差异，它也是一个key和value。

它使用起来没什么差异，那么我们来看一下他们到底有什么不同，大家平常在工作的过程当中如何来选择map或者来选择unordered_map，我们应该如何来选择呢？
好，在这里呢首先我我们需要明确的是unordered_map呢它是由哈希table来实现的,
unordered_map它的构成呢就是数组加上我们的哈希函数，数组加上哈希函数，也就是跟我们这个图的结构呢很类似，

跟我们这个结构很类似，就是我们准备一个数组 ，然后呢我们每一个数组里面呢它会用链表把同时哈希到相同槽位的把它链接起来，这样的一个结构就是哈希函数，哈希函数是将我们的字符串，避免插?的时候字符串的?较；hash函数计算出来的值通过对数组?度的取模能随机分布在数组当中;
比如说我们今天的任务就是将字符串去一个海量字符串库当中去查询是否存在，那么
我们这个哈希函数呢就是对我们的这个 key这个 key进行哈希，
然后生成一个整数，生成整数之后，这个一般是我们64位的整数，64位的整数呢然后再映射对我们的这个数组长度进行取余。
比如说我们这个长度是12，那么生成的整数呢对我们的12进行取余，取余之后呢我们就会落到我们这个数组当中的某一个位置当中，就是将我们这个数
在位置当中，我们的这个哈希的数据结构，它就是将我们的横串通过哈希函数哈希成一个整数，然后映射到我们这个数组当中，然后我们就将这个 key和value存储在我们的这个数组当中，好，就跟我们当前的这个结构呢比较类似。
好，那么我们就需要明确一个概念了，
我们为什么要使用哈希函数？为什么要使用哈希函数？

当然大家是否还记得我们前面使用map结构的时候，如果字符串很长的话，我们的说查询效率高，好这效率高是其次，那么我们前面map大家还记得吧我们的红黑树它进行节点比较的时候，它需要比较key
对不对？我们需要比较key那么我们按unordered_map呢它就解决一个我们避免了字符串的比较，
大家明白吗？
我们去插入节点的时候，呢我们不需要跟他们进行比较，我们直接通过一个哈希函数映射到某一个位置，
那么我们去查找它的时候，呢同样的是通过这个哈希函数映射到相同的位置，对不对？它会哈希到相同的位置，
那么我们是不是不需要比较，我们哈奇的函数是不是解决了一个比较的问题？
我们的map虽然它的查找效率高，但是比较字符串是非常的慢。

当然如果是有冲突的时候呢是需要比较的，我们落到这个曹位就认为他
就是如果这里有冲突的时候，呢我们会要跟key依次的比较。
那么如果他们都映射到这个位置，映射到这个位置他们的哈希值，
然后再跟我们的数组取余以后呢,它们落在相同的位置，那么呢我们还需要比较这两个字符串的，
我们如果有冲突的情况下，依然要比较我们的字符串，依然要进行字符串的比较，
我们只是插入操作的时候不需要比较.

取模之后呢它能够随机分布到数组当中，
随机的分布在数组当中，也就是说我们哈希函数的目标呢就是想让我们插入节点的时候，呢能够随机分布到我们这个数组当中，这样我们就避免了比如说这里产生冲突了，产生冲突了，我们是不是还需要进行字符串的比较，如果查找的时候还是需要进行字符串的比较，那么我们来看一下它的哈希函数呢它的目标呢是想让我们能够随机的分布在我们的数组当中，
我们的哈希函数呢一般返回的是64位整数，我们将一个64位的整数插入到一个很小的数组当中，
那么很有可能会产生冲突，必然会产生冲突，为什么会产生冲突？
呢在这里呢对优化了比较次数，那么我们来看一下为什么
大家来看一下为什么我们会必然产生冲突？
假设我们通过两次哈希函数，第一个哈希函数呢哈希出来的值是一，
第二个哈希函数出来的值呢是5，那么如果我们把它插入到4当中，
如果我们把它映射到4这个再字等于4的数字当中，是不是我们的一进行举？
一对我们的次序模，然后等于1，对不对？那么5呢
对我们的4取模是不是等于1？也是等于1，那么他们是不是都落在我们的一号槽位当中，这个数组的一号槽位当中？
对，
我们的磁均类型的红黑树呢是比较慢的，那么我们来看一下，

好，那么我们来看一下size等于8的时候，size等于8的时候是不是一个映射到1，一个映射到5，那么这里是不是就避免了一个
就没有冲突了，这个能看明白吗？
就是同样的是1和5，我们的数组的长度呢不同，呢它们可能就一个产生冲突，另一个不产生冲突，这个应该能看明白吧？
好，那么我们应该如何来选择哈希函数呢？
我们根据哈希函数的作用，我们就知道如何来选择了，我们首先是不是要选择计算速度快的？
我们通过一个长的字符串，经过我们的哈希函数能够快速的算出我们64位整数，对不对？
那么第二个呢就是我们字符串这个操作能够保持一个强随机分布性，如果什么叫强随机分布性？就是尽量的减少冲突次数，我们的朋友呢全部落在我们的数字当中，减少避免的避免我们的冲突，对不对？

那么我们一般选取怎样的哈希函数呢像murmurhash1，murmurhash2，murmurhash3，siphash（redis6.0当中使?，rust等?多数语?选?的hash算法来实现hashmap），随机分布性就是比如说我们插入一个MAC一跟MAC二，他们哈希出来的值呢会间隔比较大，它不会像我们的一个有聚集作用，比如说我们的MAC一哈希到三这里，那么Mark二呢
他知道四这里这种呢就是一种聚集的一种聚集的，就是一个不具备强随机分布性的，
那么如果我们的一个在2,一个在11，它们之间间隔距离很远，那么呢它这种呢就具备强随机分布性。
好那么一般呢我们就使用了这些
murmurhash哈希系列跟我们的siphash跟我们的c里哈希呢他们都具备一个强随机分布性。

我们再来聊聊一下负载因子，什么叫负载因子？就是我们这个数组
我们在这里是不是我们的哈希table它是由数组跟哈希函数呢来构成的，那么我们这里插入的元素跟我们这个数组的长度的关系的比值呢就是我们的这个负载因子，也就是说我们数组存储元素的个数跟我们这个数组的长度的比值呢就是负载因子。

就是我们这个数组，占用率的问题，我们存储的元素占我们这个长度总共占了几个位置，对不对？当然这里可能会产生冲突，对不对？
那么负载因子越小的话，冲突就越小，什么叫负载因子越小？
呢就是我们有一个大数组，
对数组越长冲突越小，对我们是不是就冲突就越小，负载因子越大，那么呢我们的冲突呢就会越大。
比如说大于一的情况下，那必然会产生冲突对不对？什么叫大于一？就是我们存储的元素都大于我们这个数组的长度了，那么必然会产生冲突，
对不对？这个就必然大于一的时候必然冲突。
就是冲击原理，比如说7个苹果放到6个箱子里面，是不是至少有1个箱子里面有2个苹果，这个应该很容易理解，
大于一的时候必然会产生冲突，对不对？
好，那么我们再来看一下，大家一定要认真听，啊现在非常关键，因为我们的哈希冲突的解决方案呢就直接引出了我们今天的
因今天的主角，也就是我们的速溶过滤器，我们来看一下我们的哈希冲突它有哪些解决方案。
在这里呢 演示了两种哈希冲突的解决方案，为什么只列出这两种，呢因为这两种呢是使用的最多的两种，其他的都是不那么好用的，而且我见到过的当中呢是没有使用的，
只是在文章中搜到了有那种，但是呢我在其他的解决冲突的方案方案当中呢没有看到他们使用过，
我只看到过这两种的使用方法，就是解决冲突的两种方法，第一种呢就是我们的链条法，啊我们的临时这个结构就是1013号
对这个情况要说的很重要那么，这个呢就是为了避免内存的大量的内存消耗大量的内存，因为
这里会有一个负载因子，负载因子呢就说明我们这个数据呢有很多像我们这张图像这张图里面
是不是有的数组的曹魏它是没有存储东西的，像69 10 11它并没有存储东西，并没有存储内容。
好，那么我们接着来讲练表法，列表法呢是大多数使用
大多数的解决方案，像我们的radius当中，它就是使用的链表法，链表法呢就是将冲突的元素呢
用链表的方式呢把它链接起来，将这个节点把它链接起来，这个呢就是链表法常用的这个是比较常用的处理冲突的方式，
但是呢它可能会出现一种极端的情况，大家可思考一下，比如说在这里呢它这里有三个节点，呢
有三个节点发生冲突了，那么呢我们在这里会链接很长，大家是否还记得我们的map，
他的最差的情况是不是要比较20次，比如说我们有100万的数据要比较20次，那么如果我们的哈希冲突这里有20个的话，那么是不是效率也会很低，
对不对？
那么如果像这种哈希冲突很严重的朋友呢呃很严重的情况下，呢我们就可以
将这个链表转化成红黑树转化成红黑树，这样呢我们又可以
减少比较的次数，又可以减少比较的次数，在我们的Java Java八大中呢就是这么处理的，就是我们的Java语言当中呢他是这么处理的，
就是我们可以呢将这个链表如果这个链表过长，我们就把它转化成红黑树。
那么
因为我们的电表它的时间复杂度是on也就是我们最差的情况下，要将所有的电表都需要比较，
那么如果我们把它转成红黑树，是不是又转化成o log了，那么我们的比较次数呢能够大大的减小，对不对？
那么我们再来看一下，那么在实际应用过程当中，我们这个列表过长判断这个列表过长的
据是什么，我们可以采用超过256或者是512，这个都有看到过就是其他的开源项目当中有使用512的，也有使用256的，那么呢这个呢就是一个经验值。
就是超过这个节点的时候，我们就将这个链表结构转化为红黑树的结构，这样呢我们就减少这个链表的比较的次数，这个是我们的链表法。
好，那么第二种方面表法呢它并没它引入了一个新的结构，也就是说它引入了一个链表的结构呢来存储我们的数据对不对？
引入了链表的方式，那么另外一种呢开放寻址法，它就是直接将数据存储在我们的数据当中，不引入任何其他的数据结构，
不引入任何其他的数据结构，这个就是我们的开放寻执法，一般呢是使用我们的线性探查的这样的一个解决思路，
对超过这个数字呢就无法忍受，

总结

红?树和hashtable都不能解决海量数据问题，它们都需要存储具体字符串，如果数据量?，提供不了?百G的内存；所以需要尝试探寻不存储key的?案，并且拥有hashtable的优点（不需要?较字符串）

我们首先呢是从这个背景引入的，背景引入
得出一个结论就是我们是用一个字符串去海量一个数据数据串是字符串的一个库当中呢查询这个字符串是否存在，
这是我们的一个总体需求，然后呢还跟大家总结了一下就是我们的缓存穿透的问题，他是怎么我们在面试的过程中如何来回答这个问题，以及
我们这个场景是怎样子的，场景是怎样子的，是在什么样的情况下，他不是在写入数据，是在我们请求数据的时候
出现的问题，那么出现的问题是什么？

就是我们的redis跟mysql呢这个数据都不存在那么呢我们可能黑客就可能利用此漏洞，就不妨的往我们的mysql灌数据对不对？往我的mysql数据，这样呢可能会让我们的mysql压力过大，可能会引起我们整个系统就陷入瘫痪，就不能对外提供服务，这样的一个情况呢就叫做缓存穿透问题。

那么我们的解决方案呢也有两种，第一种呢就不跟大家解释了，第二种就是我们需要在serve端这里一个数据结构能够快速的判断这个字符串是否在mysql当中，我们就用一个数据结构呢能够快速的判断这个数据是否在我们的mysql当中，好，这个呢就是我们的缓存穿透问题的解决，然后呢我们就引入了我们的set跟map。

为什么在这里需要跟大家介绍一下这个 set跟map呢？
为什么用set的map来引入这个问题，因为对这种处理方案不是很熟悉的朋友呢很容易联想到的一种解决方案
大家还记得这个还记得这个负载因子，我们的负载因子是不是要
小于一最好啊小于一，也就是我们的数组的长度要大于我们数组存储元素的个数，我们这个越大是不是我们的冲突就越小？

冲突太多，我们的效率就会变低了。
好，我们接着来回顾啊我们为什么要使用这个红黑树，就是我们的set跟map啊跟大家讲的，第一个是帮大家回顾一下我们前面文章当中红黑树红黑树它的
具体的实现以及我们插入的时候应该如何来插入，然后呢在这里也跟大家介绍了跟大家介绍了我们这个红黑树的节点，它可以存储相同keys的值，可以存储相同key的值，只是我们的map跟设置呢它做了运算对不对？
它做了这种判断，
也就是我们通过这种判断呢等于它我们就把它改成修改操作，我们插入的时候呢把它如果插入相同的元素，呢我们就把它改成修改操作，
这个是我们的色这个 map在我们的红黑树上面呢做了修改，我们的红黑树并没有限定我们，并没有限定大家一定要记住它，并没有限定我们是否可以存储相同，

我们这个有什么问题呢 set跟map来实现，我们是不是要将这个 key全部要存储，这是第一个，我们需要全部存储。
第二个呢就是如果字符串比较长的时候，大家
一起来回顾一下，就是如果字母算比较长的时候，我们就算值比较20次30次，那么呢也是一个非常大的操作，那么这个效率呢
最主要的是不是我们这个字符串长的时候我们不好解决。
还有一个就是我们的存这个数据量大，我们需要全部存储啊，是不是这两个问题？

那么我们先来解决这个字符串比较长的问题，
**字符串比较长怎么办？**因为我们的用红黑树来实现的话，我们就必然要进行字符串的比较，那么呢我们能不能解决一个不需要进行字符串比较，呢那么我们就引入了我们的unordered_map的办法，
它就不需要进行字符串的比较，因为我们是通过哈希函数将这个字符串将这个字符串呢把它
哈希到哈希成一个整数，然后呢再映射到我们的数组当中，这样呢我们就可以
可以不需要进行比较，我们下次来查找，这个比如说我们这个查找这个单位，我们查找单位这个节点，那么我们下一次
通过哈希函数是不是还是映射到这三这个位置，我们没有跟任何的字符串这里面的任何字符串进行比较

比如说我们查找daring这个节点，我们是不是还是将daring这个字符串通过哈希函数哈希成整数，然后又重新映射到三这个位置，
那么是不是我们没有跟任何字符串地址比较？
那么呢也这里就引出了我们哈希函数的作用，它的作用呢就是可以避免我们插入的时候呢一个字符串的比较。
同时我们哈希函数呢它还必须有必须要具备一个功能，就是它必须要具备一个强随机分布性。
大家思考一下，如果我们刚刚跟大家举个例子了，就是 Mark一跟Mark二，如果他们不具备强随机分布分布性的话，就是我们这个哈希函数，那么它们可能会相邻，如果相邻的话，我们下次插入的时候它
它的冲突的几率呢就会大大的增加，如果我们它的冲突的几率呢会大大的增加，
在这里呢也跟大家举了几个强随机分布性的几个行几个哈希函数，使用的最多的就是我们这两个，
第一个是murmurhash2，
我们的rads6.0之前，radies6.0之前呢就是使用的我们的murmurhash2，二大家也可以看一下源码，在这里呢也会有注释，我们的radish当中呢它有注释，
我们可以搜一下大家可以看一下我们的murmurhash2，呢在我们之前呢它是使用的我们的murmurhash2，
就是我们之前是采用的murmurhash2，，现在呢我们使用的是siphash，啊在这呢是注释当中呢
给我们的提示，也就是我们在6.0之前，它是采用的我们的murmurhash2，
我的等会的测试代码，也就是我们从线上代码当中抠出来的代码，呢它也是采用的我们的murmurhash2，
我们的siphash呢是我们的redis6.0当中目前使用到的，

想一下哈希冲突的解决方案哈希冲突呢它是必然产生的，为什么呢有两种情况必然产生哈希冲突？第一个第一种原有两种原因，第一种原因呢就是我们这个
将一个很大的数映射到一个小数组当中，它很有可能就是必然会产生冲突。第二种呢就是我们可能是负载因子的原因，就是我们负载因子越大，
比如说我们这个负载因子大于2>3，那么呢它必然会产生冲突的，因为我们的数组的长度都小于了都小于这个数组存储元素的个数了，那么呢它也会必然产生冲突。
那么我们能产生冲已经产生冲突了，我们就要考虑去怎么解决哈希冲突的问题。第一种呢就是我们的列表法也是常用的一种
像我们的redis6.0，它就是使用的我们的链表法，那么redis为什么使用我们的链表法？呢它主要原因是我们的radies6.0，它对内存是有严格的要求的，
**也就是说我们不能够浪费空间来来保证你的查找效率，所以呢我们就必须使用链表法，**并且呢还采用的是一个头叉法。

那么我们来讲一下今天最主要的一个方法就是开放寻址法，我们的列表法呢它是引入了一个数据结构来
来链接这个冲突的节点，那么我们的开放寻址法呢它是将所有的元素呢都放在这个数组当中，不使用额外的数据结构，
它不使用任何额外的数据结构。
好，那么我们的开放形式法呢它又有三种方法又有三种方法，第一种呢
好，我们先来讲解一下开放选址的它的一个步骤。
首先呢我们插入新元素的时候，使用哈希函数的去定位元素的位置，这个大家应该很很容易理解。
第二种呢就是我们索引判断这个索引是否存在元素，如果该槽位为空则插入，如果不为空那就是产生冲突了，产生冲突呢我们就有解决方案，因为我们这个
数组不为空，这个数组的曹魏不为空，那么其他的曹魏可能会为空对不对？那么我们就去尝试，
我们就去尝试其他的曹魏是不是没有元素对不对？那么我们的最开放巡视法最主要的核心思想就是
去其他曹魏没有元素的地方去探查什么叫探查，探查其他数组其他的曹魏没有元素的那些曹魏，
这个是我们的核心思想，那么有哪几种方式来探查？
呢第一种就是我们很容易想到的，
比如说我们当前插入的元素的索引，这种数组的索引是I那么我们可以I加一尝试一下，
就是我们往往右边移动一项，就是我们这个数组，比如说我们1号位置这里有有数据，噢我们5号这里数据有数据，那么我们加1我们在6号位置看一下有没有数据，如果没有数据，那么我们就插入到这个位置这是，这是第一种。

那么第二个问题
这个有什么问题呢是不是跟我们前面讲的聚集哈希是一样的，就是
我们把它放在一起了，那么如果
那么是不是很容易引起很容易引起下一次冲突？
是不是很容易引起下一次冲突，那么就引入了第二种方法，我们把这个步长加大一点我们把这个步长加大一点，
用平方，比如说我们先往左边探查，然后再往右边探查，就是减号就是往左边探查，
加号呢就是往右边探查，这是我们左右互相的探查，我们每一次探查的步伐呢把它扩大，就是给它一个平方，比如说3的平方9，
通过这种方式呢往左右两边探查，这样呢我们也可以解决前面这种聚集哈希的问题。
好，我们来解释一下什么叫同类哈希聚集。就是虽然我们对插入后那映射规则就不好锁定，
啊不是，我们当然我们下次查找还是要通过这种，我们是采用这种规则去探查的，那么我们下一次去查找这个位置的时候，呢也需要通过这种方法依次去探查，一直找到这个 T为止，
所以呢这个是比较麻烦的对不对？
我们是采采用这种策略去探查的，那么我们下次来查找这个元素的时候，依然要按照这个规则去查找那个元素，
这个应该能明白了，这个呢就是我们
为了避免同类哈希聚集，那么我们就把这个步长加大一点，加大一点，往左右两边的探查，左右两边依次去尝试探查。
当然如果我们插入节点之后，下一次同样的也要按照这种规则去探查，
打倒那个元素明白了吗？我们依然要按照这个规则去探查那个元素。好，
这个呢就是解释同类哈希聚集，也就是它的近似值，呢比如说我们的哈希它的就是我们这个字符串它的值相似的时候，它的哈希值呢理论上它也会比较近似，当然我们如果采用前面的这种墙随机
像随机分布式的哈奇函数呢这种情况比较少，但是不能说它不存在明白了吗？
就是它这种情况会比较少，它不是百%的，
这个墙是相对性的，也会比较靠近，也会比较靠近这个墙随机分布性，呢它是相对而言的，
那么这种他的哈希值也近似，所以呢他的数组的槽位呢也会比较靠近，
也会比较靠近，那么呢就会形成一个哈希聚集，也就是说我们通过这种
步长很短的会一直会发生碰撞，会一直发生碰撞，那么在这里可能会延伸到a加n
都没有找到曹魏，明白了吗？

那么我们来看一下，
我们第一种呢哈希冲突呢会马上出现，我们第二种大家思考一下，虽然是这种往左右两边进行扩张，他只是将我们的聚集冲突之后
两种方法停止，呃这个只要你规则上只要你规则定了，那么你下次查找再按照你这种规则依次去探查，那么也是可以的。
我们第二种只是将聚集冲突延后了，
我们虽然把步长增大了，但是呢它还会产生聚集冲突，它只是把这个聚集冲突对没有根治，那么怎么根治呢？

那么怎么根治这类问题？那么就出现了双重哈希，引入布隆过滤器的最重要的一个依据，最重要的一个依据就是我们的双重哈希解决上面的哈希聚集问题。
好，在这里呢是找到了一个对迟早会碰撞，那么我们怎么用双重哈希来解决上面的哈希聚集问题？呢在我们点那时当中，
也就是我们的c #语言当中，哈希table类呢它的哈哈希函数呢是这样定义的，大家看一下，这是它的哈希函数的定义。

在.net HashTable类的hash函数Hk定义如下：
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %
(hashsize – 1)))] % hashsize
在此 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))) 与 hashsize
互为素数（两数互为素数表示两者没有共同的质因?）；
执?了 hashsize 次探查后，哈希表中的每?个位置都有且只有?次被访问到，也就是
说，对于给定的 key，对哈希表中的同?位置不会同时使? Hi 和 Hj；

好，我们把它稍微移到这边来，
这种定义呢然后在这里呢做了一个运算，当然我们使用的是一个哈希函数，大家一定要明确一点，我们使用的是同样的哈希函数，
同样的哈奇函数通过这种运算，呢通过这种运算避免通过这种运算之后，大家看一下，这里面呢它会有一个
我们这一块跟我们的哈希赛子减一呢它互为素数，什么叫互为素数？也就是他们之间没有公费就是没有公约数，

那个呢比如说我们相邻的这个元素，比如说我们这个相邻的元素，相邻的元素跟它互值的话，那么同时也跟这个值进行互值。
他的户籍有传递性对不对？户籍具有传递性，那么是不是
通过如果他相邻的，他是不是也会找一个速速去探查，也会找一个速速的位置跟他相隔速速的位置呢进行探查。
好，这个有点抽象，大家一定要理解一下，就是我们素数呢它具有传递性，啊就是质数，互为质数，嘛它们具有传递性，
就是如果我们这个相邻的元素他们估值的话，
就是我们第一个元素他会找一个复制的地方，然后第二个元素呢也会找一个复制的地方，那么他们之间不会进行碰撞。
好，放在左边，好，
那么我们把这个移移移过来一点点，好，这个能听明白吧？
举个例子，
这个例子不好举，因为我们这个很难取个值出来，这个只能理解，就是我们通过这种质数粒子直观的多是吧？
那么我们应该怎么举例，呢这个因为是数学我也不好举例，
因为这个是数学我不好举例，这个只是
一种共识吧之一种共识，大家记住的前提就是我们可以能够给他移动次数的位置，这个是不是移动相当于给他移动一个位置，啊
就是我们相当于给他移动一个速速的位置，让他们之间减少减少碰撞，他是这么实现的。
通过这种方式呢我们能够减少碰撞，就是我就是有这个原理里面他看到了这里有原理，

就是最多的情况下会出现三次碰撞。
就是三就是我们这里会有三次就像我们刚刚画的这个图一样，
明白了吗？双重体现在哪里？双重主要体现在我们
我们这个哈希函数哈希函数这里是不是有一个补偿这个补偿的哈希函数呢又跟前面的哈希值呢？
这里就相当于两个哈希值，明白吗？这里就相当于一个哈希一，好，我们把这个东西把它简化一下，就相当于我们的哈希一加上我们的哈希二配备的
哈希二，明白吧？我们是通过不懂是吧？因为我们的后面呢对哈希的值，因为我们的哈希二呢是根据哈希一算出来的，
我们的哈希二呢是根据哈希一算出来的，我们实现不溶过滤器的时候呢也是采用这种思想，也是采用这种思想来实现的，
那么我们就相当于一个哈希一加上一个哈希二，采用这样的补偿呢进行
进行试探，就是我们的线性试探我们的试探方法呢就是这样的试探方法。
好，大家先记住这个，可以吧这个大家可以理解吧？
这个是哈希哈希一函数，我们这里哈希一函数这一波运算，呢我们把它看成看成哈希二，明白了吗？
好，这里呢不跟大家详细的解释解释了，这个这个是一个数学推论过来的。

我们主要的目的，是来看来看一下我们这个技术
他是如何来实现的，我们应该怎么来使用它，我们知道它的原理就明白了。
好对使用当然你也能够说出它的原理，
这个原因这个数学推论的原理就不用不用大家去学习了，这个有必要吗？我觉得没有必要。
我们不需要去创作这些哈希函数，有数学家帮我们去实现这些哈希函数，以及有数学家帮我们去研究这个理论，为什么这样能够减少碰撞？
明白了吧这个明白了，对，那得开个数学班了。好，那么我们在这里就过了具体原理，呢大家可以看一下。

好，同样的我们的哈希paper像我们的这个哈希冲突的解决方案，就是我们这个方案，呢就是我们这个哈希 table呢它的节点呢也同时存储了我们的key和value，
就是两个相似的字符上可能产生相似的哈希值，双重是不是再将两个相似的哈希值再做一次二？
次对可以这么理解可以这么理解。
就是我们当然呢这两次花期呢我们不是两个字符串之间，呢我们不考虑，我们每次考虑只考虑一个字符串，
但是呢我们并没有要求key的大小顺序，跟我们前面红黑树一样的，跟我们的前面红黑树一样的，我们同样的可以修改代码，
让插入存在的数据呢进行修改操作，这个大家应该容易理解我们在这里呢并没有要求我们t的大小顺序，
如果我们要修改那个字段的话，我们是不是也要
找到那个 Key，然后修改值，而不是变成插入操作，我们的hash table跟我们的红黑树是一模一样的，就是它
没有要求我们的是否一样，明白了吧？

好，那么我们接着来讲它的优点和缺点，它的优点呢
不需要进行字符串的比较，这个大家可以理解。
第二个呢就是访问速度更快，它的时间复杂度呢是o一，对不对？它的时间复杂度是o一，
o一就是一次就能够找到对不对？好，那么它的缺点呢它需要引入策略来避免冲突，因为冲突了的话，
像这里冲突了三次，那么如果这里是长字符串的话，我们依然要比较三次字符串，字符串的比较依然有三次对不对？
所以呢我们需要引入一个策略来避免冲突，减少冲突，对不对？它整体来说呢这是一个空间换时间的操作。
好，那么我们来看一下，
我们刚刚说了，我们需要大量的内存来存储这个 t和管理，像不管我们使用的是色子或者是map，还是使用的我们的unordered_map，
是不是都需要存储这个值？
就是我们前面讲的三个结构都需要存储这个值，大家思考一下，如果我们
海量垃圾邮件垃圾邮件，
大家思考一下，如果有11条垃圾邮件，11条垃圾邮件，这个邮件要内容又比较长的话，那么是不是要可能要占用GT的
内存，或者是几十g几百g的内存来存储来存储我们的t和value的TT值，这两个结构是不是都要存储我们的这个 string就是t值？
那么这样是不是并没有我们这几个结构是都不能解决我们前面的问题，我们的map或者以及我们unordered_map
都不能解决上面的问题，为什么不能解决？因为我们需要存储这个string，如果海量数据的情况下，我们没有这么大的内存，
那么如果我们不可能引入一个超级计算机吧对不对？
我们不可能用一个超级计算机来来解决一个这样的问题，嘛对不对？这个听明白的朋友慢慢说说完毕好吗？

布隆过滤器

我们这三个点，那么我们现在
不能过滤进来，也是在面试的过程当中经常会问到的，就是
面试官可能会问我们的过滤器是怎样的一个实现方案，他为什么可以解决这个问题？
那么今天呢我们来一步一步来分析，我们布隆过滤器它是怎样的一个结构？

布隆过滤器呢它既然我们在这里需要存储string，那么显然我们的布隆过滤器呢它是不需要存储的这个string的，那么我们看一下我们的布隆过滤器
解决不需要存储我们这个string也能够确定它存在还是不存在这个问题的。

好，我们来看一下布隆过滤器的定义，布隆过滤器的定义呢它是一种概率型的，大家一定要清楚。
在这里面呢有一个概率性的数据结构，在我们以还会跟大家讲解跳表，
跳表呢它也是一个概率性的数据结构，
大家已经看到了概率性呢它的这种数据结构呢它的威力非常强大，那么我们后面讲跳表的时候呢也会跟大家来讲解另外一种概率性的数据结构，
它的特点呢就是高效的插入和查询，能够明确的告知某个字符串一定不存在，
大家看到一定要注意，一定不存在，可能存在，一定要注意这两个词一定跟可能也就是说我们不能够确定它
一定存在，我们不能确定它一定能存在，只能说它可能存在，但是我们能明确的知道它一定不存在，
这样是不是可以解决我们上面的问题。

大家看一下我们上面的几个背景程序，除了这个公安办案除了这个公安办案以及我们的这个 Word查询，
这里面这三个是不是允许有误差？
这三种都是允许有误差的，
对不对？我们是允许有误差的，如果我们的第三第二种第一种跟第四种能够控制，**如果能够控制假阳率的话，也能够满足需求的话，那么我们不能过滤器呢解决这5个问题都是可以的。**好，那么等一下呢

误差不是零容忍，我们来看一下布隆过滤器，
布隆过滤器呢它相对于传统的查询结构，像我们刚刚说的这些结构呢它更加高效，不理解的好，更加高效，占用空间呢更小，
我们刚刚是不是上面的这里面第一个，
他们的问题就是要存储，就是我们占用空间大，然后呢高效呢谈不上对不对？
我们的map跟设置它需要对我们的字符串进行比较，
maps需要跟上进行比较，这个高校谈不上，那么我们的unordered_map呢它的高校就跟我们的冲突率相关了，unordered_map高校跟我们的冲突率相关，
如果冲突率比较大的话，也就是说我们这个链表很长的话，我们也会要进行很多次的比较，也会需要进行很多次的比较，才能够找到我们那个数据，所以呢这两个都是不能使用的。
好，这个我相信大家应该能够理解他们都谈不上高效，因为他们都有各自的缺陷，有一个共同的缺陷，就是他们要占用大量的内存，
那么我们的unordered_map呢比他们两个要稍微好一点，不需要进行字符串比较，如果冲突率很高的情况下，
那么也是不行的，那么如果我们引入双重滑行呢能够缓解这种问题，但是不能不能
解决这个问题。好，那么我们来布隆过滤器，呢它就是在我们的这三个基础上的吸收他们的优点，吸收我们的优点来进行
实现的。

好，在这里呢必须要跟大家明确一下他的缺点，这个缺点呢也是面试的过程中经常会问到的，他的缺点就是
这个误差它是存在误差的，就是可能存在不能确定它一定存在。
好，我们来看一下它是如何来组成的，我们刚刚的我们刚刚的哈希table呢它是数组加哈希函数，

而我们的布隆过滤器呢它是位图加上n个哈希函数构成的，那么我们来看一下位图，什么叫位图？呢位图它的单位是我们的
对，这是疑问，
呃一个比特位一个比特位。
对可以解决存储，我我们的不能过滤器呢主要对不支持删除操作。
对，他不支支持删除操作是他的最大的缺点，面试的过程中经常会问到就是他不支持删除操作，那么我们能不能
给他以就是改善他，让他支持删除操作的？等一下我们在后面的后面的源码讲析的过程中呢会跟大家讲解。
好，那么我们来看一下，
它是位图加上n个哈希函数，n个哈希函数，那么我们来首先来看一下位图是怎样构成的，我们如何来做位图来实现位图？
在c加加当中呢我们可以使用这种bite。
比如说我们在这里面跟大家举个例子，我们是不是可以使用on sine
差来来代替我们的这个盖子，对不对？这个盖子里面是不是有8个是不是有8个比特？
有8个比特对不对？有8个比特，那么我们用袋子8分8是不是能够构建一个64位64比特的位图？

就是我们如何实现位置这个位置？
好，我相信呢这个应该很容易理解很容易理解吧？好，那么我们要插入具体的位置，呢假设我们现在的哈希函数
这里有一个string通过哈希函数生成了173，那么我们怎么将173哈希到我们这个位图当中呢?我们怎么将173哈希到我们这个位图当中？呢
我们是不是首先要对我们整个长度整个位图的长度88 64对不对？那么我们需要对64取余，取余之后我们得出来的结果。
好，我们对64取余就相当于对63进行取&操作，取&操作这就变成一个位运算的对不对？位运算显然要快一些对不对？
那么位运算快一些，那么我们呢在这里呢是45，
那么45我们怎么样找到这个数组的位置，呢找到数组的位置，呢这个 I和j是在哪里？呢我们的横坐标跟竖坐标，
我们 I是不是我们的竖坐标？我们的j是不是我们的横坐标？那么我们的竖坐标和横坐标怎么来查找这个点？呢我们是不是可以对八取余呢就找到了我们的横坐标横坐标，它的位置是5，那么它的纵坐标
I是也是5，那么我们就找到55，那么我们将这个位置呢置为一，这个呢就是我们的一个哈希函数加上位图是如何来哈希的？

就是第这个图告诉我们位图是如何来做。第二个呢就是我们怎么去
去置位，将我们的位图这个值置位，比如说我们将这个 Value映射到我们这个位图当中，那么我们就可以在5和5这个位置呢把它置为一
就可以了。
好，我们来看一下它的原理，就是当一个元素加入位图时，k个哈希函数呢会将这个元素映射到我们位图中的k个点，
位位于我们位图当中的k个点，并把它们制为一，并把它们制为一，也就是当我们检索的时候，呢再通过k个哈希函数检索的时候，就是我们查询的时候，
这个是我们插入的时候这个是插入的时候，这个是我们查询的时候，我们查询的时候呢也是通过这k个函数检测，这k个点是某个纬度，
如果有不唯一的点那么一定不存在，
比如说我们的是正一，它在这个位置这个位置跟这个位置是一，假设我们插入一个试卷，二它第一个位置在我们的
啊我们已经存在的这个位点里面，那么我们再看第二个哈希函数，第二个哈希函数它不在我们原来的这三个点当中，那么我们认为sting二肯定不等于string1
就是我们用QQ函数呢都通过三个哈希函数来进行到我们这个位置当中的不同的点，不同的点，那么我们去查询的时候呢我们就去
一也是通过这三个哈希函数哈希出三个点，看这三个位图当中的位置是不是都唯一，如果都唯一，那么说明它可能存在，如果有一个不唯一有一个不唯一，那么就说明它
肯定不存在，一定不存在。
这个呢就是我们的原理图，就是它的原理图，那么
我们位图中每个槽位它只有两种状态，不是0就是1，
对不对？我们像上图一样，我们的string一跟string二在这个位置，在这个位置它有被两个
映射到，它被两个映射到对不对？这里被两个地方两个呃4G1跟4G2都映射到这个位置了，
那么我们就不知道他被映射了几次，不知道这个一被设置了几次对不对？也不知道被多少个string给哈希映射了，以及是被哪个哈希函数映射过来的，我们不确定是哈希一映射过来的，还是哈希二映射过来的，对不对？
所以呢，我们不能够支持删除操作。
为什么我们不能过滤器，他不支持删除操作，因为
我们这里每个槽位只有两个状态，我们不知道他被设置了几次，同时我们也不知道被哪个
哈希函数映射过来的，所以呢我们删除的时候可能会引起很多不同，对不对？
好，我们知道这个不支持删除操作之后，我们来看一下我们在实际应用过程当中，呢我们的布隆过滤器应该如何来使用？
我们在这里是三个哈希函数，那么我们到底要选择多少个哈希函数？对，不确定性比较大，
那么我们应该选择多少个哈希函数？呢我们到底刚刚我们前面的有朋友已经问了，我们到底分配多少空间的位图呢？
我们能够这个位置当中能够存储多少个元素，呢因为大家都知道我们这里有一个
有一个我们有一个负载因子，所以呢我们尽量的为了减少冲突，呢应该是我们的数组长度要大于我们的存储元素的个数，那么在这里也是一样，**我们是不是这个位图的大小要大于我们
要带插入的字符串的个数要多一些，**我们这个数组要大于我们这个是这里是正一跟是正二是两个，我们的数组长度很大，对不对？
我们这个数组长度呢要大于两个字，
那么我们如何我们能不能够控制假阳率呢？
我们能不能控制假阳率？什么叫假阳率？就是不能过滤器能够明确一定一定不存在，不能够明确一定存在，那么存在判断是有误差的。
**也就是说我们错误判断存在的概率就叫假阳率，**我们
错误的判断这个东西存在的概率叫做假的率，就是比如说我们的是正一跟是正二，
好，在这里举个例子，为什么是选三字哈行？对误判率。对我是这里
来推导告诉我们要选举要选取多少个元素，
然后我们要选取多少个位图，就是这个空间位图手段空间以及我们这个函数，那么呢我们是有工序
公式，它会告诉我们应该选择这个这几个数值是多少。
好，这个假良心率能够听明白了不怕，这个如果不明白的话，那么好，那么我们在这里呢跟大家解释一下，
在我们的实际应用过程当中，呢我们一般是明确这两个，
就是我们要往布能过滤器中存多少元素，这个是我们提前可以写好的，我们自己填的，我们人为填的。
那么第二个要填的是我们能够接受的假阳率，
就是误判率就是我们能够接受的，比如说0.000，像我们这0.1有几个04个01个一对不对？是不是一夜
1/1亿对不对？那么就是1亿个里面只有一个出错，这个明白了吗？我们1亿次判断当中只有一个判断出错，
就是我们这个 P的数值填什么值，我们就是填这个值。
好，那么我们一般呢是根据这两个值去算m和km呢就是根据我们当前
不能问这种存在的元素跟我们的假药率，我们来算出我们的位数应该要要有多少，我们的哈希函数的个数要有多少？
好，那么呢这个是我们的实际应用场景，我们只会列出一个公式，大家呢直接带出来就行了，这个推导的过程我们就交给数学家他们来推导，我们直接用结论就行了，
我们直接用结论就行了，我们知道怎么用就行了，怎么用我们就知我们要填两个值，第一个是我们不能过这些元素的个数，以及我们能够接受的假阳率就是误判率。
好，那么我们就来选定这4个值，然后来看一下这个函，我们的这里呢也会有1个
网有一个网站，他呢把我们的噢在这里已经写好了，我们放在这边，这里有个网站大家看到n大家还记得它的概念，吧就是我们
提前要填的，我们往不能过滤器中需要插入多少条数据，假设我们插入4000条数据，那么呢我们在这里呢
是千千万/1，那么我们的假阳率呢能接受的是千万/1，也就是我们1,000万次判断的当中有一次出错，那么我们填这个值。
那么第三个参数跟第四个参数呢就由他们来计算，由他们来计算，我们提交一下让他们来计算。
那么它算出来的值呢就是这个是我们要用的空间的数量，以及算出来我们的k的值是多少。
我们可以根据这两个的计算的算出来我们这个 m和k的值，
就是我们到底要使用多少，这个位置的倒角是多少，以及我们这个哈希函数的个数是多少，那么呢我们就可以通过这个网站可以提前的预演。
同时呢我们也可以看出他们的规律，就是我们
让两个值不不变，比如说我们要看p和 n的关系p和n的关系，我们把mk
的值不变，也就是我们的存储空间位图的大小不变，以及我们party函数的不变

好，我们来看一下他们的关系，这个是他们的关系，我们这个的关系呢
我们让这两个值不变，这两个值不变。我们来看一下n和p的关系，p就是我们的假阳率的关系，那么n呢就是我们的
布隆过滤器当中的个数的关系。我们来看一下，随着我们数量的增加，也就是我们往不溶过滤器增加的数量增加，
那个权益一定要增加，它的假人率越来越大。我们n和b的关系呢就是随意的按计算账，我们的p呢它越来越大。
那么同样的我们来看一下第二个，我们固定住n和k我们固定住n和k我们固定住n和k
我们来看一下p跟m的关系，随着我们的内层的震荡，随着我们位图内层的震荡，我们的假阳率越来越低，
明白了吗？负相关对的，这个也很容易就是我们的这个数位图的大小很大的话，那么假阳率肯定会小，对不对？假阳率肯定会小。
那么我们接着来看第三个的关系，那么我们第三个p
p和k那么呢我们就是将我们的m跟n把它
固定住，我们先把它固定这两个鞍钢，我们的
m就是我们的存储空间跟我们的数量，不变，我们来看一下p和k的关系，那么这个关系呢
大家可以看到了，我们这个23呢它是一个最低点，它是这样一种好，先
先往下然后再往上的这样的一种趋势，也就是说到达23的时候呢它是一个最佳位置点，
在这个23的时候呢是一个最佳的位置点，就是这个位置。
啊这个麦克老师这个方式图没画好，
那么呢是在这个位置呢它是最最最优点，在这里呢它会有一个最优点。
选择对
就是23以上它又会增加了，我们的假压率又会增加了，就是我们的函数个数增大了，大家也可以想象得到我们的k
哈希函数哈希函数越多的话，哈希函数越多的话，那么我们要在位图当中设置的点也会越多，大家明白吗？就是我们的哈希函数越多，那么我们在这个绘图当中的点也会点的越多，
点的越多是不是？内存占用越多啊，课程占用越多，就是那个设置为一的点越多，不是内存占用内存越多，是设置
唯一的也非得多，那么相应的它的假阳率也会增加，这个都可以理解对不对？
好，这个讲完了之后呢我们已经理解了这4个概念之后，我们再来
跟大家再来强调一下，我们实际工作过程当中，我们使用不能过滤器的时候，我们是先填这两个参数，
n和p指定n和p去算出来m和k好，那么我们来看一下，我们的我们再来讲一个，我们再来看源码，
就是我们如何来选择k个哈希函数？
呢这k个哈希函数就跟我们的开放选址当中的双重，大家双重哈希是一样的，
双重哈希是一样的，双重哈希大家看一下，这个呢就是我们选取k个函数怎么来选取，我们采用的是mama哈 c二me m哈希二，我们将
这个 p存入到我们的曼曼曼哈希二，然后呢指定一个种子偏移量种子偏移量，然后呢我们将这个哈希一的值呢带入到我们的这个
哈希这是，我们同样的是采用的哈希函数，然后呢把它放到这个二里面，
这样呢我们通过哈希一跟哈希二模拟出这里k个k是我们哈希函数的个数，k是哈希函数的个数，
而我们的m呢就是我们的位图的大小，对不对？
M就是位图的大小。
好，
这个呢我们通过哈希一乘以I乘以我们的哈希二，再对我们的绘图进行取余，呢
就算出我们要在哪些位图哪些点进行搞死呃进行设置为一，设置一，
通过这种K歌哈希函数呢这样就是模拟k个哈希函数是不是跟我们的双重
双重哈希是一模一样的，我们的双重哈希是不是刚刚马克老师跟大家操作了，他是不是其实就是
我们前面的可以把它看作哈希一，然后加上一个k贝的k贝的后面的我们不管了，后面的我们不管了，把它
把这里一坨看成我们的哈希二函数就行了，我们通过这种双重哈希去探测没有着色的点，那么我们同样的
使用双重哈希呢能够解决一个，就是比如说我们这里三个函数，我们不可能让这三个函数都都着在一个点，吧
如果我们这三个函数找到一个点，那么就没有意义了。
比如说我们这三个哈希函数都找到这个点行不行？那显然不行，对不对？我们是不是
利用前面的发生函数的那个探测是双头发起探测，让他至少不跟自己
跟钱跟之前的冲突，明白了吗？好，这个听明白了没有？发Mark刷个鲜花好吗？就是为什么我们在这里采用双重双重花心？就是我们使用
双种花饰的这三个全部落在这一个点上，因为他们是复制的，双种花是一样的往这边看一处看长
就是这是，我们在第二道我们要去探讨一下，我们再去探索另外一个，
让他们减少冲突，至少让我们k个函数之间减少冲击，对不对？
如果我们k个函数之间都有冲突了，那我们这个不能过滤器肯定效率很低了，对不对？
避免重叠，我们的嘎斯蒂的朋友呢说的很对，这样呢我们就可以避免这几个函数重叠的，我们这里呢就是采用的双头发型，
所以呢我们的双重哈希呢也能够解决，我们那个聚集聚集哈希就是同类聚集哈希也是一样的道理。
那么这里怎么推论呢大家就不用考虑了，怎么推你只知道我们的双重哈希能够解决这种冲突就行了。
能够避免冲突就行了
好，那么呢我们来看一下这个源码，k等于2k1不是等于2，k一是我们
算出来的值，比如说我们这里要插入4000个数据，要插入4000个数数据，而且是1/千万的假阳率，
那么他会算出来我们要用23个函数，我们的杨波朋友听明白了，这个是我们填的，这两个是通过这个公式算出来的。
对，我们的k是根据n我们的n和p算出来了，根据前面一步一步算出来的，那么23
其实我们只用了一个哈希函数，明白了吗？我们的其实我们只用了一个函数，看到我们都是用的mama哈奇二，看到没有？这23个函数是通过我们这种
双重发息，就我们给他加一个步长I然后我们巴西二跟哈希跟我之间的关系，
谢谢
这个运算呢是不是跟我们前面的运算很像，左移32位跟我们的点赞这里面它是差不多的。对，明白了吧？
从这个呢通过这两个函数呢去算出来的，这32个k呃23个。
对明白了，对对对我们的衣服就是你我要听明白了，
并不是真的，我们这里并不是有23个哈希函数，我们只是用一个哈希函数呢通过这种偏移的方式呢让它伪造出来
32个哈奇函数，明白了吗？好，这个呢这是我们最核心的思想，就是我们的布隆过滤最核心的思想，那么我们来真正的来使用了
我们真正的来使用这个太好以后在工作中要使用布隆过滤器的朋友的，可以直接拿过来使用就行了。
好，我们来看一下，我们是首先我们来看一下是如何来使用的。
首先我们要初始化我们的不能过滤器，大家看一下我们初始布隆过滤器填的哪些参数，第一个呢当然是我们这个结构体，第二个呢我们来看一下，
第二个是我们的这个 C的，就是我们的k一量开始是排g的跟那个 k种子k一亮，那么我们在这里设为里，
这个就是我们要带插入的4000个元素，明白了吗？
我们要插入4000个元素，跟我们现现在这里举的例子是一样的，我们要插入4000个元素，
然后我们的假阳率是多少？这里呢是
也是千万/1，对不对？也是千万/1，我们把它设置假阳率呢是1/千万，那么我们根据我们来看一下它是怎么算的，我们通过这个
假阳率跟要插入的元素去算出我们位图要占多少空间，以及我们要用多少个哈希函数，那么我们这个
塌砌函数啊我们的位图的空间的大小是多少，呢通过这个东西我们就可以算出来算出来就是这个塞子塞子，呢我们再把它分配这个这么多的内存就行了。
这个就是分配出我们的位生成的我们的位图，这个就是我们的位图绘图的大小，绘图的那个内存块对不对？这个就是我们的位图，这个呢就是我们的
空间的，这个是我们k的大小k的个数，我们的k的个数来看一下就是这个哈希方式。
好，大家看一下我们的哈希方式，
在这里大家看一下，我们是不是首先它吸然后把它制为一，
相当于这个操作。这个代码在这里就相当于这样的。对，我们都是喜欢写c风格的代码，好，我们看一下二的，好，我们来看一下，

然后呢我们再把它计算出来就行了，然后再把它加到这个就是加入元素的时候，这个是我们往里面添加元素，把那个 key key呢
知道没有？
好，这个呢我们将t把它放进去，然后呢把它设置地址，就是把那个设置为一设置为一以后，我们就把它
每天出去，如果我们超过我们的最大数量，这里还会有1个最大数量，这个最大数量是不是我们算出来的？啊不是，是我们选定的就是那个4个。
如果呃4000，个如果我们想出来4000个，那就等于如果大于4000个，我就把它称之为一，
啊没什么区别没什么区别，当然不为零更好，但是你一定要就是实际项目中这里是填一个时间种子，填一个时间种子，在这里呢随便填一个值。
好，我们来运行一下这个代码我来运行一下这个代码。首先编译一下，
我们要指定头文件就是我们的main CPD然后上来，然后输入到我们的test里面，把我们的再运行一下。
好，大家看一下我们的功能我们的功能就是往里面插入了art item，这里1000个插入了1000个字符串，大家看到了我们插入了1000个字符串，
我们插入了1000个字不算，那么它的开头都是0words，这是个我们的URL对不对？然后我们来检测一下这个0和10,001是否在里面？
我们的0和10,001是否在我们的这个库里面，在我们的不能过滤器当中，那么呢我们通过运算大家可以看到了，我们的0呢它是存在的，是在我们的字符串当中，
我们的10,001呢它是不存在的，因为我们这里插入的是1000个数据1000个数据，那么我们这里最大是不是1000点html，这里大家应该能够清楚吧？

对应该写可能存在的，因为我们的误差率呢是千万/1，大家看到我们写的误差是1/千万。
好，这个布隆过滤器呢其实是比较简单的，关键是呢我们要将我们所学的知识能够串接起来，能够将我们所学的知识串接起来，我们的set map以及我们按unordered_map为什么他们不行，以及他们的细节有什么问题，
为什么我们的布隆过滤器可以，呢我们的布隆过滤器它没有存储这个 String，没有存储这个 key，
我们是通过这种概率型的来通过概率型的然后来映射这个点，通过这种设置假阳率的方式，就是我们能够接受多大的误差率。

代码

#ifndef __MICRO_BLOOMFILTER_H__
#define __MICRO_BLOOMFILTER_H__

/**
 *
 *  仿照Cassandra中的BloomFilter实现，Hash选用MurmurHash2，通过双重散列公式生成散列函数，参考：http://hur.st/bloomfilter
 *    Hash(key, i) = (H1(key) + i * H2(key)) % m
 *
**/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>

#define __BLOOMFILTER_VERSION__ "1.1"
#define __MGAIC_CODE__          (0x01464C42)

/**
 *  BloomFilter使用例子：
 *  static BaseBloomFilter stBloomFilter = {0};
 *
 *  初始化BloomFilter(最大100000元素，不超过0.00001的错误率)：
 *      InitBloomFilter(&stBloomFilter, 0, 100000, 0.00001);
 *  重置BloomFilter：
 *      ResetBloomFilter(&stBloomFilter);
 *  释放BloomFilter:
 *      FreeBloomFilter(&stBloomFilter);
 *
 *  向BloomFilter中新增一个数值（0-正常，1-加入数值过多）：
 *      uint32_t dwValue;
 *      iRet = BloomFilter_Add(&stBloomFilter, &dwValue, sizeof(uint32_t));
 *  检查数值是否在BloomFilter内（0-存在，1-不存在）：
 *      iRet = BloomFilter_Check(&stBloomFilter, &dwValue, sizeof(uint32_t));
 *
 *  (1.1新增) 将生成好的BloomFilter写入文件:
 *      iRet = SaveBloomFilterToFile(&stBloomFilter, "dump.bin")
 *  (1.1新增) 从文件读取生成好的BloomFilter:
 *      iRet = LoadBloomFilterFromFile(&stBloomFilter, "dump.bin")
**/

// 注意，要让Add/Check函数内联，必须使用 -O2 或以上的优化等级
#define FORCE_INLINE __attribute__((always_inline))

#define BYTE_BITS           (8)
#define MIX_UINT64(v)       ((uint32_t)((v>>32)^(v)))

#define SETBIT(filter, n)   (filter->pstFilter[n/BYTE_BITS] |= (1 << (n%BYTE_BITS)))
#define GETBIT(filter, n)   (filter->pstFilter[n/BYTE_BITS] & (1 << (n%BYTE_BITS)))

#pragma pack(1)

// BloomFilter结构定义
typedef struct
{
    uint8_t cInitFlag;                              // 初始化标志，为0时的第一次Add()会对stFilter[]做初始化
    uint8_t cResv[3];

    uint32_t dwMaxItems;                            // n - BloomFilter中最大元素个数 (输入量)
    double dProbFalse;                              // p - 假阳概率 (输入量，比如万分之一：0.00001)
    uint32_t dwFilterBits;                          // m = ceil((n * log(p)) / log(1.0 / (pow(2.0, log(2.0))))); - BloomFilter的比特数
    uint32_t dwHashFuncs;                           // k = round(log(2.0) * m / n); - 哈希函数个数

    uint32_t dwSeed;                                // MurmurHash的种子偏移量
    uint32_t dwCount;                               // Add()的计数，超过MAX_BLOOMFILTER_N则返回失败

    uint32_t dwFilterSize;                          // dwFilterBits / BYTE_BITS
    unsigned char *pstFilter;                       // BloomFilter存储指针，使用malloc分配
    uint32_t *pdwHashPos;                           // 存储上次hash得到的K个bit位置数组(由bloom_hash填充)
} BaseBloomFilter;

// BloomFilter文件头部定义
typedef struct
{
    uint32_t dwMagicCode;                           // 文件头部标识，填充 __MGAIC_CODE__
    uint32_t dwSeed;
    uint32_t dwCount;

    uint32_t dwMaxItems;                            // n - BloomFilter中最大元素个数 (输入量)
    double dProbFalse;                              // p - 假阳概率 (输入量，比如万分之一：0.00001)
    uint32_t dwFilterBits;                          // m = ceil((n * log(p)) / log(1.0 / (pow(2.0, log(2.0))))); - BloomFilter的比特数
    uint32_t dwHashFuncs;                           // k = round(log(2.0) * m / n); - 哈希函数个数

    uint32_t dwResv[6];
    uint32_t dwFileCrc;                             // (未使用)整个文件的校验和
    uint32_t dwFilterSize;                          // 后面Filter的Buffer长度
} BloomFileHead;

#pragma pack()


// 计算BloomFilter的参数m,k
static inline void _CalcBloomFilterParam(uint32_t n, double p, uint32_t *pm, uint32_t *pk)
{
    /**
     *  n - Number of items in the filter
     *  p - Probability of false positives, float between 0 and 1 or a number indicating 1-in-p
     *  m - Number of bits in the filter
     *  k - Number of hash functions
     *
     *  f = ln(2) × ln(1/2) × m / n = (0.6185) ^ (m/n)
     *  m = -1 * ln(p) × n / 0.6185 , 这里有错误
     *  k = ln(2) × m / n = 0.6931 * m / n
     * darren修正：
     * m = -1*n*ln(p)/((ln(2))^2) = -1*n*ln(p)/(ln(2)*ln(2)) = -1*n*ln(p)/(0.69314718055995*0.69314718055995))
     *   = -1*n*ln(p)/0.4804530139182079271955440025
     * k = ln(2)*m/n
    **/

    uint32_t m, k, m2;

    //    printf("ln(2):%lf, ln(p):%lf\n", log(2), log(p)); // 用来验证函数正确性

    // 计算指定假阳(误差)概率下需要的比特数
    m =(uint32_t) ceil(-1.0 * n * log(p) / 0.480453); //darren 修正
    m = (m - m % 64) + 64;                              // 8字节对齐

    // 计算哈希函数个数
    double double_k = (0.69314 * m / n); // ln(2)*m/n // 这里只是为了debug出来看看具体的浮点数值
    k = round(double_k);    // 返回x的四舍五入整数值。
    printf("orig_k:%lf, k:%u\n", double_k, k);

    *pm = m;
    *pk = k;
    return;
}


// 根据目标精度和数据个数，初始化BloomFilter结构
/**
 * @brief 初始化布隆过滤器
 * @param pstBloomfilter 布隆过滤器实例
 * @param dwSeed    hash种子
 * @param dwMaxItems 存储容量
 * @param dProbFalse 允许的误判率
 * @return 返回值
 *      -1 传入的布隆过滤器为空
 *      -2 hash种子错误或误差>=1
 */
inline int InitBloomFilter(BaseBloomFilter *pstBloomfilter, uint32_t dwSeed, uint32_t dwMaxItems,
                           double dProbFalse)
{
    if (pstBloomfilter == NULL)
        return -1;
    if ((dProbFalse <= 0) || (dProbFalse >= 1))
        return -2;

    // 先检查是否重复Init，释放内存
    if (pstBloomfilter->pstFilter != NULL)
        free(pstBloomfilter->pstFilter);
    if (pstBloomfilter->pdwHashPos != NULL)
        free(pstBloomfilter->pdwHashPos);

    memset(pstBloomfilter, 0, sizeof(BaseBloomFilter));

    // 初始化内存结构，并计算BloomFilter需要的空间
    pstBloomfilter->dwMaxItems = dwMaxItems;    // 最大存储
    pstBloomfilter->dProbFalse = dProbFalse;    // 误差
    pstBloomfilter->dwSeed = dwSeed;            // hash种子

    // 计算 m, k
    _CalcBloomFilterParam(pstBloomfilter->dwMaxItems, pstBloomfilter->dProbFalse,
                          &pstBloomfilter->dwFilterBits, &pstBloomfilter->dwHashFuncs);

    // 分配BloomFilter的存储空间
    pstBloomfilter->dwFilterSize = pstBloomfilter->dwFilterBits / BYTE_BITS;
    pstBloomfilter->pstFilter = (unsigned char *) malloc(pstBloomfilter->dwFilterSize);
    if (NULL == pstBloomfilter->pstFilter)
        return -100;

    // 哈希结果数组，每个哈希函数一个
    pstBloomfilter->pdwHashPos = (uint32_t*) malloc(pstBloomfilter->dwHashFuncs * sizeof(uint32_t));
    if (NULL == pstBloomfilter->pdwHashPos)
        return -200;

    printf(">>> Init BloomFilter(n=%u, p=%e, m=%u, k=%d), malloc() size=%.2fMB, items:bits=1:%0.1lf\n",
           pstBloomfilter->dwMaxItems, pstBloomfilter->dProbFalse, pstBloomfilter->dwFilterBits,
           pstBloomfilter->dwHashFuncs, (double)pstBloomfilter->dwFilterSize/1024/1024,
           pstBloomfilter->dwFilterBits*1.0/pstBloomfilter->dwMaxItems);

    // 初始化BloomFilter的内存
    memset(pstBloomfilter->pstFilter, 0, pstBloomfilter->dwFilterSize);
    pstBloomfilter->cInitFlag = 1;
    return 0;
}

// 释放BloomFilter
inline int FreeBloomFilter(BaseBloomFilter *pstBloomfilter)
{
    if (pstBloomfilter == NULL)
        return -1;

    pstBloomfilter->cInitFlag = 0;
    pstBloomfilter->dwCount = 0;

    free(pstBloomfilter->pstFilter);
    pstBloomfilter->pstFilter = NULL;
    free(pstBloomfilter->pdwHashPos);
    pstBloomfilter->pdwHashPos = NULL;
    return 0;
}

// 重置BloomFilter
// 注意: Reset()函数不会立即初始化stFilter，而是当一次Add()时去memset
inline int ResetBloomFilter(BaseBloomFilter *pstBloomfilter)
{
    if (pstBloomfilter == NULL)
        return -1;

    pstBloomfilter->cInitFlag = 0;
    pstBloomfilter->dwCount = 0;
    return 0;
}

// 和ResetBloomFilter不同，调用后立即memset内存
inline int RealResetBloomFilter(BaseBloomFilter *pstBloomfilter)
{
    if (pstBloomfilter == NULL)
        return -1;

    memset(pstBloomfilter->pstFilter, 0, pstBloomfilter->dwFilterSize);
    pstBloomfilter->cInitFlag = 1;
    pstBloomfilter->dwCount = 0;
    return 0;
}

///
///  函数FORCE_INLINE，加速执行
///
// MurmurHash2, 64-bit versions, by Austin Appleby
// https://sites.google.com/site/murmurhash/
FORCE_INLINE uint64_t MurmurHash2_x64 ( const void * key, int len, uint32_t seed )
{
    const uint64_t m = 0xc6a4a7935bd1e995;
    const int r = 47;

    uint64_t h = seed ^ (len * m);

    const uint64_t * data = (const uint64_t *)key;
    const uint64_t * end = data + (len/8);

    while(data != end)
    {
        uint64_t k = *data++;

        k *= m;
        k ^= k >> r;
        k *= m;

        h ^= k;
        h *= m;
    }

    const uint8_t * data2 = (const uint8_t*)data;

    switch(len & 7)
    {
    case 7: h ^= ((uint64_t)data2[6]) << 48;
    case 6: h ^= ((uint64_t)data2[5]) << 40;
    case 5: h ^= ((uint64_t)data2[4]) << 32;
    case 4: h ^= ((uint64_t)data2[3]) << 24;
    case 3: h ^= ((uint64_t)data2[2]) << 16;
    case 2: h ^= ((uint64_t)data2[1]) << 8;
    case 1: h ^= ((uint64_t)data2[0]);
        h *= m;
    };

    h ^= h >> r;
    h *= m;
    h ^= h >> r;

    return h;
}

// 双重散列封装
FORCE_INLINE void bloom_hash(BaseBloomFilter *pstBloomfilter, const void * key, int len)
{
    //if (pstBloomfilter == NULL) return;
    int i;
    uint32_t dwFilterBits = pstBloomfilter->dwFilterBits;
    uint64_t hash1 = MurmurHash2_x64(key, len, pstBloomfilter->dwSeed);
    uint64_t hash2 = MurmurHash2_x64(key, len, MIX_UINT64(hash1));

    for (i = 0; i < (int)pstBloomfilter->dwHashFuncs; i++)
    {
        pstBloomfilter->pdwHashPos[i] = (hash1 + i*hash2) % dwFilterBits;
    }

    return;
}

// 向BloomFilter中新增一个元素
// 成功返回0，当添加数据超过限制值时返回1提示用户
FORCE_INLINE int BloomFilter_Add(BaseBloomFilter *pstBloomfilter, const void * key, int len)
{
    if ((pstBloomfilter == NULL) || (key == NULL) || (len <= 0))
        return -1;

    int i;

    if (pstBloomfilter->cInitFlag != 1)
    {
        // Reset后没有初始化，使用前需要memset
        memset(pstBloomfilter->pstFilter, 0, pstBloomfilter->dwFilterSize);
        pstBloomfilter->cInitFlag = 1;
    }

    // hash key到bloomfilter中
    bloom_hash(pstBloomfilter, key, len);
    for (i = 0; i < (int)pstBloomfilter->dwHashFuncs; i++)
    {
        SETBIT(pstBloomfilter, pstBloomfilter->pdwHashPos[i]);
    }

    // 增加count数
    pstBloomfilter->dwCount++;
    if (pstBloomfilter->dwCount <= pstBloomfilter->dwMaxItems)
        return 0;
    else
        return 1;       // 超过N最大值，可能出现准确率下降等情况
}

// 检查一个元素是否在bloomfilter中
// 返回：0-存在，1-不存在，负数表示失败
FORCE_INLINE int BloomFilter_Check(BaseBloomFilter *pstBloomfilter, const void * key, int len)
{
    if ((pstBloomfilter == NULL) || (key == NULL) || (len <= 0))
        return -1;

    int i;

    bloom_hash(pstBloomfilter, key, len);
    for (i = 0; i < (int)pstBloomfilter->dwHashFuncs; i++)
    {
        // 如果有任意bit不为1，说明key不在bloomfilter中
        // 注意: GETBIT()返回不是0|1，高位可能出现128之类的情况
        if (GETBIT(pstBloomfilter, pstBloomfilter->pdwHashPos[i]) == 0)
            return 1;
    }

    return 0;
}


/* 文件相关封装 */
// 将生成好的BloomFilter写入文件
inline int SaveBloomFilterToFile(BaseBloomFilter *pstBloomfilter, char *szFileName)
{
    if ((pstBloomfilter == NULL) || (szFileName == NULL))
        return -1;

    int iRet;
    FILE *pFile;
    static BloomFileHead stFileHeader = {0};

    pFile = fopen(szFileName, "wb");
    if (pFile == NULL)
    {
        perror("fopen");
        return -11;
    }

    // 先写入文件头
    stFileHeader.dwMagicCode = __MGAIC_CODE__;
    stFileHeader.dwSeed = pstBloomfilter->dwSeed;
    stFileHeader.dwCount = pstBloomfilter->dwCount;
    stFileHeader.dwMaxItems = pstBloomfilter->dwMaxItems;
    stFileHeader.dProbFalse = pstBloomfilter->dProbFalse;
    stFileHeader.dwFilterBits = pstBloomfilter->dwFilterBits;
    stFileHeader.dwHashFuncs = pstBloomfilter->dwHashFuncs;
    stFileHeader.dwFilterSize = pstBloomfilter->dwFilterSize;

    iRet = fwrite((const void*)&stFileHeader, sizeof(stFileHeader), 1, pFile);
    if (iRet != 1)
    {
        perror("fwrite(head)");
        return -21;
    }

    // 接着写入BloomFilter的内容
    iRet = fwrite(pstBloomfilter->pstFilter, 1, pstBloomfilter->dwFilterSize, pFile);
    if ((uint32_t)iRet != pstBloomfilter->dwFilterSize)
    {
        perror("fwrite(data)");
        return -31;
    }

    fclose(pFile);
    return 0;
}

// 从文件读取生成好的BloomFilter
inline int LoadBloomFilterFromFile(BaseBloomFilter *pstBloomfilter, char *szFileName)
{
    if ((pstBloomfilter == NULL) || (szFileName == NULL))
        return -1;

    int iRet;
    FILE *pFile;
    static BloomFileHead stFileHeader = {0};

    if (pstBloomfilter->pstFilter != NULL)
        free(pstBloomfilter->pstFilter);
    if (pstBloomfilter->pdwHashPos != NULL)
        free(pstBloomfilter->pdwHashPos);

    //
    pFile = fopen(szFileName, "rb");
    if (pFile == NULL)
    {
        perror("fopen");
        return -11;
    }

    // 读取并检查文件头
    iRet = fread((void*)&stFileHeader, sizeof(stFileHeader), 1, pFile);
    if (iRet != 1)
    {
        perror("fread(head)");
        return -21;
    }

    if ((stFileHeader.dwMagicCode != __MGAIC_CODE__)
            || (stFileHeader.dwFilterBits != stFileHeader.dwFilterSize*BYTE_BITS))
        return -50;

    // 初始化传入的 BaseBloomFilter 结构
    pstBloomfilter->dwMaxItems = stFileHeader.dwMaxItems;
    pstBloomfilter->dProbFalse = stFileHeader.dProbFalse;
    pstBloomfilter->dwFilterBits = stFileHeader.dwFilterBits;
    pstBloomfilter->dwHashFuncs = stFileHeader.dwHashFuncs;
    pstBloomfilter->dwSeed = stFileHeader.dwSeed;
    pstBloomfilter->dwCount = stFileHeader.dwCount;
    pstBloomfilter->dwFilterSize = stFileHeader.dwFilterSize;

    pstBloomfilter->pstFilter = (unsigned char *) malloc(pstBloomfilter->dwFilterSize);
    if (NULL == pstBloomfilter->pstFilter)
        return -100;
    pstBloomfilter->pdwHashPos = (uint32_t*) malloc(pstBloomfilter->dwHashFuncs * sizeof(uint32_t));
    if (NULL == pstBloomfilter->pdwHashPos)
        return -200;


    // 将后面的Data部分读入 pstFilter
    iRet = fread((void*)(pstBloomfilter->pstFilter), 1, pstBloomfilter->dwFilterSize, pFile);
    if ((uint32_t)iRet != pstBloomfilter->dwFilterSize)
    {
        perror("fread(data)");
        return -31;
    }
    pstBloomfilter->cInitFlag = 1;

    printf(">>> Load BloomFilter(n=%u, p=%f, m=%u, k=%d), malloc() size=%.2fMB\n",
           pstBloomfilter->dwMaxItems, pstBloomfilter->dProbFalse, pstBloomfilter->dwFilterBits,
           pstBloomfilter->dwHashFuncs, (double)pstBloomfilter->dwFilterSize/1024/1024);

    fclose(pFile);
    return 0;
}

#endif

#include "bloomfilter.h"
#include <stdio.h>

#define MAX_ITEMS 4000      // 设置最大元素
#define ADD_ITEMS 1000      // 添加测试元素
#define P_ERROR 0.0000001   // 设置误差


int main(int argc, char** argv)
{

    printf(" test bloomfilter\n");

    // 1. 定义BaseBloomFilter
    static BaseBloomFilter stBloomFilter = {0};

    // 2. 初始化stBloomFilter，调用时传入hash种子，存储容量，以及允许的误判率
    InitBloomFilter(&stBloomFilter, 0, MAX_ITEMS, P_ERROR);

    // 3. 向BloomFilter中新增数值
    char url[128] = {0};
    for(int i = 0; i < ADD_ITEMS; i++){
        sprintf(url, "https://0voice.com/%d.html", i);
        if(0 == BloomFilter_Add(&stBloomFilter, (const void*)url, strlen(url))){
            // printf("add %s success", url);
        }else{
            printf("add %s failed", url);
        }
        memset(url, 0, sizeof(url));
    }

    // 4. check url exist or not
    const char* str = "https://0voice.com/0.html";
    if (0 == BloomFilter_Check(&stBloomFilter, str, strlen(str)) ){
        printf("https://0voice.com/0.html exist\n");
    }

    const char* str2 = "https://0voice.com/10001.html";
    if (0 != BloomFilter_Check(&stBloomFilter, str2, strlen(str2)) ){
          printf("https://0voice.com/10001.html not exist\n");
    }

    // 5. free bloomfilter
    FreeBloomFilter(&stBloomFilter);
    getchar();
    return 0;
}