详解C++位图/布隆过滤器+海量数据处理
目录
3.2.1. 给定100亿个整数，设计算法找到只出现一次的整数？
3.2.2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
3.2.3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
3.3.1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
3.3.2如何扩展BloomFilter使得它支持删除元素的操作
一、位图
1.1位图的概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
例：一个int类型的数据占用4个字节，即32个bit位，可以表示0-31的数是否存在。
1.2位图的实现
位图的实现主要是以下三个函数：set（）、reset（）、test（）。
- 对于set，想要让某一比特位变为1其他位不变，则可以用1按位或对应的比特位，那就只需让1向高位移动j位，然后用位图中对应的字节进行按位或等即可。
对于reset，想要让某一比特位变为0其他位不变，则可以用0按位与对应的比特位，那就只需让1向高位移动j位，然后按位取反，最后用位图中对应的字节进行按位与等即可。
对于test，我们可以让对应比特位按位与1，其他比特位按位与0，这样其他比特位都是0，如果测试的比特位是1，则结果是非0，那就是true，如果测试的比特位是0，则结果是0，那就是false。
namespace zyl
{
// 非类型模板参数
template <size_t N> //容量N个字节
class bitset
{
public:
//构造函数
bitset()
{
_bits.resize(N / 8 + 1, 0);//开辟最少一个字节的空间
}
//置位函数，将指定的位设置为1
//因为我们用的char存储的数据，一个char为一个字节,
void set(size_t x)
{
size_t i = x / 8; //x/8 表明i是在vector中的哪一个字节当中
size_t j = x % 8; //j表明 在 vector 第i个字节中的第几位
_bits[i] |= 1 << j; //把vector 第i个字节中的第j位置1；
}
//复位函数，将指定位设置为0
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j); //把vector 第i个字节中的第j位置0；
}
//访问函数，获取指定的位的值
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j); //用& 只查看 不修改
}
private:
vector<char> _bits;
};
}1.3、位图应用面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
1.我们常规的方法，直接遍历，时间复杂度O（N），但是40亿个数中寻找一个数，无异于大海捞针，直接遍历所消耗的时间还是很多，更别说我们用什么来存储这40亿个数?
2.利用二分查找法，二分查找法的时间复杂度为O(logN),时间复杂度来说很快，但是二分查找只适用于有序的数列，我们还得先进行排序，最快的快排也会消耗大量时间?
3.采用位图
首先，我们把数据存在对应的比特位，节省了大量的空间（42亿个数据换算比特位进行存储，也就是需要0.5GB，512MB内存申请是没有压力的。），然后一个比特位，只能显示0/1，正好我们用0/1代表数据是否存在。
二、布隆过滤器
2.1 布隆过滤器提出
我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？
1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：不能处理哈希冲突
3. 将哈希与位图结合，即布隆过滤器
2.2布隆过滤器概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
2.3 布隆过滤器模拟实现实现
2.3.1?布隆过滤器的插入
一般的位图下，每一个数据只跟位图产生一个映射点，而且只能用于整型。但布隆过滤器是每一个数据可以有N个映射点，N个映射点对应于N个哈希函数，这个是我们自己定义的。用哈希函数将非整型转化成整型。映射多个位置，降低误判率
插入原理：添加一个元素时，用哈希函数计算出该元素在位数组中的多个位置，并将这些位置的值设为1
void set(const K& key)
{
//通过不同的哈希函数，让同一个数据可以计算出三个不同的位置
size_t hash1 = HashFunc1()(key) % (N * X);
size_t hash2 = HashFunc2()(key) % (N * X);
size_t hash3 = HashFunc3()(key) % (N * X);
//计算出位置后，使用位图的set方法将位图上对应的比特位进行0变1
_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
}2.3.2?布隆过滤器的查找
分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
bool test(cost K& key)
{
//先逐个位置判断，如果它是0，直接返回false
size_t hash1 = HashFunc1()(key) % (N * X);
if (!_bs.test(hash1))
{
return false;
}
size_t hash2 = HashFunc2()(key) % (N * X);
if (!_bs.test(hash2))
{
return false;
}
size_t hash3 = HashFunc3()(key) % (N * X);
if (!_bs.test(hash3))
{
return false;
}
//直到最后，说明该数据是存在的，返回true
return true;
}2.3.3?布隆过滤器的删除
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
2.3.4 整体代码
namespace zyl
{
struct BKDRHash
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto ch : key)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
struct APHash
{
size_t operator()(const string& key)
{
unsigned int hash = 0;
int i = 0;
for (auto ch : key)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
}
++i;
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& key)
{
unsigned int hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N,
size_t X = 5,
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
//通过不同的哈希函数，让同一个数据可以计算出三个不同的位置
size_t hash1 = HashFunc1()(key) % (N * X);
size_t hash2 = HashFunc2()(key) % (N * X);
size_t hash3 = HashFunc3()(key) % (N * X);
//计算出位置后，使用位图的set方法将位图上对应的比特位进行0变1
_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
}
bool test(cost K& key)
{
//先逐个位置判断，如果它是0，直接返回false
size_t hash1 = HashFunc1()(key) % (N * X);
if (!_bs.test(hash1))
{
return false;
}
size_t hash2 = HashFunc2()(key) % (N * X);
if (!_bs.test(hash2))
{
return false;
}
size_t hash3 = HashFunc3()(key) % (N * X);
if (!_bs.test(hash3))
{
return false;
}
//直到最后，说明该数据是存在的，返回true
return true;
}
private:
std::bitset<N* X> _bs;
};
}三、海量数据处理
3.1 哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
超过100G大小的文件，肯定不能直接放到内存中，而是通过将它切割，分成很多份。那么如何去切割呢？是平均分成100份，每一份1G？
如果平均切割，那么会导致的问题是：如果文件中有好几个相同的值，且分布不集中，此时平均切割就很可能使一个IP有很多份在很多小文件中。
因此不能平均切割，需要的是哈希切割。哈希切割就是通过取模，让取模结果相同的数据放到同一份小文件里面。
哈希切割后，通过map来对每一个小文件进行统计
如果小文件超过一个G呢？
不管什么情况上来先遍历子文件内容，将每个内容构造成键值对插入到map里面，如果map存不下，则在插入的过程中会出现内存不够的情况，insert会报错，那其实就是new结点失败，new失败是会抛异常的，我们只要捕获这个异常即可，此时说明这个子文件中大多是不同的IP，那么只需要递归哈希切分这个子文件即可。
如果map能够存的下，则正常统计出 出现次数最多的IP即可，无须进行其他任何操作。
3.2 位图应用
3.2.1. 给定100亿个整数，设计算法找到只出现一次的整数？
使用两个位图，分别记录每个整数出现的次数，如果出现0次，则两个位图都为0；
如果出现1次，则第一个位图为0，第二个位图为1。
俩次或两次以上 的为 第一个位图为1，第二个位图为1。
插入好后，去寻找 01 即可
3.2.2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
思路1：先将一个文件的数据映射到位图中，然后用另外一个文件的数据去遍历，得到交集，需要注意去重。
思路2：分布将两文件映射到两个位图，然后通过两位图的与运算判断是否有交集。
3.2.3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
这道问题跟第一个问题基本一样，就是让“01”（出现一次）和"10"（出现俩次）为需要找到的整数。如果出现"11"以上，那么就不行。
3.3 布隆过滤器
3.3.1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
精确算法：可以使用哈希切割的方法，将两个文件按照query的哈希值分割成若干个小文件，使得每个小文件的大小不超过内存限制。然后对每一对小文件，用散列表或者排序的方法找出其中的交集。最后将所有小文件的交集合并起来，就得到了两个大文件的交集。
近似算法：可以使用布隆过滤器的方法，先将一个文件中的所有query插入到一个布隆过滤器中，然后遍历另一个文件中的query，用布隆过滤器检查是否可能存在于第一个文件中。如果可能存在，则加入到候选集合中。最后再对候选集合进行一次精确匹配，就得到了两个大文件的近似交集。
3.3.2如何扩展BloomFilter使得它支持删除元素的操作
使用计数型布隆过滤器，即在每个位数组位置上不再存储一个比特位，而是存储一个计数器。当插入一个元素时，将其映射到的位数组位置上的计数器加一；当删除一个元素时，将其映射到的位数组位置上的计数器减一。这样就可以实现删除操作，但是会增加空间开销和计算复杂度 。
使用双重布隆过滤器，即维护两个布隆过滤器，一个用于存储插入的元素（A），一个用于存储删除的元素（B）。当插入一个元素时，将其加入到A中；当删除一个元素时，将其加入到B中。当查询一个元素时，先检查它是否在A中，如果不在，则认为不存在；如果在，则再检查它是否在B中，如果在，则认为已经删除；如果不在，则认为存在。这样也可以实现删除操作，但是会增加误判率和维护成本
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！