目录
一,位图
1. 位图概念
2.实现
3. 测试题
位图的优缺点
二,布隆过滤器
1). 布隆过滤器提出
2). 概念
3). 布隆过滤器的查找
4). 布隆过滤器删除(了解)
5). 布隆过滤器优点
6). 布隆过滤器缺陷
三,海量数据面试题
1)哈希切割
一,位图
我们首先由一道面试题来理解位图
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】
40亿无符号整形,我们知道1G大概是10亿个字节,也就是说起码 16G数据,排序,二分查找都需要在内存下进行,16G的内存性价比着实有些低。而我们使用位图的方法,用40亿个比特位来表示这40亿个数是否存在,大概就是要消耗 512MB(40亿bit == 5亿字节 == 512MB)的内存。
注意:
1. 位图概念
2.实现
#include <iostream>
#include <vector>
using namespace std;
template < size_t N>
class bitset
{
public:
bitset()
{
_bit.resize(N / 8 + 1, 0); // + 1防止有越界
}
// 映射的比特位设置为1
void set(size_t x)
{
size_t spa_bit = x / 8;
size_t in_bit = x % 8;
_bit[spa_bit] &= (1 << in_bit);
}
// 映射的比特位设置为0
void reset(size_t x)
{
size_t spa_bit = x / 8;
size_t in_bit = x % 8;
}
// 测试x,是否存在
bool test(size_t x)
{
size_t spa_bit = x / 8;
size_t in_bit = x % 8;
return _bit[spa_bit] & (1 << in_bit);
// 返回0: 则不存在
// 返回一个很大的数:存在
}
private:
vector<char> _bit;
};
测试案例:
再回到题目,我们知道有40亿个数,我们知道这只是数量,不是范围,所以,我们尽量开到无符号的最大值,在开大小的时候我们可以这么来设置:
bitset<-1> st 或者 bitset<0xffffffff> st;
3. 测试题
template <size_t N>
class two_set
{
public:
void set(size_t x)
{
if (st1.test(x) == false
&& st2.test(x) == false)
{// 00 -> 01 情况
st2.set(x);
}
else if (st1.test(x) == false
&& st2.test(x) == true)
{// 01 -> 10 情况
st1.set(x);
st2.reset(x);
}
}
private:
// 我们用 01,00,10 表示三种情况
bitset<N> st1; // 记录第一位
bitset<N> st2; // 记录第二位
};
template <size_t N>
class cross_set
{
public:
void set1(size_t x)
{
st1.set(x);
}
void set2(size_t x)
{
st2.set(x);
}
void test()
{
for (size_t i = 0; i < N; i++)
{
if (st1.test(i) && st2.test(i))
cout << i << " ";
}
}
private:
bitset<N> st1;
bitset<N> st2;
};
class cross_set2
{
public:
void set(size_t x )
{
st.set(x);
}
void test(size_t x)
{
if (st.test(x))
{
cout << x << " ";
st.reset(x); //第一次检测完后设置为0
}
}
private:
bitset<N> st;
};
思想:还是用2个位图,用 00 , 01, 10, 11 表示这四种状态,跟第1题类似。
位图的优缺点
优点:速度快,节省空间。
缺点:只映射整型,像浮点数,string等类不能作为存储,进行映射。
二,布隆过滤器
1). 布隆过滤器提出
2). 概念
哈希的详细知识点,请查看本篇文章: 详解布隆过滤器的原理,使用场景和注意事项 - 知乎 (zhihu.com)
![哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题),哈希算法,算法,c++,数据结构,面试,开发语言](https://imgs.yssmx.com/Uploads/2023/12/756874-6.png)
使用布隆过滤器,优点之一是节省空间。虽然哈希函数个数越多,冲突的概率越低;但占用的平均内存也会提高
然后就是当我们的哈希函数为3时,过滤器的长度与插入个数的关系。(K是哈希函数个数,m是长度,n是插入个数)
根据里面提供的关系可以得出, 布隆过滤器长度应是插入个数的 5 倍
3). 布隆过滤器的查找
![哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题),哈希算法,算法,c++,数据结构,面试,开发语言](https://imgs.yssmx.com/Uploads/2023/12/756874-8.png)
4). 布隆过滤器删除(了解)
关于哈希函数的选择,我们参考这篇大佬hash函数算法博客的推荐:各种字符串Hash函数 - clq - 博客园 (cnblogs.com)文章来源:https://www.toymoban.com/news/detail-756874.html
// 三个哈希函数
struct APHash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (long i = 0; i < str.size(); i++)
{
size_t ch = str[i];
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
};
struct BKDRHash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto e : str)
{
hash += (size_t)e;
hash *= 31;
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& str)
{
if (!str[0]) // 这是由本人添加,以保证空字符串返回哈希值0
return 0;
size_t hash = 5381;
for (auto e : str)
{
size_t ch = size_t(e);
hash += (hash << 5) + ch;
}
return hash;
}
};
template <size_t N, class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class bloom_set
{
public:
// 插入
void set(const string& str)
{
Hash1 hash1;
size_t len = N * time;
st.set(hash1(str) % len);
Hash2 hash2;
st.set(hash2(str) % len);
Hash3 hash3;
st.set(hash3(str) % len);
}
// 判断是否存在
// 1. 如果其中一个不存在,那么一定不存在
// 2. 如果三位置都存在,那么可能存在,需要确认
bool test(const string& str)
{
Hash1 hash1;
Hash2 hash2;
Hash3 hash3;
size_t len = N * time;
if (!st.test(hash1(str) % len))
return false;
if (!st.test(hash2(str) % len))
return false;
if (!st.test(hash3(str) % len))
return false;
return true; // 都存在,那可能存在
}
private:
static const size_t time = 5; // 过滤器长度与插入个数关系
bitset < N * time > st;
};
5). 布隆过滤器优点
6). 布隆过滤器缺陷
三,海量数据面试题
1)哈希切割
![哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题),哈希算法,算法,c++,数据结构,面试,开发语言](https://imgs.yssmx.com/Uploads/2023/12/756874-9.png)
![哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题),哈希算法,算法,c++,数据结构,面试,开发语言](https://imgs.yssmx.com/Uploads/2023/12/756874-10.png)
1. B3有一种query大量重复,无法进行切割。2. B3中有大量不同,可以切割。
如果插入2.5G的内存,一定会报内存不足的问题,而这个就是 情况2,出现这个我们可以更换哈希函数,对小文件进行再次进行切割。如果插入2.5G的内存,没有内容不足的问题,那么就是情况1。
下期预告: C++11 !!!
结语
本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力。文章来源地址https://www.toymoban.com/news/detail-756874.html
到了这里,关于哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!