前言
本次主要讲解bitset和布隆过滤器
一、什么是bitset？
第一次提到bitset应该是在第一次算法博客上提到，它可以完美的代替bool a[N],bitset到底是什么，我们下面来讲解一下
bitset称为位图，bit–比特位，set集合，位图，就是每一位存放一种状态，通常判断某个数据在不在，使用于数据量大，无重复，只关注在不在的数据的情况。
当然库里是有bitset的
bitset
这里放的是位数，比如有bitset<1000 > bt,就是存放1000bit位，想表示10存在，就把10搞成1。
一些重要操作
我画横线的就是常用的，但是用法不多，就都提一下了解了解
operator[]
有点像我们的map的[]，相当于直接对某一位进行操作，可以访问，bt[2] = 1,bt[3] = 0;
count
表示记录了多少位是1，原理相当于遍历
size
比如bitset< 1000 > bt；那他的size就是1
test
表示测试某一位是否是一，如果是1返回true，否则返回false
any
表示是否有任意一位搞成了1，只要有就返回true，否则返回false
none
和any相反
all
表示是否所有位都是1，是则返回true，否则返回false
set
某一位搞成1
reset
某一位搞成0
流插入和流提取
cout比较好理解，就是把这些位数打印出来
cin是干啥的？ 输入一个字符串，将这个字符串给bitset，如果输入位数小于size，会自动补齐0，此时流状态正常，如果输入非法字符，除了0 / 1的都为非法字符，此时会把bitset的每一位都搞成0，流状态会被设置成fallbit，之后无法读入，如果输入位数多余size，流状态也会被设置为fallbit，之后也无法读入。
所以，要使用就按规则使用，可以位数小于或者等于size，也不要输入非法字符。
to_string
变成字符串
实际上bitset没啥玩意，稍微看看就看懂了
二、模拟实现
底层就存放数组就可以，第一个问题， 数组内部放什么？因为bit位没法存放啊，可以存放char / int，存放int，一个int在32位下是4个字节，32个bit位，如果想开1000位，可以拿1000 / 32 + 1得到需要存放的位数，又因为是0到31是第一个数字，这么求出来的大小正好
template<size_t N>
class bitset {
public:
bitset()
{
_a.resize(N / 32 + 1);
}
private:
vector<int> _a;
};
接下来思考最重要的set,reset,和test怎么搞。当然第一步就是拿到这个数在哪一位，i / 32拿到第i + 1个数，下标是i，因为位数是从0开始计算的，这样正好，比如想把第32位搞成1，就是32 / 32，第二个数字的第0位，下标是1，所以取到位数的核心操作就是
size_t i = x / 32;
size_t j = x % 32;
set
搞成1，很简单的位运算，这里利用了a | 0 = a,只控制1那一位进行变化
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_a[i] |= (1 << j);
}
reset
我们需要控制只有一位变成0，第一步可以搞一个1左移j位然后取反，这样得到只有那一位是0，再&上就完事了。这里利用了1 & a = a.
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_a[i] &= (~(1 << j));
//利用一个特性，1 & a = a,只控制要变的那一位是0
//00 00 01 01
//11 11 10 11
}
test
就看那一位是不是1就行，可以把1左移j位去&，也可以像这么写
bool test(const int& x)
{
size_t i = x / 32;
size_t j = x % 32;
return (_a[i] >> j) & 1;
}
剩下其实想实现都不难，有一个比较难就是operator[]，看看库里
只读比较简单，但是改怎么搞，没法返回那一位啊，库里给的是reference，这其实是一个类，返回值应该是一个对象，这个reference对象重载了operator =，同时应该存放了指针能确保拿到vector
这个实现不是库里的实现，是我自己理解来的实现，实现的比较麻烦，但是基本可以实现相同的效果，看看就行，别学，还是建议去看源码来学
class reference {
private:
vector<int> *_a;
int _i, _j;
public:
reference(vector<int>* t,int pos1,int pos2)
:_a(t),_i(pos1),_j(pos2)
{}
reference& operator=(bool x)
{
if (x)
{
(*_a)[_i] |= (1 << _j);
return *this;
}
else
{
(*_a)[_i] &= (~(1 << _j));
return *this;
}
}
reference& operator=(const reference& ot)
{
bool x = (*ot._a)[ot._i] & (1 << ot._j);
return operator=(x);
}
operator bool()const
{
return ((*_a)[_i] & (1 << _j)) ;
}
};
reference operator[](size_t pos)
{
assert(pos < _a.size() * 32);
size_t i = pos / 32;
size_t j = pos % 32;
return reference(&_a, i , j);
}
bool operator[](size_t pos) const
{
assert(pos < _a.size() * 32);
size_t i = pos / 32;
size_t j = pos % 32;
return (_a[i] & (1 << j)) != 0;
}
三、布隆过滤器
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
来看使用场景，比如你注册需要起一个名字，如果这个名字重复了，不可以注册，如果没重复就可以注册，这种需要快速返回结果的情况就可以使用布隆过滤器，因为如果重复了，你也不知道是否查询的错误，如果没重复，那么结果一定是对的，就可以重复。
当然，如果要保证结果正确，可以用一些SQL等记录已经有的数据，如果不存在直接返回，如果存在再去存放数据的容器里面去寻找。
布隆过滤器
比如利用三个哈希函数来映射
为什么不存在是一定的，存在是不一定的，如果这个字符串存在，那他一定会映射到了三个值，如果不存在，那他的三个对应的值一定没有被映射到。
比如映射进去两个字符串，1映射的大小是100，200，300，2是300，400，500，
查找：第一个字符串映射的值是100，500，600，那他就一定不存在，因为如果他存在，这三个值一定被映射到了，所以不存在是一定的，第二个字符串映射的值是100，400，500，此时就找到了，但是这个字符串不存在，所以此时存在是不一定的。
四、模拟实现
这里几个要点：
1.查找的逻辑：只要有一个不存在就返回false，都存在返回true
2.采用的哈希函数最好评分较高，冲突率小
其余模拟比较简单，上代码：
#pragma once
#include<bits/stdc++.h>
using namespace std;
struct BKDRHash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (size_t i = 0; i < str.size(); ++i)
{
hash = hash * 131 + str[i];
}
return hash;
}
};
struct APHash
{
size_t operator()(const string str)
{
size_t hash = 0;
size_t ch;
for (size_t i = 0; i < str.size(); ++i)
{
ch = str[i];
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string str)
{
if (str == "")
{
return 0;
}
size_t hash = 5381;
for (auto ch : str)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N,class K = string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>
class BloomFilter
{
public:
void Set(const K& key)
{
_bs.set(HashFunc1()(key) % N);
_bs.set(HashFunc2()(key) % N);
_bs.set(HashFunc3()(key) % N);
}
bool Test(const K& key)
{
//只要有一个不在就是不在，因为不在是确定的，哈希值即使冲突，只要有映射都会存在
//如果三个都存在，就return true，有概率会导致错误的结果，但是概率很小
if (!_bs.test(HashFunc1()(key) % N))
{
return false;
}
if (!_bs.test(HashFunc2()(key) % N))
{
return false;
}
if (!_bs.test(HashFunc3()(key) % N))
{
return false;
}
return true;
}
private:
bitset<N> _bs;
};
可以自己去测试测试误判率，当然，分析来讲，插入的字符串越多越容易误判。
优点：
既然他是哈希 + 位图的结合体，那他就同时有他俩的优点。
1… 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
7.不方便删除
缺点
1…有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题（存疑？目前有文章说计数方式也不能删除）
五、一些常见的问题
给定100亿个整数，设计算法找到某个整数是否存在？
1.排序 + 二分
2.遍历
前两种方式都不合适，因为首先得找到数组存放进去，虽然整数只有四十多亿个，大概需要16个G的数组
所以需要使用bitset，存放四十多亿个比特位，只需要0.5个G
给定100亿个整数，设计算法找到只出现一次的整数？
两个bitset，用00 01 10表示没出现过，出现过1次，出现过两次以及以上的数字，最后找01就可以了
template<size_t N>
class TwoBitSet
{
//记录只出现一次的
public:
void set(size_t x)
{
//这里控制状态可以自己来控制
if (bt1.test(x) == false)
{
bt1.set(x);
}
else
{
bt2.set(x);
}
}
bool testonetime(size_t x)
{
return bt1.test(x) && !bt2.test(x);
}
private:
myspace::bitset<N> bt1, bt2;
};
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
还是使用两个bitset，第一个文件入第一组数据，第二个文件入第二组数据，遍历所有位数，两个都是1就说明是交集。
1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
还是使用两个bitset，利用00 01 10 11来存放四种状态，表示0次，1次，2次，2次及以上，最后遍历一下即可。
1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
近似算法就是布隆过滤器，第一个文件入布隆过滤器，第二个文件进行查找即可
精确算法
既然要精确， 就需要全整进去，但是只有一个G内存怎么办？可以把一个大文件分成多个小文件，怎么分？
1.第一种方式，平均分配，比如两个文件都平均分成十份，然后每一份和另外十份对比，找交集，这种方式不推荐，效率太低。
2.第二种方式，哈希切割，比如Hashi = Hash(query) % 10,这样分成十个文件，再去相同编号的文件里去寻找交集就可以（利用set），因为相同的query的哈希值映射到的文件一定相同。
第二种方式有没有问题？如果100亿个query哈希值重复太多/重复的query太多怎么办？
这两种情况都会导致切割之后一个文件还是内存太大，set放不进去。
如果是第一种情况，换一个哈希函数就可以，说明这个哈希函数不好。
如果是第二种情况，用一个set去重就可以。
但是我怎么知道哪种方式出的问题呢？
可以先把切割之后仍然比较大的文件入set，这里的query都一定哈希值相同，如果抛内存异常，说明这个大多数query都是冲突，换一个哈希函数，如果正常入进去set，就自动去重了，然后再正常玩就可以。
完整代码
总结
布隆过滤器了解，bitset的使用要清楚。