目录
一，位图
1.1 关于大量数据的问题
1.2 位图概念
1.3 位图模拟实现
1.4 位图的应用
1.5 位图优缺点
二，布隆过滤器
2.1 一些场景
2.2 布隆过滤器概念
2.3 布隆过滤器模拟实现和测试
2.4 布隆过滤器查找
2.5 布隆过滤器删除
2.6 布隆过滤器优缺点
一，位图
1.1 关于大量数据的问题
先看一个面试题：
给40亿个不重复的未排序的无符号整数，然后如何快速判断一个数是否在这40亿个数中
以我们前面的知识，最先想到的有两种方法：1，排序+二分查找 2，存到哈希表和红黑树中再查
但是题目中给的是40亿个整数，我们先算下需要的内存：1G就是1024MB，是1024*1024KB，是1024*1024*1024Byte，相当于10亿Byte，所以，40亿个数需要4*40Byte大概就是16G的空间，所以由于空间的限制，上面两种方法就都可以去掉了。
所以我们需要一种更好的方法去存储这40亿个整数
1.2 位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常用来判断某个数据存不存在的。
比如上面的题目，判断数据在不在，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位位1，代表存在，为0表示不存在，如下图：
1.3 位图模拟实现
namespace bit
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);//8+1，多开一个
//这样开空间的 {(0 7)(8 15)(16 23)(24 31)...}
} // char char char
//插入
void set(size_t x)
{
size_t i = x / 8; //一个数组里面有很多个char，每个char有8个比特位，先算x需要被映射到哪个8比特位上
size_t j = x % 8; //再算在该8比特位里面的位置，整个过程可以理解为看电影时，先找在哪一排，再找具体的位置
_bits[i] |= (1 << j);
//假如x是10，10/8=1，找到第一个char，再模8就是2，然后将1往左移两格，向高位移，比如00000001，往左移就是00000010
//这样的话，我们就用非常小的空间代价把大量数据存起来了
}
//删除
void erset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);//按位取反，1与0为0完成删除，0与0还是0，不变
}
//判断在不在
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j); //如果存在，那1与1就是1，返回1；如果不在，0与1就是0，返回0
//return( _bit[i] >> j) & 1;
}
private:
vector<char> _bits;
};
void test_bit_set1()
{
bitset<100> bs1;
bs1.set(10);
bs1.set(11);
bs1.set(15);
cout << bs1.test(10) << endl;
cout << bs1.test(11) << endl;
cout << bs1.test(15) << endl;
bs1.erset(10);
bs1.erset(11);
bs1.erset(15);
cout << bs1.test(10) << endl;
cout << bs1.test(11) << endl;
cout << bs1.test(15) << endl;
}
void test_bit_set2()
{
bitset<-1> bs1; //给的是整形的最大值
bitset<0xFFFFFFFF> bs2;
}
}1.4 位图的应用
先看下下面几个题目：
①给100亿个整数，设计算法找到只出现一次的整数
②给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集
③一个文件有100亿个整数，给1G内存，请设计算法找到出现次数不超过2的所有整数
上面的题目都有个共同点，就是和1，2和大于2的数字有关，换成位就是01，10和11，所以我们可以用一个封装了两个位图的类来解决，对于问题一，在类插入时，如果是00则表示第一次出现，01表示出现过一次，10出现两次，10后的不考虑；后面的两个问题也是同样的解决逻辑
namespace bit
{
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
bool inset1 = _bs1.test(x);
bool inset2 = _bs2.test(x);
//00
if (inset1 == false && inset2 == false) //还未出现
{
// -> 01
_bs2.set(x);
}
else if (inset1 == false && inset2 == true) //第一次出现
{
// -> 10
_bs1.set(x);
_bs2.erset(x);
}
else if (inset1 == true && inset2 == false) //第二及以上次出现
{
// -> 11
_bs1.set(x);
_bs2.set(x);
}
}
void print_onse_num()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs1.test(i) == false && _bs2.test(i) == true)
{
cout << i << endl;
}
}
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
void test_bit_set3()
{
int a[] = { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 };
twobitset<100> bs;
for (auto e : a)
{
bs.set(e);
}
bs.print_onse_num();
}1.5 位图优缺点
优点：位图的存储和查找效率非常快，而且可以节省很多空间
缺点：可以看出，位图只能存储可以转化成位的整数，如果是其他类型的数就不能使用位图，比如浮点数，string等自定义类型
所以为了使位图的设计能够支持其他类型的数据，就有了下面要介绍的布隆过滤器
二，布隆过滤器
2.1 一些场景
直接看图：
又比如我们生活中的场景：
我们在注册账号时：
2.2 布隆过滤器概念
布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑的，比较巧妙的概率型数据结构，特点是高效的插入和查询，可以用来告诉你“某个数据一定不存在或者可能存在”，它是多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
2.3 布隆过滤器模拟实现和测试
struct HashBKDR
{
//BKDR字符串转int
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
struct HashAP
{
// AP
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashDJB
{
// DJB
size_t operator()(const string& key)
{
size_t hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
//降低冲突，一个值映射一个位置容易误判，映射多个位置可以降低误判
// N表示准备要映射N个值
//哈希函数个数，代表一个值映射几个位，哈希函数越多，误判率越低，但是需要的空间消耗越多
template<size_t N,
class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio * N);
_bits->set(hash1);
size_t hash2 = Hash2()(key) % (_ratio * N);
_bits->set(hash2);
size_t hash3 = Hash3()(key) % (_ratio * N);
_bits->set(hash3);
}
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio * N);
if (!_bits->test(hash1))
return false; // 准确的
size_t hash2 = Hash2()(key) % (_ratio * N);
if (!_bits->test(hash2))
return false; // 准确的
size_t hash3 = Hash3()(key) % (_ratio * N);
if (!_bits->test(hash3))
return false; // 准确的
return true; // 可能存在误判
}
private:
const static size_t _ratio = 5;
bit::bitset<_ratio* N>* _bits = new bit::bitset<_ratio * N>;
//由于std库中这个东东是用静态数组实现的，一旦数据过大就会栈溢出，所以使用new的方式将数据转移到堆上，就可以解决了
};测试一
void TestBloomFilter1()
{
BloomFilter<10> bf;
string arr1[] = { "苹果", "西瓜", "阿里", "美团", "苹果", "字节", "西瓜", "苹果", "香蕉", "苹果", "腾讯" };
for (auto& str : arr1)
{
bf.Set(str);
}
for (auto& str : arr1)
{
cout << bf.Test(str) << “ ”;
}
cout << endl << endl;
string arr2[] = { "苹果111", "西瓜", "阿里2222", "美团", "苹果dadcaddxadx", "字节", "西瓜sSSSX", "苹果 ", "香蕉", "苹果$", "腾讯" };
for (auto& str : arr2)
{
cout << str << ":" << bf.Test(str) << endl;
}
}
测试二
void TestBloomFilter2()
{
srand(time(0));
const size_t N = 100000;
BloomFilter<N> bf;
cout << sizeof(bf) << endl;//因为报栈溢出，查看bf的大小
std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(1234 + i)); //让每个字符不一样
}
for (auto& str : v1)
{
bf.Set(str);
}
// 相似
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html";
url += std::to_string(rand() + 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 = "zhihu.com";
url += std::to_string(rand() + i);
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
2.4 布隆过滤器查找
布隆过滤器不是为了解决冲突，而是为了降低冲突！
将一个元素用多个哈希函数映射到一个位图中，因此被映射到位置的比特位一定为1，所以在查找时，分别计算每个哈希值对应的比特位置存储的是否为0，只要有一个为0，表面该元素一定不在哈希表中，如果都不为0，那么可能存在，因此存在误判
2.5 布隆过滤器删除
布隆过滤器不能直接支持删除，因为在删除一个元素时会影响其他元素
2.6 布隆过滤器优缺点
优点：
①增加和查询的时间复杂度为O(K)，K为哈希函数个数，一般都是一位数，因此和数据量大小无关
②哈希函数相互之间没有关系，方便硬件运算
③布隆过滤器不存储元素本身，所以在某些保密要求较高的场合有很大优势
④在能承受一定误判时，布隆过滤器比其他数据结构有很大的空间与时间优势
⑤数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
缺点：
①有误判，即存在假阳性，不能准确判断元素是否在集合中，但也有补救方法
②不能获取元素本身
③大多数情况不能删除元素
