网站静态页模板,做网站jijianjianzhan,python基础教程资料,成都哪家网站建设哈希应用——海量数据面试题 一、位图应用1、给定100亿个整数#xff0c;设计算法找到只出现一次的整数#xff1f;2、给两个文件#xff0c;分别有100亿个整数#xff0c;我们只有1G内存#xff0c;如何找到两个文件交集#xff1f;#xff08;1#xff09;用一个位图… 哈希应用——海量数据面试题 一、位图应用1、给定100亿个整数设计算法找到只出现一次的整数2、给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集1用一个位图512MB2用两个位图1GB 3、位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 二、哈希切割三、布隆过滤器1、给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法2、如何扩展BloomFilter使得它支持删除元素的操作 一、位图应用
1、给定100亿个整数设计算法找到只出现一次的整数
我们描述状态有三种分别是 1、出现0次 2、出现1次 3、出现2次及以上
我们了解到如果只有一个位图那么状态就只有0和1两种状态所以我们如果想要描述上面的三种状态的话那么我们就需要开辟两个位图进行存储这三种情况其第一个位和第二个位的组合进行分析出这三种情况。
这三种情况分别是00-01-10此时当我们读取到重复的整数时就可以让其对应的两个位按照00→01→10的顺序进行变化最后状态是01的整数就是只出现一次的整数。
#includeiostream
#includevector
#includeassert.h
#includebitset
using namespace std;int main()
{// 此处应该从文件中读取100亿个整数vectorint v{ 12, 8, 13, 2, 8, 1, 2, 3, 3, 12, 43, 77 };// 堆上申请空间// 申请两个位图bitset4294967295* bs1 new bitset4294967295;bitset4294967295* bs2 new bitset4294967295;for (auto e : v){if (!bs1-test(e) !bs2-test(e)) // 00-01{bs2-set(e);}else if (!bs1-test(e) bs2-test(e)) // 01-10{bs1-set(e);bs2-reset(e);}else if (bs1-test(e) !bs2-test(e)) // 10-10{// 不做任何处理}else{assert(false);}}for (size_t i 0; i 4294967295; i){// 打印01if (!bs1-test(i) bs2-test(i)){cout i ;}}cout endl;return 0;
}注意点如果我们存储100亿个整数的话在堆中需要申请大约40个G的空间这个空间是非常大的而我们利用位图来解决这个问题的时候我们就只需要512MB也就是代码中的4294967295两个位图才只需要1个G的空间。
2、给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集
1用一个位图512MB
方法是依次读取文件中的整数的值将其映射到一个位图中再读取另一个文件中的所有整数判断在不在位图中在就是交集不在就不是交集。
2用两个位图1GB
依次读取第一个文件中的所有整数将其映射到位图1。依次读取另一个文件中的所有整数将其映射到位图2。将位图1和位图2进行与操作结果存储在位图1中此时位图1当中映射的整数就是两个文件的交集。
3、位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数
这个与第一道题目大差不差我们直接进行更改一下就可以进行书写了
#includeiostream
#includevector
#includeassert.h
#includebitset
using namespace std;int main()
{// 此处应该从文件中读取100亿个整数vectorint v{ 12, 8, 13, 2, 8, 1, 2, 3, 3, 12, 43, 77 };// 堆上申请空间// 申请两个位图bitset4294967295* bs1 new bitset4294967295;bitset4294967295* bs2 new bitset4294967295;for (auto e : v){if (!bs1-test(e) !bs2-test(e)) // 00-01{bs2-set(e);}else if (!bs1-test(e) bs2-test(e)) // 01-10{bs1-set(e);bs2-reset(e);}else if (bs1-test(e) !bs2-test(e)) // 10-10{// 不做任何处理}else{assert(false);}}for (size_t i 0; i 4294967295; i){// 打印01和10if ((!bs1-test(i) bs2-test(i)) || ((bs1-test(i) !(bs2-test(i))))){cout i ;}}cout endl;return 0;
}
二、哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址与上题条件相同如何找到top K的IP如何直接用Linux系统命令实现
1、我们将这个log file叫做A文件由于A文件的大小超过100G这里可以考虑将A文件切分成200个小文件。 2、在切分时选择一个哈希函数进行哈希切分通过哈希函数将A文件中的每个IP地址转换成一个整型 i0 ≤ i ≤ 199然后将这个IP地址写入到小文件Ai当中。 3、由于哈希切分时使用的是同一个哈希函数因此相同的IP地址计算出的 i i值是相同的最终这些相同的IP地址就会进入到同一个Ai小文件当中。 经过哈希切分后得到的这些小文件理论上就能够加载到内存当中了如果个别小文件仍然太大那可以对其再进行一次哈希切分总之让最后切分出来的小文件能够加载到内存。
我们用sort log_file | uniq -c | sort -nrk1,1 | head -K命令选取出现次数top K的IP地址。 利用sort进行排序。
利用uniq统计出现次数。
-nrk1进行反向排序。 前两个。
三、布隆过滤器
1、给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法
先读取其中一个文件当中的query将其全部映射到一个布隆过滤器当中。然后读取另一个文件当中的query依次判断每个query是否在布隆过滤器当中如果在则是交集不在则不是交集。
2、如何扩展BloomFilter使得它支持删除元素的操作
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 如上图如果我们删除“李四”这个数据的话那么三个1都要置0则导致张三有俩置0了那张三的数据岂不是很奇怪
一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。
