文章目录
- 一、位图
- （1）位图概念介绍
- （2）简单模拟实现
- （3）位图应用
- 二、布隆过滤器
- （1）关于布隆过滤器概念及介绍
- （2）布隆过滤器的使用场景
- （3）模拟实现
- （4）布隆过滤器天生不支持删除reset
- （5）BF总结
- 三、海量数据处理
- （1）问题1/2
- （2）问题3/4
- （3）问题3
- 四、所有源码(含BF)
一、位图
（1）位图概念介绍
先看下面的一道题：
1.有40亿个不重复的无符号整数，无序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
如果我们放到哈希表或红黑树中或用排序和二分查找这两种方法。
前两种方法不可行，因为40亿个整数占用大约16G的内存空间，第一要排序需要先把数放到内存，只能用文件归并排，但是不能文件中不能搞二分查找即不能用下标去访问；第二如果放到红黑树但是同样放不进去，如果放到树里面，给一棵树查找一次，但是这里是很多数据，来一个树先读2G查找再释放掉，再来一个树放进去查，不断的查，与其这样不如读的时候判断一下没必要放树里面，直接暴力查找了，还有额外的消耗表里面的结点不光有数据还是有指针。所以上俩种方法不行主要原因就是内存不够。
我们可以用一种直接定址法，我们可以最少用1字节即char标记一个数在不在，一个char数组最少消耗4G，我们还可以最少，即开比特位，比如一个字节开8个比特位，我们也可以开int的，如下图，0到7映射到第一个cha人，8到15映射到第二个char，依次映射，40亿个数，如果是一个整数去存储需要16G，现在是按位去存储，用位去标识，缩小了32倍，也可以这么说，这是40亿个整数看成40亿个比特位，除以8大概就是相当于5亿字节，需要512MB，这里东西就叫位图。
位图：它是一种直接定址法的哈希映射，用来判断整型的在不在的问题，用每一位来存放某种状态，适用于海量数据，数据无重复的场景。
（2）简单模拟实现
template<size_t N>
class bitset
{
public:
bitset()
{
_b.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _b[i] & (1 << j);
}
private:
vector<char> _b;
};
库里面这个函数是有的，我们是不能去按位去开数组的，我们可以用vector数组存储char类型控制char。
我们需要实现里面三个核心接口set和set以及test，set把x映射的那个比特位设置成1，reset把它设置成0，test判断在不在。
初始化构造：我们还需要空间，我们要N个比特位我们需要开N/8，但这样少开一个比特位需要加上1，然后初始都为0。
先实现set：
但是我们怎么去找到对应的比特位？
1、一个字节是8比特位，我们是算它在第几个8比特位，我们可以直接除8算出i即在第i个char数组位置，接着算在第几个8比特第几个上面，可以直接模8算出j即char位置第几个比特位。
2、然后我们把char的第j位设置为1，我们需要进行位运算，我们需要把j位设置成1，其他位不能影响需要用到或，因为或有一个特点0和任何数或还是任何数，我们还需用1进行左移j位，左移是向高位移，最后再或等，这样设置完毕。如下图
实现reset：
同样先算出i和j，想让它第j位设置为0，先左移再取反，但是不能那个影响其它位，就需要按位与等，因为1和1与还是1，0和1与还是0。
实现判断test：
同样先算出i和j，对对应的位置直接与，两种可能性，与之后除了第j位其他位都为0，如果第j位是0，那么结果就是0返回假，如果第j为不是0，那么结果是非0
值，非0值即为真不管是1还是其他非0数，都返回真。注意位运算优先级是很低的需要加括号。
我们测试一下：
那么开头那个问题就可以解决。
（3）位图应用
我们再看几个问题：
2.给100亿个整数，设计算法只出现一次的整数。
部分核心代码：
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (_b1.test(x) == false && _b2.test(x) == false)
{
_b2.set(x);
}
else if (_b1.test(x) == false && _b2.test(x) == true)
{
_b1.set(x);
_b2.reset(x);
}
}
void one_print()
{
for (size_t i = 0; i < N; ++i)
{
if(_b2.test(i))
{
cout << i << endl;
}
}
}
public:
bitset<N> _b1;
bitset<N> _b2;
};
100亿个整数不影响我们开空间，因为可能有重复的，我们可以搞2个位图。出现0次就是00，出现1就是01次，出现1次以上就是10。
直接运用刚才的两个位图，直接复用，两个位进行组合。
_b1和_b2都test一下如果都是00表示没有出现过，就把_b2设置成1即01表示出现了1次，如果是_b1为0，_b2为1就把_b1设置为为，_b2设置为0即10表示出现2次。
接着写个打印函数去找出现1次，N是个范围，只需要遍历，只需要判断_b2是真，就是出现1次，因为01，打印即可
如图：
3.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
第一种：可以把其中一个文件的值，读到内存的一个位图中，再读取另一个文件，判断在不在上面位图中，在就是交集。但是找出的交集存在重复的值，还要再次去重。可以改进，每次找到交集，都将上面的位图对应的值设置为0解决重复问题。
第二种：更好的是放到两个位图中，把文件1放到位图1，把文件2放到位图2。
读取文件1的数据映射到位图1，读取文件2的数据映射到位图2，用for循环遍历范围N，如果位图1和位图2都在就是交集。
如果数据量大就选第二种方法，反之第一种。
4.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
这道类似第二道，用第二道题的思想，出现0次用00表示，出现1用01表示，出现2次用10表示，出现3次以上用11表示。不超过2次的所有整数就去找01和10。
总结：位图也是一种哈希结构，效率很高速度快，O(1)，而且还节省内存。
缺点就是：只能映射整型，统计次数也有限。其他类型string，double等不能映射。下面的布隆过滤器就是解决这种问题。
二、布隆过滤器
（1）关于布隆过滤器概念及介绍
如果是大量字符串，位图是没法完成映射的，如果用哈希或红黑树，会有大量消耗，有附带消耗。我们可以用仿函数转成整型，间接映射，但是这样会有一个冲突问题，假如字符串是汉字，字符串的长度是8，会有256^8中组合，会存在多对一冲突。
而布隆过滤器的思想不是解决冲突，而是降低冲突概率，一个值映射一个位置容易误判，映射多个位置就可以降低误判率，即将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找，分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
（2）布隆过滤器的使用场景
首先要找到它的特点，它能容忍误判的场景，比如我们在注册时，快速判断昵称是否使用过。如果没注册过，会立刻给你反馈，说明是准确的；如果它注册过有两种可能性，把昵称放到这个布隆中，第一它真的被用过了，第二它没被用过，存在了误判，但是从用户使用场景上是不知道的，可以允许误判，昵称用户感知不到。
如果是昵称，10亿个用户是存在数据库里面的，数据库的数据本质在磁盘上，快速不判断是不去找磁盘的，因为磁盘IO太慢了，所以我们把昵称全部读到布隆过滤器里面，节省空间，在布隆就直接反馈昵称注册过，不在布隆就反馈没注册过，但是在是会存在误判的，有可能真没被注册过。
如果是手机号，判断不在就直接返回没注册过，不在是准确的，判断在，可能会存在误判，明明没有注册过，这时候要去数据库里面磁盘上确认一下，然后再返回这个结果，以数据库的结果为准。这个跟直接去数据库查找相比，从整体而言效率是高的。因为布隆是在内存当中时间复杂度是O(1)，把不在的都快速过滤掉，如果在的话再去找数据库，单拿在的场景多消耗了一点，整而言效率高，减少了数据库的访问。
布隆过滤器为啥叫这个名字，它是先提前做一层过滤，不在就直接走了，在的话再去数据库确认一下再返回。它的优点是快节省内存，缺点存在误判。
如下图：
大部分使用布隆过滤器的数据类型都是用字符串，如果用整型就用位图。
减少磁盘IO和网络请求，一旦一个值必定不存在，就不用进行后面的查询。BF实践当中一般都是做数据过滤，判断在不在，如果不在就不用再往后请求了，如果在继续再往后面请求，如果再次请求数据都在数据库里面，甚至数据库在远程服务器中，还要走一层网络，成本还是蛮高的。
（3）模拟实现
主要先上部分核心代码，后面有原码。
template<size_t N,class K=string,class Hash1= BKDRHash,
class Hash2= APHash,class Hash3= DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
_b.set(hash1);
size_t hash2 = Hash2()(key) % len;
_b.set(hash2);
size_t hash3 = Hash3()(key) % len;
_b.set(hash3);
}
bool test(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
if (!_b.test(hash1))
return false;
size_t hash2 = Hash2()(key) % len;
if (!_b.test(hash2))
return false;
size_t hash3= Hash3()(key) % len;
if (!_b.test(hash3))
return false;
return true;
}
private:
static const size_t _M = 6;
bitset<N*_M> _b;
};
我们在模板里面增加三个hash函数算法，可以在网上搜字符串哈希函数算法，我所取的这个三个hash函数的散列质量及效率是别人进过测试后排在前三的。在set函数里面先给一个哈希映射的第一个位置，把key转成可以去摸的整型值，摸上N，同理3个hash函数，set3个位置。
如果判断在不在，三个位置都要在才在即真，只有一个位置不在就是不在即假。
有一个关键问题：在和不在谁会存在误判？
在是不准确的，会存在误判，如果判断一个位置不在，说明至少有一个位置为0，上面说到只要有一个不在就是不在；如果判断在的话，这个位置不可能为0，三个位置都为1。比如一个字符串，本来不在，但是它映射的位置都跟别人冲突了即都被被人映射了，所以导致认为它在，即误判。
hash函数个数，代表一个值映射几个位，哈希函数越多，误判率越低，但是希函数越多，平均空间越多。
这是下面别人通过实验总结出来的公式，来降低误判率，此图链接来源于：链接。
以上的测试结果可以看出布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。哈希函数的个数也需要考虑，但治不了本。因为n插入个数和BF长度存在一个倍数，我们适当增加倍数_M，来验证一下，6是最好的。如图：
找的是不在的字符串去测试，因为本来就在测试时它肯定在，它不在的有可能能会被判断成在，这就是误判，结果是在是不准确的，因为本来不在它会判断成在。
（4）布隆过滤器天生不支持删除reset
因为会对别人造成影响以及其他影响(即使用计数法(由多个比特位控制)也非常不好，不确定删除哪个数据以及本来不在误判成在的数据，把它删了其他的又找不到了)，如下图，删除nza，会把2号位置置成0，再查找azn，查找时就不在了，有关联影响。
（5）BF总结
布隆过滤器优点：
1.增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
1.有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
建立一个白名单，存储可能会误判的数据)
2.不能获取元素本身
3.一般情况下不能从布隆过滤器中删除元素
4.如果采用计数方式删除，可能会存在计数回绕问题
三、海量数据处理
(1) 哈希切割
（1）问题1/2
1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
这里是找交集，不是整型的是字符串。
近似算法:就是之前说的，先把一个文件的数据放到BF中，再去找交集判断在不在，在就是交集，当然后面还有去重的需求。
精确算法：query本质就是一个字符串，假设单个query平均50字节，100亿个就是500G。我们可以如下图把文件A和B文件分别切成1000份（linux指令就可以切，写一个进程帮我们执行切文件的指令。），这样做还是要和每个文件找交集，所以我们可以用hash切分，用一个哈希函数计算出每个文件对应的i即文件号，然后让A0和B0，A1和B1依次找交集，只需要编号相同的小文件直接去找交集，因为一个一个的小文件就像一个桶，进入同一个桶都是冲突的值，A和B相同字符串会进去编号的相同小文件，而且我们用的是相同hash函数。
但是会有一个问题：
某些小文件不是平均切分，可能会出现冲突过多，某个Ai，Bi小文件过大，太大加载不去内存，如果换个哈希函数再切，前提还是要算出这个两个文件多大，才决定你要切多少份，更重要的问题是继续换哈希函数可能切不动，因为有大量重复，而且这里还有两种可能：
第一种可能单个文件有大量重复的query字符串
第二种可能有大量不同的query。
第一种重复的值不管用什么哈希函数都切不动，第二种大量不同的字符串肯定可以继续用哈希函数切分，主要是怎么区分，要分别处理，
解决：
我们可以这样直接使用一个unordered_set/set,依次读取文件query，插入set中
如果读取整个小文件query，都可以成功插入，那就是第一种，因为set插入key，如果有了返回false，没有继续插返回true，插入过程是不会失败的。
如果读取整个小文件query，插入过程抛异常，说明内存满了装不下，会抛bad_alloc异常，那就是第二种，要换其他哈希函数，再次分割，再求交集。
2.如何扩展BloomFilter使得它支持删除元素的操作
把每个映射的值改成引用计数，每个值由多个比特位组成，如01,10,11，分别代表1次，2次。3次，往上加，取决于用几个比特位。但其实没必要，会浪费空间，本身就不支持删除。
（2）问题3/4
3.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
还是一样的，哈希切分500份，依次读取数据，Hash函数计算出i，这个ip就是第i个小文件，直接用unordered_map/map统计出现次数。
如果某个过程中，出现抛异常，则说明单个文件小文件过大，冲突太多，需要重新换哈希函数，再次哈希切分这个小文件，比如这个单个小文件10G再切个30份，AA0到AA29，再生成小文件，和处理源文件的逻辑是一样的；没有异常正常统计，统计完一个小文件，记录最大的，clear，再统计下一个文件。
（3）问题3
4.与上题条件相同，如何找到top K的IP？
找次数最多IP，可以建一个K个数的小堆，小堆每一个位置是pair，key是ip，value是次数，如果比你大我就进去。
总结：相同的IP一定进入相同小文件，读取单个小文件，就可以统计IP出现次数。
四、所有源码(含BF)
bitset.h
#pragma once
#include<vector>
#include<string>
#include<iostream>
#include<ctime>
using namespace std;
namespace nza
{
template<size_t N>
class bitset
{
public:
bitset()
{
_b.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _b[i] & (1 << j);
}
private:
vector<char> _b;
};
void test1()
{
bitset<100> bs;
bs.set(6);
bs.set(15);
bs.set(66);
cout << bs.test(6) << endl;
cout << bs.test(7) << endl;
cout << bs.test(66) << endl;
cout << endl;
}
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (_b1.test(x) == false && _b2.test(x) == false)
{
_b2.set(x);
}
else if (_b1.test(x) == false && _b2.test(x) == true)
{
_b1.set(x);
_b2.reset(x);
}
}
void one_print()
{
for (size_t i = 0; i < N; ++i)
{
if(_b2.test(i))
{
cout << i << endl;
}
}
}
public:
bitset<N> _b1;
bitset<N> _b2;
};
void test2()
{
int a[] = { 6, 22, 99, 88, 6, 4, 3, 22, 5,};
twobitset<100> tb;
for (auto e : a)
{
tb.set(e);
}
tb.one_print();
cout << endl;
}
struct BKDRHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 31;
}
return hash;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long i = 0; i < s.size(); i++)
{
size_t ch = s[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& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N,class K=string,class Hash1= BKDRHash,
class Hash2= APHash,class Hash3= DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
_b.set(hash1);
size_t hash2 = Hash2()(key) % len;
_b.set(hash2);
size_t hash3 = Hash3()(key) % len;
_b.set(hash3);
}
bool test(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
if (!_b.test(hash1))
return false;
size_t hash2 = Hash2()(key) % len;
if (!_b.test(hash2))
return false;
size_t hash3= Hash3()(key) % len;
if (!_b.test(hash3))
return false;
return true;
}
private:
static const size_t _M = 6;
bitset<N*_M> _b;
};
void test_BF1()
{
BloomFilter<100> b;
b.set("nza");
b.set("zan");
b.set("qwe");
b.set("ewq");
cout << b.test("nza") << endl;
cout << b.test("zan") << endl;
cout << b.test("qwe") << endl;
cout << b.test("ewq") << endl;
cout << b.test("kd") << endl;
}
void test_BF2()
{
srand(time(0));
const size_t N = 10000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https://www.education.com/-kd/2023/06/12/66666.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "https://www.education.com/-kd/2023/06/12/66666.html";
url += std::to_string(999999 + i);
v2.push_back(url);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str))
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string url = "https://editor.csdn.net/md?articleId=131012473";
url += std::to_string(i + rand());
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
}
test.cpp
#include"bitset.h"
int main()
{
nza::test1();
nza::test2();
nza::test_BF1();
nza::test_BF2();
return 0;
}
