@[TOC]

哈希切割及海量数据处理面试题讲解

问题1

1. 给两个文件，分别有100亿个query字符串，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

近似算法：

<font color = "#000066">把一个文件的内容set到布隆过滤器中，然后遍历另一个文件判断在不在，在的就是交集。

精确算法：

首先我们估算一下100亿个字符串大概占多少空间？

<font color = "#000066">那我们要假设一下，假设单个字符串50字节，那100亿个就是5000亿字节，大概就是500G（之前我们算过1G大概10亿字节嘛）。 每个文件500G

那我们肯定要对文件进行切割，因为我们只有1G可用内存。

<font color = "#000066">那我们可以把每个文件切成1000份，然后每份500mb

那大家思考一下，我们这样切分有没有什么问题？

<font color = "#000066">比如我们现在要那A0去跟B找交集，那会有什么问题？ 是不是A0跟B的每一个小文件都可能会有交集啊，那我们找交集的时候每一个小文件都需要跟另一个文件的1000个小文件都找一下交集，这是不是太暴力，效率太低了啊。

所以呢我们可以换一个切割方法：

<font color = "#000066">不再像上面那样平均切割。 那怎么切呢？ <font color = blue>这种方法叫做哈希切割 <font color = "#000066">那它是这样切的： 选择一个哈希函数，把query字符串传过去，算出来一个散列地址i，这个i是几，就把它放到第i个文件里面 那这样切割能达到一个什么效果呢？ 🆗，我们用哈希函数去切割的话，A、B文件中相同的值进入的小文件的文件号一定是一样的（因为它们的值是一样的，用的哈希函数也是一样的，那算出来的i肯定就是一样的）。 那这样的话，我们找交集就不用像之前那样麻烦了，编号相等的小文件找交集就行了。 A0只用和B0找交集就行了，A1和B1，A2和B2，...，依次类推

但是这样切割也会有一个问题就是：

<font color = "#000066">哈希切割的话不是平均切割，那就会导致有的小文件比较小，有的比较大，那就有可能存在有的小文件超过了可用内存1G（那其实就是对应的冲突比较多） 那如果存在这样的文件，即分割之后还是比较大的这种，它其实又分为两种情况： 1.在这单个文件中，存在大量重复的query字符串 2.没什么重复值，大部分都是不同的 那这两种不同的情况，我们的处理方式也是不同的。

那问题来了我们如何去辨别这两种情况呢？

<font color = "#000066">其实也不难，如果出现这种比较大的小文件，我们直接搞一个set/unordered_set，然后把文件里面的query字符串插入进行。 那如果是大量重复值的情况，那往set里面插入的话后面的是不是就会插入失败啊。 所以： 如果整个小文件里面的字符串都可以成功插入到set里面，那就是第一种情况（大量重复值） 如果在插入的过程中抛了内存异常，那就是第二种情况（大部分都是不同的，没什么重复值），因为我们只有1G内存，如果没什么重复值那就都插入成功，然后就会内存不够用，是会抛异常的。 那对于这种情况呢我们就换哈希函数对它再进行切割使它体积变小，在分割的小一点，然后就可以直接找交集了

问题2

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

怎么处理呢？

<font color = "#000066">首先还是使用一个哈希切割，比如这里我们切500份，那这样相同的IP就会进入同一个小文件。 然后我们通过单个小文件就可以统计出它里面存到各个IP出现的次数 那统计次数的话我们可以直接用map/unordered_map 那同样的，如果出现有些划分完的文件比较大：

那找TOP-K的IP呢？

<font color = "#000066">🆗，那TOK-K的问题我们之前二叉树的文章里面是详细讲解过的，这里就不细说了。 那我们就可以建一个K个数的小堆，每个元素存一个pair（key是IP，value是次数），然后遍历后面的IP次数更新这个小堆，最后TOP-K就出来了。