【C++】哈希应用——海量数据面试题

哈希应用——海量数据面试题

  • 一、位图应用
    • 1、给定100亿个整数,设计算法找到只出现一次的整数?
    • 2、给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
      • (1)用一个位图(512MB)
      • (2)用两个位图(1GB)
    • 3、位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
  • 二、哈希切割
  • 三、布隆过滤器
    • 1、给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
    • 2、如何扩展BloomFilter使得它支持删除元素的操作


一、位图应用

1、给定100亿个整数,设计算法找到只出现一次的整数?

我们描述状态有三种,分别是:
1、出现0次
2、出现1次
3、出现2次及以上

我们了解到,如果只有一个位图,那么状态就只有0和1两种状态,所以我们如果想要描述上面的三种状态的话,那么我们就需要开辟两个位图进行存储这三种情况,其第一个位和第二个位的组合进行分析出这三种情况。

这三种情况分别是:00->01->10,此时当我们读取到重复的整数时,就可以让其对应的两个位按照00→01→10的顺序进行变化,最后状态是01的整数就是只出现一次的整数。

#include<iostream>
#include<vector>
#include<assert.h>
#include<bitset>
using namespace std;int main()
{// 此处应该从文件中读取100亿个整数vector<int> v{ 12, 8, 13, 2, 8, 1, 2, 3, 3, 12, 43, 77 };// 堆上申请空间// 申请两个位图bitset<4294967295>* bs1 = new bitset<4294967295>;bitset<4294967295>* bs2 = new bitset<4294967295>;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亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

这个与第一道题目大差不差,我们直接进行更改一下就可以进行书写了:

#include<iostream>
#include<vector>
#include<assert.h>
#include<bitset>
using namespace std;int main()
{// 此处应该从文件中读取100亿个整数vector<int> v{ 12, 8, 13, 2, 8, 1, 2, 3, 3, 12, 43, 77 };// 堆上申请空间// 申请两个位图bitset<4294967295>* bs1 = new bitset<4294967295>;bitset<4294967295>* bs2 = new bitset<4294967295>;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地址转换成一个整型 i(0 ≤ 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个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/168113.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Node.js与npm版本比对

Node.js与npm版本比对 Node.js与npm版本比对版本对比表Node版本对比 Node.js与npm版本比对 我们在项目开发过程中&#xff0c;经常会遇到公司一些老的前端工程项目&#xff0c;而我们当前的node及npm版本都是相对比较新的了。 在运行以前工程时&#xff0c;会遇到相关环境不匹…

浅谈uniapp中开发安卓原生插件

其实官方文档介绍的比较清楚而且详细,但是有时候他太墨迹,你一下子找不到自己想要的,所以我总结了一下开发的提纲,也是为了自己方便下次使用。 1.第一步,下载官方提供的Android的示例工程,然后倒入UniPlugin-Hello-AS工程请在App离线SDK中查找,之后Android studio,编译运行项目…

不会用PS抠图?教你懒人抠图法,必须学会!

相信很多小伙伴都有遇到这样的窘境——好不容易找到得素材图片&#xff0c;中间的图案很好看&#xff0c;可是特别想去掉后面的背景&#xff0c;应该如何抠图呢&#xff1f; 能够将图片中的物品或人物抠出来是一种很有用的技巧&#xff0c;可以在很多场景下应用&#xff0c;比…

MySQL -- 环境安装(CentOS7)

MySQL – 环境安装&#xff08;CentOS7&#xff09; 文章目录 MySQL -- 环境安装&#xff08;CentOS7&#xff09;一、环境安装1.卸载不必要的环境2.检查系统安装包3.卸载默认安装包4.获取MySQL官方yum源6.看看yum源能不能正常工作7.安装mysql服务 二、MySQL登录与配置1.启动My…

论文阅读 - Coordinated Behavior on Social Media in 2019 UK General Election

论文链接&#xff1a; https://arxiv.org/abs/2008.08370 目录 摘要&#xff1a; Introduction Contributions Related Work Dataset Method Overview Surfacing Coordination in 2019 UK GE Analysis of Coordinated Behaviors 摘要&#xff1a; 协调的在线行为是信息…

造车先做三蹦子220101--机器学习字符(字母、和数字识别)的“小白鼠”与“果蝇”

“0”数字字符零 的图片(16*16点阵)&#xff1a; #Letter23Digital23R231006d.pyimport torch import torch.nn as nn import torch.optim as optim #optimizer optim.SGD(model.parameters(), lr0.01) from PIL import Image from PIL import ImageDraw from PIL import Im…

取证之查看本机保存的WiFi密码

一、电脑保存有WiFi密码&#xff0c;且正常连接该WiFi 1、打开网络适配器高级选项 2、双击无线网卡&#xff0c;选择无线属性 3、点击安全&#xff0c;显示字符&#xff0c;即可看到WiFi密码。 二、电脑保存有密码&#xff0c;但是没有链接WiFi。 1、查看wlan接口上的配置文件…

OSPF的网络类型

1.3配置OSPF的网络类型 1.3.1实验3&#xff1a;配置P2P网络类型 实验需求 实现单区域OSPF的配置实现通过display命令查看OSPF的网络类型 实验拓扑 实验拓扑如图1-11所示 图1-11 配置P2P网络类型 实验步骤 步骤1&#xff1a;[1] 配置IP地址 路由器R1[2] 的配置 <Huawe…

【鸿蒙软件开发】文本显示(Text/Span)

文章目录 前言一、Text控件1.1 创建文本string字符串引用Resource资源 1.2 添加子组件创建Span文本装饰线和样式文本装饰线设置文字一直保持大写/小写添加事件。 1.3 自定义文本样式文本对齐长文本处理设置行高通过decoration属性设置文本装饰线样式及其颜色。通过baselineOffs…

Excel·VBA制作工资条

看到一篇博客《excel表头_Excel工资表怎么做&#xff1f;3分钟学会利用函数生成工资表》&#xff0c;使用排序功能、函数制作工资条。但如果需要经常制作工资条&#xff0c;显然使用VBA更加方便 VBA制作工资条 Sub 制作工资条()Dim title_row&, blank_row&, ws_new$,…

在 Python 中使用 Pillow 进行图像处理【3/4】

第三部分 一、腐蚀和膨胀 您可以查看名为 的图像文件dot_and_hole.jpg&#xff0c;您可以从本教程链接的存储库中下载该文件&#xff1a; 该二值图像的左侧显示黑色背景上的白点&#xff0c;而右侧显示纯白色部分中的黑洞。 侵蚀是从图像边界去除白色像素的过程。您可以通过使用…

【CANoe】文件处理_hex文件读取解析

hex文件里面只有00&#xff0c;01&#xff0c;04三种码。那么我们在解析的时候只需要对这三种不同状态的进行不同的解析即可。 hex文件格式的解析&#xff0c;可阅读&#xff1a;HEX文件格式详解 首先创建一个Block的结构体&#xff0c;根据经验我们知道&#xff0c;一个数据…

如何使用vim粘贴鼠标复制的内容

文章目录 一、使用步骤1.找到要编辑的配置文件2.找到目标文件3.再回到vim编辑器 一、使用步骤 1.找到要编辑的配置文件 用sudo vim /etc/apt/sources.list编辑软件源配置文件 sudo vim /etc/apt/sources.listvim 在默认的情况下当鼠标选中的时候进入的 Visual 模式&#xff…

开源WAF--Safeline(雷池)测试手册

长亭科技—雷池(SafeLine)社区版 官方网站:长亭雷池 WAF 社区版 (chaitin.cn) WAF 工作在应用层&#xff0c;对基于 HTTP/HTTPS 协议的 Web 系统有着更好的防护效果&#xff0c;使其免于受到黑客的攻击 1.1 雷池的搭建 1.1.1 配置需求 操作系统&#xff1a;Linux 指令架构&am…

【数据分享】2023年我国科技型中小企业数据(免费获取/Excel格式/Shp格式)

企业是经济活动的参与主体&#xff0c;一个城市的企业数量决定了这个城市的经济发展水平&#xff01;之前我们分享过2023年高新技术企业数据&#xff08;可查看之前的文章获悉详情&#xff09;&#xff0c;我国专精特新“小巨人”企业数据&#xff08;可查看之前的文章获悉详情…

基于SpringBoot的学生班级考勤管理系统

基于SpringBootVue的学生班级考勤管理系统的设计与实现~ 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatisVue工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 管理员界面 课程管理 班级管理 学生管理 学生界面 考勤管理 摘要 学生…

zzy-project-cli,提供多个框架的脚手架

npm地址 install npm install zzy-project-cli -g做什么&#xff1f; 将多个可选的框架提供给使用者选择&#xff0c;选中后自动下载对应模板&#xff0c;快捷使用。 使用 step1 zzy-cli create [项目名称]step2 获取模板之后选取任一进行下载 下载完成之后即可使用 模…

2023/10/23学习记录

1.VS2019中sln对应解决方案 修改sln的文件名&#xff0c;对应的解决方案名称也会变化。 2.如何修改生成的exe文件名呢&#xff1f; 属性--->杂项--->&#xff08;名称) 3.这是任务管理器&#xff0c;这里红色部分显示的是“这是文件描述”。 当通过属性查看详细信息的时…

二叉树题目:最大二叉树

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;最大二叉树 出处&#xff1a;654. 最大二叉树 难度 5 级 题目描述 要求 给定一个没有重复元素的整数数组 num…

快速拿下 AI Prompt 工程师证书攻略!

Datawhale干货 贡献者&#xff1a;许文豪、司玉鑫、甘元琦 Prompt 是 AI 2.0 时代打开大模型能力的金钥匙&#xff0c;它能够大大的提高工作效率。 如果把大语言模型 (LLM&#xff0c;Large Language Model) 具象成一个的员工&#xff0c;那 Prompt 提示词则好比是你给员工下的…