中山手机网站建设价格,网站制作的合同,中国国建设监理协会网站,滨州网站建设公司目录 一
二
三
2.单个子文件太大怎么办#xff1f;#xff08;分两种情况讨论#xff09; 一
这样的题目典型就是KV模型的问题#xff0c;即通过key IP找对应的value 出现次数#xff0c;对于KV模型的问题首先想到的就是用map来统计次数#xff0c;但是100G大小的文件…目录 一
二
三
2.单个子文件太大怎么办分两种情况讨论 一
这样的题目典型就是KV模型的问题即通过key IP找对应的value 出现次数对于KV模型的问题首先想到的就是用map来统计次数但是100G大小的文件是无法加载到内存的所以直接用map是不行的。有人可能会想到用位图来解决这里的问题多开几个位图用多个比特位的组合来表示次数这样的想法也是不行的你怎么知道次数最多是几次呢如果出现次数最多是10w次呢你要开多少个位图呢内存够开那么多位图吗所以这样的方式也是不行的。 给一个超过100G大小的log filelog中存着IP地址设计算法找到出现次数最多的IP地址
统计次数最先想到的就是mapKV模型但文件太大用不了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都是重复的IPmap当然是可以存的下的对于大量出现的IP只需要对应的出现次数value即可。
2. 具体实现的方案是这样的上来先遍历子文件内容将每个内容构造成键值对插入到map里面如果map存不下则在插入的过程中会出现内存不够的情况insert会报错那其实就是new结点失败new失败是会抛异常的我们只要捕获这个异常即可此时说明这个子文件中大多是不同的IP那么只需要递归哈希切分这个子文件即可。 如果map能够存的下则正常统计出 出现次数最多的IP即可无须进行其他任何操作。
