哈希切分

目录

2.单个子文件太大怎么办?(分两种情况讨论)


这样的题目典型就是KV模型的问题,即通过key IP找对应的value 出现次数,对于KV模型的问题首先想到的就是用map来统计次数,但是100G大小的文件是无法加载到内存的,所以直接用map是不行的。有人可能会想到用位图来解决这里的问题,多开几个位图,用多个比特位的组合来表示次数,这样的想法也是不行的,你怎么知道次数最多是几次呢?如果出现次数最多是10w次呢?你要开多少个位图呢?内存够开那么多位图吗?所以这样的方式也是不行的。

给一个超过100G大小的log file,log中存着IP地址,设计算法找到出现次数最多的IP地址?

统计次数最先想到的就是map,KV模型,但文件太大用不了map,文件太大了,无法加载到内存中,位图能解决key的问题,解决不了kv的问题

map不行,我们间接用map


既然直接用map存储无法解决,那就间接用map进行存储KV键值对。切分大文件变成小文件,让小文件中的内容能够加载到内存里面,能够用map存储起来。
首先试想一下,平均切分100G文件可以吗?如果平均切分的话,则某些多次出现的IP可能会被散列到不同的子文件当中,每次内存只能加载一个子文件的内容,此时统计出的最多IP次数在大文件中是最多的吗?这当然是不确定的,所以平均切分的方式万万不可行,因为相同的IP有可能在平均切分的过程中被散列到不同的子文件,则会导致每个子文件中出现次数最多的IP是不可靠的。


在切分文件的这一步中就要用到哈希切分了,我们可以将IP进行字符串哈希算法的转换,将其转换为整型,控制映射的范围为0-99,即用转换为整型后的值去%100,那么相同的IP就一定会映射到同一个文件当中,此时每个子文件就相当于一个冲突哈希桶,里面装着的都是出现多次的IP,当然也有可能是只出现一次的IP,反正这些都不重要,只要出现多次的IP没有散列到不同的子文件,分到相同的子文件即可。
此时每个子文件中出现次数最多的IP的次数和在大文件中出现的次数是相同的,则我们只需要一个字符串对象,存储当前子文件中出现次数最多的IP即可,然后依次遍历后面的子文件,若次数大于上一个文件中出现次数最多的IP,那就更新字符串对象即可

2.单个子文件太大怎么办?(分两种情况讨论)


1.
如果哈希切分后的单个子文件还是太大该怎么办呢?
此时要分为两种情况,如果子文件中冲突的IP大多是不相同的IP,那么map是会统计不下的,此时就需要我们换个字符串hashfunc,递归哈希切分这个子文件,可以改变一下哈希函数中除留余数法,模的大小,但除留余数法还是挺好用的,如果你觉得不太好用,你也可以尝试其他的哈希函数,我个人推荐继续使用除留余数法,改变一下模的大小,再换个hashfunc,重新建立映射关系,递归将这个子文件进行哈希切分,直到map能够统计这个子文件中的IP内容为止。
另一种情况就是,如果子文件中冲突的IP大多是相同的IP,此时虽然文件的大小表面上看来很大,map有可能存不下,但是不要忘了,map是可以去重的呀,虽然你文件很大,但是大多数的IP都是重复的IP,map当然是可以存的下的,对于大量出现的IP只需要++对应的出现次数value即可。

2.
具体实现的方案是这样的,上来先遍历子文件内容,将每个内容构造成键值对插入到map里面,如果map存不下,则在插入的过程中会出现内存不够的情况,insert会报错,那其实就是new结点失败,new失败是会抛异常的,我们只要捕获这个异常即可,此时说明这个子文件中大多是不同的IP,那么只需要递归哈希切分这个子文件即可。
如果map能够存的下,则正常统计出 出现次数最多的IP即可,无须进行其他任何操作。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows11通过SMB映射NAS网络驱动磁盘

环境 NAS:威联通TS-416 操作系统:Windows11 第一步 连接NAS winr 打开运行,输入NAS局域网IP地址,按照如下的格式输入 然后输入NAS的账号和密码就可以通过SMB连接到NAS了 第二步 映射网络驱动器 举个栗子:右键Stora…

【AIGC】Stable Diffusion的模型入门

下载好相关模型文件后,直接放入Stable Diffusion相关目录即可使用,Stable Diffusion 模型就是我们日常所说的大模型,下载后放入**\webui\models\Stable-diffusion**目录,界面上就会展示相应的模型选项,如下图所示。作者…

[GXYCTF2019]禁止套娃

进来发现只有这句话,习惯性访问一下flag.php,发现不是404,那就证明flag就在这了,接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码,githack拿到index.php源码 这里观察到多次判断,首先要…

Unity如何修改预制体(预制件)?

文章目录 19 复制复制复制,预制体与变体 19 复制复制复制,预制体与变体 【预制件】 预制件作用:方便复用 【预制件】的制作 直接拖拽,从层级面板 -> 项目面板。层级面板中当前图标会变蓝,子物体名字变蓝色。预制件…

node+vue3+mysql前后分离开发范式——实现对数据库表的增删改查

文章目录 ⭐前言⭐ 功能设计与实现💖 node后端操作数据库实现增删改查💖 vue3前端实现增删改查⭐ 效果⭐ 总结⭐ 结束⭐结束⭐前言 大家好,我是yma16,本文分享关于 node+vue3+mysql前后分离开发范式——实现对数据库表的增删改查。 技术选型 前端:vite+vue3+antd 后端:…

Javaweb之SpringBootWeb案例之AOP核心概念的详细解析

2.3 AOP核心概念 通过SpringAOP的快速入门,感受了一下AOP面向切面编程的开发方式。下面我们再来学习AOP当中涉及到的一些核心概念。 1. 连接点:JoinPoint,可以被AOP控制的方法(暗含方法执行时的相关信息) 连接点指的…

边缘计算:重塑数字世界的未来

引言 随着物联网(IoT)设备的激增和5G网络的普及,我们正站在一个计算模式的新纪元门槛上——边缘计算。这一技术范式将数据处理和分析推向网络的边缘,即设备或终端,为实时性要求较高的应用提供了前所未有的可能性。 目…

保育员答案怎么查找? #经验分享#微信

在大学生的学习过程中,我们经常会遇到各种难题和疑惑。有时候,我们可能会花费大量的时间和精力去寻找答案,但结果却并不尽如人意。为了帮助大家更好地解决这个问题,今天我要向大家介绍几款备受大学生欢迎的搜题软件,它…

问题:由于环境因素或人为因素干扰,致使土地生态系统的结构和功能失调,引起() #学习方法#经验分享

问题:由于环境因素或人为因素干扰,致使土地生态系统的结构和功能失调,引起() A.土地退化 B.土壤污染 C.生态平衡失调 D.土地沙化 参考答案如图所示

HCIA-HarmonyOS设备开发认证V2.0-轻量系统内核基础-互斥锁mux

目录 一、互斥锁基本概念二、互斥锁运行机制三、互斥锁开发流程四、互斥锁使用说明五、互斥锁接口六、代码分析(待续...) 一、互斥锁基本概念 互斥锁又称互斥型信号量,是一种特殊的二值性信号量,用于实现对共享资源的独占式处理。…

应急响应实战笔记02日志分析篇(3)

第3篇:Web日志分析 ox01 Web日志 Web访问日志记录了Web服务器接收处理请求及运行时错误等各种原始信息。通过对WEB日志进行的安全分析,不仅可以帮助我们定位攻击者,还可以帮助我们还原攻击路径,找到网站存在的安全漏洞并进行修复。 我们来…

问题:从完整的问题解决过程来看,( )是首要环节。A.理解问题 B.提出假设C.发现问题 D.检验假设 #学习方法#学习方法

问题:从完整的问题解决过程来看,( )是首要环节。A.理解问题 B.提出假设C.发现问题 D.检验假设 A.理解问题 B.提出假设 C.发现问题 参考答案如图所示

WebSocket | 基于TCP的全双工通信网络协议

文章目录 1、介绍2、示例2.1、分析2.2、代码开发2.3、功能测试 ​🍃作者介绍:双非本科大三网络工程专业在读,阿里云专家博主,专注于Java领域学习,擅长web应用开发、数据结构和算法,初步涉猎Python人工智能开…

机器学习---HMM前向、后向和维特比算法的计算

1. HMM import numpy as np# In[15]:class HiddenMarkov:def forward(self, Q, V, A, B, O, PI): # 使用前向算法N len(Q) # 状态序列的大小M len(O) # 观测序列的大小alphas np.zeros((N, M)) # alpha值T M # 有几个时刻,有几个观测序列,就有…

智慧职教考试怎么搜题找答案? #微信#其他

下面将介绍一些大学生常用的日常学习辅助工具和资料,希望能为你的学习提供帮助和便利 1.题老大 这个是公众号 内容很丰富,范围包括公考、计算机、建筑工程、会计资格、消防、外语外贸、教师资格! 下方附上一些测试的试题及答案 1、带式输…

[OPEN SQL] 更新数据

UPDATE语句用于更新数据库表中的数据 本次操作使用的数据库表为SCUSTOM&#xff0c;其字段内容如下所示 航班用户(SCUSTOM) 需要操作更新以下数据 1.更新单条数据 语法格式 UPDATE <dbtab> FROM <wa>. UPDATE <dbtab> FROM TABLE <itab>. UPDATE &l…

【机器学习笔记】4 朴素贝叶斯

贝叶斯方法 贝叶斯分类 贝叶斯分类是一类分类算法的总称&#xff0c;这类算法均以贝叶斯定理为基础&#xff0c;故统称为贝叶斯分类。 朴素贝叶斯分类是这一类算法中最简单的较为常见的算法。 先验概率 根据以往经验和分析得到的概率。我们用&#x1d443;(&#x1d44c;)来代…

MySQL 基础知识(六)之数据查询(二)

目录 6 数值型函数 7 字符串函数 8 流程控制函数 9 聚合函数 10 分组查询 (group by) 11 分组过滤 (having) 12 限定查询 (limit) 13 多表查询 13.1 连接条件关键词 (on、using) 13.2 连接算法 13.3 交叉连接 (cross join) 13.4 内连接 (inner join) 13.5 外连接 …

Redis.conf 配置文件解读

1、单位 容量单位不区分大小写&#xff0c;G和GB没有区别 配置文件 unit单位 对大小写不敏感 2、组合配置 可以使用 include 组合多个配置问题 3、网络配置 bind 127.0.0.1 # 绑定的ip protected-mode yes # 保护模式 port 6379 # 端口设置4、通用 GENERAL daemoniz…

第13讲我创建的投票列表实现

新建我创建的投票页面 {"path": "pages/createVoteList/createVoteList","style": {"navigationBarTitleText": "我创建的投票"}}个人中心页面&#xff0c;加下 点击 “我创建的投票”跳转列表页面 goVoteList:function(){u…