空间设计网站,seo技术培训东莞,福州微信网站制作,建设银行网网站目录
一#xff0c;位图
1. 位图概念
2.实现
3. 测试题
位图的优缺点
二#xff0c;布隆过滤器
1). 布隆过滤器提出
2). 概念
3). 布隆过滤器的查找
4). 布隆过滤器删除(了解)
5). 布隆过滤器优点
6). 布隆过滤器缺陷
三#xff0c;海量数据面试题
1#xff…
目录
一位图
1. 位图概念
2.实现
3. 测试题
位图的优缺点
二布隆过滤器
1). 布隆过滤器提出
2). 概念
3). 布隆过滤器的查找
4). 布隆过滤器删除(了解)
5). 布隆过滤器优点
6). 布隆过滤器缺陷
三海量数据面试题
1哈希切割 一位图
我们首先由一道面试题来理解位图 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中。【腾讯】 1. 遍历时间复杂度O(N) 2. 排序(O(NlogN))利用二分查找: logN 3. 位图解决 数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0 代表不存在。比如 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防止有越界}// 映射的比特位设置为1void set(size_t x){size_t spa_bit x / 8;size_t in_bit x % 8;_bit[spa_bit] (1 in_bit);}// 映射的比特位设置为0void 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:vectorchar _bit;
};
测试案例 再回到题目我们知道有40亿个数我们知道这只是数量不是范围所以我们尽量开到无符号的最大值在开大小的时候我们可以这么来设置 bitset-1 st 或者 bitset0xffffffff st; 3. 测试题 1. 给定100亿个整数设计算法找到只出现一次的整数 思路用两个位图存储 用 00, 01, 10表示0次1次两次及两次这三种情况。 位图一储存第一位 位图二储存第二位 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:// 我们用 010010 表示三种情况bitsetN st1; // 记录第一位 bitsetN st2; // 记录第二位
};2. 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 方法一 两个文件用两个位图存储然后依次比较两个位图之间42亿次数据即可。 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:bitsetN st1;bitsetN st2;
}; 方法二 用一个位图存储一个文件的整数然后用第二个文件的数据来查找位图如果位图中存在则是交集同时查找完了的设置为0即可防止重复输出交集。 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:bitsetN st;
}; 3. 位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 思想还是用2个位图用 00 , 01, 10, 11 表示这四种状态跟第1题类似。 位图的优缺点
优点速度快节省空间。 缺点只映射整型像浮点数string等类不能作为存储进行映射。 二布隆过滤器
1). 布隆过滤器提出
我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉 那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查找呢 1. 用哈希表存储用户记录缺点浪费空间 2. 用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。 3. 将哈希与位图结合即布隆过滤器。 2). 概念 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的 概 率型数据结构特点是 高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存 在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式 不仅可以提升查询效率也 可以节省大量的内存空间。 哈希的详细知识点请查看本篇文章 详解布隆过滤器的原理使用场景和注意事项 - 知乎 (zhihu.com) 上面博客里面的这张图也展示其中效率与哈希函数个数的关系 使用布隆过滤器优点之一是节省空间。虽然哈希函数个数越多冲突的概率越低但占用的平均内存也会提高 然后就是当我们的哈希函数为3时过滤器的长度与插入个数的关系。K是哈希函数个数m是长度n是插入个数 根据里面提供的关系可以得出 布隆过滤器长度应是插入个数的 5 倍 3). 布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找 分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。 4). 布隆过滤器删除(了解) 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。 缺陷 1. 无法确认元素是否真正在布隆过滤器中 2. 存在计数回绕 关于哈希函数的选择我们参考这篇大佬hash函数算法博客的推荐各种字符串Hash函数 - clq - 博客园 (cnblogs.com)
// 三个哈希函数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). 布隆过滤器优点
1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关。 2. 哈希函数相互之间没有关系方便硬件并行运算。 3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势。 4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势。 5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能。 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。 6). 布隆过滤器缺陷
1. 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中。(补救方法再建立一个白名单存储可能会误判的数据) 2. 不能获取元素本身。 3. 一般情况下不能从布隆过滤器中删除元素。 4. 如果采用计数方式删除可能会存在计数回绕问题。 三海量数据面试题
1哈希切割 例1. 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法 精确算法 分析query可以理解为一个字符串100亿个字符串假设一个query的平均长度为50byte, 也就是差不多5000亿byte500G每个文件装入内存是不可能的。我们采取的方法是 1. 分成多份 。 将这500G的数据进行切割分成多份(本题我们分成1000份) 2. 两个文件中的每个query经过相同的哈希函数处理进入1000份中的其中一个文件。 3. 在经过1000次比较两组文件中相对应的数据把结果填入一个文件中即可。 但我们在真正实现的时候又会出现各种各样的问题比如, 这两个大问题。 无法保证每个文件的大小。 我们预计每个小文件500MB左右但有时一个数据多重复因此会 假设B3被分到了3G我们需要进行对B3进行再次切割但B3的状况我们会遇见两种 1. B3有一种query大量重复无法进行切割。 2. B3中有大量不同可以切割。 解决方案 直接使用unordered_set/ set 来插入目标小文件。 如果插入2.5G的内存一定会报内存不足的问题而这个就是 情况2出现这个我们可以更换哈希函数对小文件进行再次进行切割。 如果插入2.5G的内存没有内容不足的问题那么就是情况1。 例2给一个超过100G大小的log file, log中存着IP地址, 只有1G的内存设计算法找到出现次数最多的IP地址 本题跟上一题类似 1. 我们先将100G文件分成多份假设分成100份然后通过哈希函数进行分类写入小文件中。 2. 将小文件写入map / unordered_map中如果写入成功则选出出现最多的id其余的数据clear。如果写入不成功小文件过大则换哈希函数再次切割重复步骤2。 3. 到最后map中留下的数据插入vector进行排序即可。 下期预告 C11 结语 本小节就到这里了感谢小伙伴的浏览如果有什么建议欢迎在评论区评论如果给小伙伴带来一些收获请留下你的小赞你的点赞和关注将会成为博主创作的动力。
