✍作者:阿润菜菜
📖专栏:C++
前言
题目
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
大多数人上来会想到这两种方法:1. 遍历,时间复杂度O(N)2. 排序(O(NlogN)),利用二分查找: logN
但是第一种效率太低了,需要一个一个遍历比对,第二种排序内存无法装得下40亿个整数数据啊!
可以发现问题是需要判断此无符号整数在不在集合中,我们可以用一个数对应一个比特位来标识,42亿个数据换算比特位进行存储,也就是需要0.5GB,512MB内存申请是没有压力的。
下面来学习一下位图法以及相关应用面试题和布隆过滤器知识。
一 位图
1.位图法介绍
位图法是一种利用每一位来存放某种状态的数据结构,适用于大规模数据的快速查找、判重、排序等。在位图法中,一个int类型的数据占用4个字节,即32个bit位,可以表示0-31的数是否存在。
位图申请内存
在内存中我们肯定是不能按照bit位来申请内存的,这不符合内存管理的机制,最小申请的内存也是1byte(字节),即8个bit位。所以在位图里面我们就开出来一个个的char,用每个char的比特位来直接对应数字。
意思是,在位图中,我们不能单独申请一个bit位来存放一个数字的状态,而是要申请一个char类型的数据,即8个bit位,然后用这8个bit位来表示8个数字是否存在。比如,如果我们要表示数字0-7是否存在,我们就可以申请一个char类型的数据a,然后用a的每一位来对应一个数字。如果a的第0位为1,表示数字0存在;如果a的第1位为1,表示数字1存在;以此类推。
2.位图实现的细节
我们这里讲解位图的三个主要功能函数:
- set():置位函数,将指定的位设置为1
- reset():复位函数,将指定位设置为0
- test(): 访问函数,获取指定的位的值
- 对于set,想要让某一比特位变为1其他位不变,则可以用1按位或对应的比特位,那就只需让1向高位移动j位,然后用位图中对应的char进行按位或等即可。
这句话的意思是,如果我们想要把一个char类型的数据a的第j位设置为1,我们可以先把1左移j位,得到一个只有第j位为1其他位为0的数b,然后把a和b进行按位或运算,得到一个新的数c,这个数c就是把a的第j位设置为1后的结果。因为按位或运算的规则是,只要有一个为1就为1,所以a的其他位不会被改变,只有第j位会被设置为1。
例如,如果我们想要把a=0010 1000的第3位设置为1,我们可以先把1左移2位,得到b=0000 0100,然后把a和b进行按位或运算,得到c=0010 1000 | 0000 0100 = 0010 1100,这个数c就是把a的第2位设置为1后的结果。
-
对于reset,想要让某一比特位变为0其他位不变,则可以用0按位与对应的比特位,那就只需让1向高位移动j位,然后按位取反,最后用位图中对应的char进行按位与等即可。
-
对于test,我们可以让对应比特位按位与1,其他比特位按位与0,这样其他比特位都是0,如果测试的比特位是1,则结果是非0,那就是true,如果测试的比特位是0,则结果是0,那就是false。
// 非类型模板参数
template <size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
//可能开的比特位恰好满足数字的个数,也可能最多浪费7个比特位
//_bits.resize(N << 3 + 1, 0);//位运算符优先级过低,这里先进行+运算,则结果和我们预想的不一致,发生错误。
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= 1 << j;
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);//这里不是&=,因为test不改变位图,只是判断一下而已
//有些编译器bool值是四个字节,返回时会发生整型提升,高位补符号位,但这些都不重要,只要是非0就行,判断为真
//我的编译器bool值是一个字节
}
private:
vector<char> _bits;
};
位图的应用
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
二、布隆过滤器
1.布隆过滤器概念
布隆过滤器是一种概率型数据结构,可以用于判断一个元素是否可能存在于一个集合中,其优点是空间效率高,查询速度快,缺点是有一定的误判率和删除困难。
将哈希与位图结合,即布隆过滤器
布隆过滤器的应用场景有:
- 解决缓存穿透问题,即避免频繁查询数据库中不存在的数据
- 邮件过滤,即用布隆过滤器来存储黑名单邮件地址,过滤掉垃圾邮件
- 网页爬虫,即用布隆过滤器来记录已经爬取过的网址,避免重复爬取
- 新闻推荐,即用布隆过滤器来记录用户已经浏览过的新闻,避免重复推荐
2.布隆过滤器实现
布隆过滤器的原理是:
- 创建一个二进制位数组(bitmap)和一组哈希函数
- 当要添加一个元素时,用哈希函数计算出该元素在位数组中的多个位置,并将这些位置的值设为1
- 当要查询一个元素时,用哈希函数计算出该元素在位数组中的多个位置,并检查这些位置的值是否都为1,如果都为1,则认为该元素可能存在;如果有任何一个位置为0,则认为该元素一定不存在
- 当要删除一个元素时,无法直接将位数组中的对应位置设为0,因为这样可能会影响其他元素的判断,所以需要使用一些变形的布隆过滤器来支持删除操作
布隆过滤器的删除
如果采用计数方式来实现reset,也就是布隆过滤器的删除,会存在一些问题。比如你不小心将某一个字符串多次重复删除,此时计数会进行- -,但如果是0- -呢?有可能还会发生越界访问等问题。所以计数方式也有他的缺陷,最好不要强制增加布隆过滤器的reset操作。
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;
}
};
struct JSHash
{
size_t operator()(const string& s)
{
size_t hash = 1315423911;
for (auto ch : s)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
};
//布隆过滤器不仅可以存字符串,也可以存其他类型,只要最后能转换成整型完成取模映射就行,取模是比较常用的哈希函数
//平均存储一个值,开辟X个比特位
template <size_t N, size_t X = 8, class K = string,
class Hashfunc1 = BKDRHash, class Hashfunc2 = APHash, class Hashfunc3 = DJBHash, class Hashfunc4 = JSHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t hash1 = Hashfunc1()(key) % (X * N);
size_t hash2 = Hashfunc2()(key) % (X * N);
size_t hash3 = Hashfunc3()(key) % (X * N);
size_t hash4 = Hashfunc4()(key) % (X * N);
_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
_bs.set(hash4);
}
bool test(const K& key)
{
size_t hash1 = Hashfunc1()(key) % (X * N);
if (!_bs.test(hash1))
{
return false;
}
size_t hash2 = Hashfunc2()(key) % (X * N);
if (!_bs.test(hash2))
{
return false;
}
size_t hash3 = Hashfunc3()(key) % (X * N);
if (!_bs.test(hash3))
{
return false;
}
size_t hash4 = Hashfunc4()(key) % (X * N);
if (!_bs.test(hash4))
{
return false;
}
//上面判断不在的情况一定是准确的。
return true;//这里可能会存在误判,多个哈希位置都和别的字符串冲突了
}
private:
std::bitset<N * X> _bs;//如果size_t类型×X过后,size_t类型存不下,也可以选择换long long类型
};
三、海量数据处理
1. 位图应用
经典面试题及解决方案:
1. 给定一个文件,包含40亿个不重复的无符号整数,给一个无符号整数,如何快速判断这个数是否在文件中?
解决方案:使用一个40亿位的位图,将文件中的每个整数映射到位图中,然后根据给定的整数在位图中查找即可。
2. 给定两个文件,分别包含100亿个整数,只有1G内存,如何找到两个文件的交集?
解决方案:使用哈希切分的方法,将两个文件分别按照哈希函数分成1000个小文件,然后对每一对小文件求交集即可。
3. 给定一个文件,包含100亿个整数,只有1G内存,设计算法找到出现次数不超过2次的所有整数?
解决方案:使用两个位图,分别记录每个整数出现的次数,如果出现0次,则两个位图都为0;如果出现1次,则第一个位图为1,第二个位图为0;如果出现2次或以上,则第一个位图为0,第二个位图为1。最后遍历两个位图,找出第一个位图为1且第二个位图为0的位置即可。
2. 哈希切割
问题
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?
因为问题是100G大小的文件,肯定是无法加载到内存解决的,传统的KV模型如map来是不能解决的,我们这里采用哈希切割的思想来解决此问题。
哈希切割是一种将一个大文件利用哈希的原理,将其分割为若干个小文件的方法,相同数据分到同一个文件。
一种解决方案是:
上来先遍历子文件内容,将每个内容构造成键值对插入到map里面,如果map存不下,则在插入的过程中会出现内存不够的情况,insert会报错,那其实就是new结点失败,new失败是会抛异常的,我们只要捕获这个异常即可,此时说明这个子文件中大多是不同的IP,那么只需要递归哈希切分这个子文件即可。
如果map能够存的下,则正常统计出 出现次数最多的IP即可,无须进行其他任何操作。
3. 布隆过滤器
- 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法。
-
精确算法:可以使用哈希切割的方法,将两个文件按照query的哈希值分割成若干个小文件,使得每个小文件的大小不超过内存限制。然后对每一对小文件,用散列表或者排序的方法找出其中的交集。最后将所有小文件的交集合并起来,就得到了两个大文件的交集。
- -
近似算法:可以使用布隆过滤器的方法,先将一个文件中的所有query插入到一个布隆过滤器中,然后遍历另一个文件中的query,用布隆过滤器检查是否可能存在于第一个文件中。如果可能存在,则加入到候选集合中。最后再对候选集合进行一次精确匹配,就得到了两个大文件的近似交集。文章来源:https://www.toymoban.com/news/detail-461158.html
- 如何扩展BloomFilter使得它支持删除元素的操作?
- 一种方法是使用计数型布隆过滤器,即在每个位数组位置上不再存储一个比特位,而是存储一个计数器。当插入一个元素时,将其映射到的位数组位置上的计数器加一;当删除一个元素时,将其映射到的位数组位置上的计数器减一。这样就可以实现删除操作,但是会增加空间开销和计算复杂度 。
- 另一种方法是使用双重布隆过滤器,即维护两个布隆过滤器,一个用于存储插入的元素(A),一个用于存储删除的元素(B)。当插入一个元素时,将其加入到A中;当删除一个元素时,将其加入到B中。当查询一个元素时,先检查它是否在A中,如果不在,则认为不存在;如果在,则再检查它是否在B中,如果在,则认为已经删除;如果不在,则认为存在。这样也可以实现删除操作,但是会增加误判率和维护成本 。
结束文章来源地址https://www.toymoban.com/news/detail-461158.html
到了这里,关于【C++】位图/布隆过滤器+海量数据处理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!