目录
位图
bitset
构造空间
将某个位变为0
将某个位变为1
检查是否存在
完整代码
拓展问题一
编辑
拓展问题二
布隆过滤器
判断是否存在
使用场景
哈希切割
拓展问题一
拓展问题二
位图
问题：有四十个亿未排序的不重复的无符号整数，此时提供一个无符号整数如何快速判断某个无符号整数是否在这40个亿数中？
方法1：遍历，时间复杂度为O（N）
方法2：（先）排序 + 二分查找，时间复杂度为O（logN）（不如位图的原因是排好序后如果进行插入删除麻烦，尤其是很多数时在0下标插入，需要挪动大量的数据，删除同样也要挪动大量数据，即排完序后是很好找，但麻烦在插入和删除，因此对于需要快速判断元素是否存在，并且需要频繁进行插入和删除操作的情况，使用位图是一个更好的选择）
方法3：位图
40亿个无符号整型 = 40亿 * 4 个字节 = 160亿个字节
1GB = 1024*1024*1024 = 2^30 = 1073741824 个字节 ≈ 10 亿个字节
故使用正常内存来存放的话需要16GB的内存
40亿个比特位 = 40亿 / 8 = 5亿个字节
5亿个字节 = 0.5GB = 512MB
5亿个字节 = 5亿 / 4 = 1.25亿个整型 ≈ 2^29
使用位图只需512MB大小的内存，且数组中整型的数量由40亿变为1.25亿
二分查找的文章：【二分查找】详细图解_二分法算法流程图-CSDN博客
基本概念：就是用每一位（bit）来存放某种状态的数据结构，适用于海量数据，数据无重复场景下的判断某数据是否存在的
适用场景：需要快速判断元素是否存在，并且需要频繁进行插入和删除操作的情况
bitset
原文链接：【算法竞赛学习笔记】Bitset详解和应用_bitset优化-CSDN博客
基本概念：是一种类似数组的数据结构，它的每一个元素只能是0或1，每个元素只用1bit的空间
优点：①支持所有位运算；②空间占用非常小 ③可使用只有01的字符串构造 ④查找速度块
缺点：只适用于整型
包含头文件：<bitset>
使用格式：biset<初始化的位大小> 命名 / 匿名对象
#include<bitset>
bitset<30> bi;
string s="100101";
bitset<10>bs(s); //长度为10，前面用0补充
cout<<bs<<endl; //0000100101
cout<<bs[0]<<endl; //打印1而不是0,访问顺序是从右向左
常见方法：
bi.size() //返回大小，即位数
bi.count() //返回1的个数
bi.any() //返回是否有1
bi.none() //返回是否没有1
bi.set() //全部变成1
bi.set(p)//将第p+1位变成1
bi.set(p,x)//将p+1位变成x
bi.reset() //全部变成0
bi.reset(p) //将p+1位变成0
bi.flip() //全部取反
bi.flip(p) //将p+1位取反
bi.test(p) //返回i的索引，如果不存在则返回0
bi.to_ulong() //返回它转换为unsigned long的结果，如果超出范围则报错
bi.to_ullong() //返回它转换为unsigned long long的结果
bi.to_string() //返回它转换位string的结果
注意事项：
1、bitset中的每个位都有一个固定的位置（类似于直接定址法），因此在存放整数时，bieset设置的大小与要存放的整数个数无关，只与所给整数的范围有关，如果开小了，那么大的整数就没有对应的位置，比如bitset<100>但是所给整数的范围为1~1000那么101~1000在bitset中就没有位置
2、biset<初始化的位大小N>，N是一个无符号整数因此N的最大值为UINT_MAX，取值时不能越界，32位机器上N最大为2^32 - 1，64位机器上N最大为2^64 - 1，即不同机器上可取的bitset的大小不同
构造空间
template<size_t N>//N表示要使用的位的个数
class bitset
{
public:
//构造一个能够放下N个位的整型数组，初始时bieset中的比特位均为0
bitset()
{
//无符号整型和整型都是四个字节大小
_bits.resize(N / 32 + 1, 0);//调用vector的resize，N/32为了确定整型数组大小，即要多少个存放整型元素的位置，+1是为了防止出现32.5的这种情况，向上取整
}
private:
vector<int> _bits;//依据比特位大小而开辟的整型数组
};-
一个整型 = 4 个字节、一字节 = 8 个比特位、一个整型 = 4 * 8 个比特位 = 32个比特位
将某个位变为0
1、确认具体位置
2、修改比特位：只修改一个位置上的比特位而不影响其它比特位
// 把x映射的位标记成1
void set(size_t x)
{
assert(x <= N);//x应该小于等于N，防止无法映射成功
size_t i = x / 32;//计算无符号整数x映射在第i个整型的32个比特位上
size_t j = x % 32;//计算具体应该放在第j位比特位上
_bits[i] |= (1 << j);//先将1移动到目标位置，然后在与原整型的32个比特位做或运算
}- 或运算：有一为一，其余为0
- 原整型x的比特位为0000 0000 0011 0010，现在要将第四个比特位修改为1
- 我们1将左移后得到0000 0000 0000 1000
- 或运算得到0000 0000 0011 1010，在不改变其它比特位的前提下对指定比特位进行了修改
补充：小端机器低字节放低地址，高字节放高地址，这是对于各个字节而言的，每个字节中的比特位还是左大右小（我们以为的和实际内存中比特位的存放方式不同）
将某个位变为1
// 把x映射的位标记成0
void reset(size_t x)
{
assert(x <= N);//x应该小于等于N，防止无法映射成功
size_t i = x / 32;//计算无符号整数x映射在第i个整型的32个比特位上
size_t j = x % 32;//计算具体应该放在第j位比特位上
_bits[i] &= ~(1 << j);//将1移动到目标位置并取反，然后在与原整型的32个比特位做与运算
}- 与运算：同一为一，其余为0
- 原整型x的比特位为0000 0000 0011 1010，现在要将第四个比特位修改为0
- 我们1将左移后得到0000 0000 0000 1000，取反后得到1111 1111 1111 0111
- 与运算得到0000 0000 0011 0010（处理修改位置为0其余位置为1再进行与运算是为了将原整型x的比特位中的1保留下来）
检查是否存在
//检查是否存在
bool test(size_t x)
{
assert(x <= N);
size_t i = x / 32;
size_t j = x % 32;
return _bits[i] & (1 << j);
}完整代码
template<size_t N>
class bitset
{
public:
//构造一个大小能够放下所有无符号整数状态位图的整型数组，初始时所有元素均为0 => 所有bit位均为0
bitset()
{
//无符号整型和整型都是四个字节大小
_bits.resize(N / 32 + 1, 0);
//一个整型 = 4 个字节
//一字节 = 8 个比特位
// 一个整型 = 4 * 8 个比特位
//N个无符号整型数，需要32 * N 个比特位
//+1向上取整，防止不够
}
// 把x映射的位标记成1
void set(size_t x)
{
assert(x <= N);//x应该小于等于N，防止无法映射成功
size_t i = x / 32;//计算无符号整数x映射在第i个整型的32个比特位上
size_t j = x % 32;//计算具体应该放在第j位比特位上
_bits[i] |= (1 << j);//将1移动到目标位置，然后在与原整型的32个比特位做或运算
}
// 把x映射的位标记成0
void reset(size_t x)
{
assert(x <= N);//x应该小于等于N，防止无法映射成功
size_t i = x / 32;//计算无符号整数x映射在第i个整型的32个比特位上
size_t j = x % 32;//计算具体应该放在第j位比特位上
_bits[i] &= ~(1 << j);//将1移动到目标位置并取反，然后在与原整型的32个比特位做与运算
}
//检查是否存在
bool test(size_t x)
{
assert(x <= N);
size_t i = x / 32;
size_t j = x % 32;
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
//测试函数
void test_bitset()
{
//实例化一个有100个位的位图
bitset<100> bs1;
bs1.set(50);
bs1.set(30);
bs1.set(90);
for (size_t i = 0; i < 100; i++)
{
if (bs1.test(i))
{
cout << i << "->" << "在" << endl;
}
else
{
cout << i << "->" << "不在" << endl;
}
}
bs1.reset(90);
bs1.set(91);
cout << endl << endl;
for (size_t i = 0; i < 100; i++)
{
if (bs1.test(i))
{
cout << i << "->" << "在" << endl;
}
else
{
cout << i << "->" << "不在" << endl;
}
}
}注意实现：如果想要申请一个四十亿大小的位图，可以使用以下三种方式：
bitset<-1> bs2;//-1的补码是1111 1111 1111 1111 1111 1111 1111 1111即2^32-1
bitset<UINT_MAX> bs3;//INT_MAX比四十亿小，UINT_MAX为4294967295，即2^23-1
bitset<0xffffffff> bs4;//0xffffffff也表示2^32-1下面的例子中直接使用bitset的方法，不使用自定义的方法了
拓展问题一
问题描述：给一百亿个无符号整数（可能有重复），设计算法找到只出现一次的数（例子中就拿100举例了）
解决办法：使用两个一样的位图（为了防止越界，所以创建时应该创建两个能放一百亿个位的bitset且要在64位机器下，32位N取不到100亿），如果两个位图的同一映射位置为00则表示可以映射到该位置的数没有出现，01表示可以映射到该位置的数出现一次，10表示可以映射到该位置的数出现两次及以上（设计时就设计了00 01 10三种情况，00和01都不是，那就是出现了两次及以上的）
template<size_t N>
class two_bit_set
{
public:
//修改比特位上的0和1
void set(size_t x)
{
// 00 -> 01
if (_bs1.test(x) == false
&& _bs2.test(x) == false)
{
_bs2.set(x);//_bs2位图的将第x位变为1
}
// 01 -> 10
else if (_bs1.test(x) == false
&& _bs2.test(x) == true)
{
_bs1.set(x);//_bs1位图的将第x位变为1
_bs2.reset(x);//_bs2位图的将第x位变为0
}
}
//检测某数是否只出现一次，即01
bool test(size_t x)
{
if (_bs1.test(x) == false
&& _bs2.test(x) == true)
{
return true;
}
return false;
}
private:
//定义两个缺省值为N的位图，即初始时有N个位的位图
bitset<N> _bs1;
bitset<N> _bs2;
};
void test_bitset2()
{
int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
two_bit_set<100> bs;
//依据数组a遍历修改两个位图中的位
for (auto e : a)
{
bs.set(e);
}
for (size_t i = 0; i < 100; i++)
{
//打印只出现一次的数
if (bs.test(i))
{
cout << i << endl;
}
}
}
拓展问题二
问题描述：给一百亿个无符号整数（可能重复），设计算法找到只出现一次的整数，且限制可使用的位图总大小为512MB（100亿个整数 =512MB = 5 * 可使用的内存空间）
1GB == 10亿个字节、一百亿个整型 == 400亿个字节 == 40GB ≈ 2^35
解决办法：用两个位图分范围查找，两个位图的大小均为2^28个位即256MB，每次查找的范围大小也是2^28
布隆过滤器
详细文章：详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)
基本概念：将哈希与位图结合，即布隆过滤器，布隆过滤器是由布隆在1970年提出的一种紧凑型，比较巧妙地概率型数据结构，由多个哈希函数将一个数据映射到位图结构中的多个位置，在C++中，可以使用Boost库中的boost::bloom_filter实现布隆过滤器功能
特点：高效的插入和查询，可以用来告诉用户“某样东西一定不存在或可能存在”，有效降低冲突
-
用哈希表存储用户记录，缺点：浪费空间
-
用位图存储用户记录，缺点：位图只能处理整形
注意事项：
1、 传统的布隆过滤器并不支持删除操作，因为将一个映射位置上的1变为0可能导致其它映射在该位置上的键在查找时找不到
2、误报率p与哈希函数个数k、布隆过滤器长度m、插入元素个数n的关系如下图：
- m = -（n * ln p）/ （ln 2） ^2
- k = m / n * ln 2
问题：为什么要由多个哈希函数将一个数据映射到位图结构中的多个位置？
解释：对于字符串而言，如果还是一个字符串映射到一个位置，因为字符串到映射位置中间要先转为整数，字符串无限整数有限，有可能存在两个字符串映射到整数的值相同，这样就造成了冲突（原本另外一个字符串不存在但是它与另一个字符串映射到同一位，且另一个字符串已经存在了，就会判断成该字符串也存在）使用多个哈希函数将一个字符串映射到位图的多个位置，可以尽可能地减少冲突地发生
判断是否存在
//选取三个哈希函数，用于将一个字符串映射到位图的三个不同的位置
struct HashFuncBKDR
{
// BKDR
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
struct HashFuncAP
{
// AP
size_t operator()(const string& s)
{
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0) // 偶数位字符
{
hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
}
else // 奇数位字符
{
hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashFuncDJB
{
// DJB
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash = hash * 33 ^ ch;
}
return hash;
}
};
//布隆过滤器
template<size_t N,
class K = string,
class Hash1 = HashFuncBKDR,
class Hash2 = HashFuncAP,
class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
//将某个键用三个哈希函数映射到位图的三个不同的位置
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % M;//调用第一个哈希仿函数 % m获得一个映射位置
size_t hash2 = Hash2()(key) % M;//调用第二个哈希仿函数 % m获得一个映射位置
size_t hash3 = Hash3()(key) % M;//调用第三个哈希仿函数 % m获得一个映射位置
//进行映射
_bs->set(hash1);
_bs->set(hash2);
_bs->set(hash3);
}
//判断某个键是否存在
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % M;//调用第一个哈希仿函数计算第一个映射位置
if (_bs->test(hash1) == false)//如果没有找到就返回假
return false;
size_t hash2 = Hash2()(key) % M;
if (_bs->test(hash2) == false)
return false;
size_t hash3 = Hash3()(key) % M;
if (_bs->test(hash3) == false)
return false;
return true; // 返回存在真时，因为多个键可能映射在同一位置，所以返回为真时存在误判
}
private:
static const size_t M = 10 * N;//最佳的M的取值
bit::bitset<M> _bs;
};
使用场景
解释：可以使用布隆过滤器减少向数据库访问的次数，如果键经过布隆过滤器后表示存在，因为布隆过滤器的存在情况会存在误判，所以要接着去数据库寻找内容，但如果在布隆过滤器中不存在就不用去数据库寻找了
哈希切割
拓展问题一
问题描述：给两个文件，分别有100亿个query（字符串），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
分析：假设一个query为五十字节，100亿个query占用500G空间，很明显不能将两个文件同时放入内存中进行比较
存放：我们假设这两个文件分别为A和B，同时有1000个存放A和B中query的子文件Ai和Bi（i表示下标），之后从A中依次读取一个query（读取时不以字节为基本单位而是以一个字符串为基本单位，不会将一个字符串拆开）放入哈希函数HashFunc（可能相同可能不同）获取对应的哈希码后再 % 1000得到子文件下标i，然后就将query放入Ai文件（B也一样），最终A和B相同的query一定会进入编号相同的Ai和Bi小文件
时间复杂度：O（N）（最坏情况下只需A0-B0、A1-B1这样比较N次就可以判断出是否存在交集）
而如果不细分为Ai和Bi查找时的时间复杂度就为O（N^2）因为每次一个子文件要和所有子文件比较，N个子文件 * N次比较 = O^2
查找：将Ai中存放的query放入set类型的对象seta中，将Bi中存放的query放入set类型的对象setb中，利用循环++i在seta和setb中寻找交集即可（set<string> seta、set<string> setb）
若遇到某个小文件的大小超出题目的内存限制时（抛异常超出内存限制），可能的原因有两种：
①过多的完全相同的query映射到同一个子文件，但因为set可以去重，所以查找时将这些query放入set类型的对象中后，重复的内容不会被放入，因此这种情况影响不大
②过多不同的query映射到同一个子文件，这时set不能去重，需要二次处理，再寻找一个新的哈希函数，进行切分放入新的Ai和Bi子文件中
这种方法叫做存放和查找的方式叫做：哈希切割
拓展问题二
问题描述：给一个超过100G大小的log file, log中存着IP地址, 设法找到出现次数最多的IP地址？
分析：统计次数应该用map<string，int>，同时如果此时抛异常说超出内存限制，就只存在一种情况，即有冲突的IP地址很多，此时需要换一个新的哈希函数进行二次切分处理
解决方法：仍然说上面的哈希切割方法
~over~
![数据结构05：树与二叉树 习题02[C++]](https://img-blog.csdnimg.cn/direct/b2967a3f83c145919c19754b668c927c.png)
![[AI OpenAI] 推出ChatGPT Edu](https://img-blog.csdnimg.cn/img_convert/70eff9f261c8e65ca2b615859c622084.png)
