海量数据处理问题分析

哈希切割top K问题

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

将100G的log file 哈希切分成1000份，为什么不切成100份
因为100份中不一定每个文件大小都是1G，有的文件可能要
5,6个G的，因为有哈希冲突，可能某个文件哈希冲突多
文件大小要10G左右了，因此哈希切分成1000份，每份100M
这样最多IP大小也就1到2个G，哈希表可以进行处理。
切分时：先把IP字符串转为整型，再取模Ip%1000
进行哈希切分存储。因为相同的IP一定会进入同一个文件
然后1000份中用哈希表KV模型进行统计每个IP的次数
用第一个文件中IP次数和第二个最多IP次数比较，大的保留
小的销毁，依次向后比较，直到统计完1000份中最大的IP次数。
如果某一个文件IP值过多，导致文件过大，可以用不同的哈希
算法进行切分来实现分流。

位图应用

给定100亿个整数，设计算法找到只出现一次的整数

要知道100亿个整数占多少空间，10亿个整数大概占一个G
100亿大概占10个G，但是一百亿个整数，所以要大概占40个G
很明显内存中是存不下的，位图只需要用位来表示一个数在或者
不在，一个字节为8个比特，现在用32个比特位表示，则40G
用位图需要40/32=1.25G,因此我们需要用位图进行操作
一个数字用两位进行表示，需要消耗2.5G，一共三种状态
没有出现'00'表示，出现一次用'01'表示，出现2次出现
用'10'表示，两次以上出现依然保持'10'状态，位图一个整形
可以标记32个数，现在标记16个数，16个数中每个数存储
两个比特位。

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集

方法1.把100亿个整数放在一个位图中，开辟一个位图需要500M
从另一个文件中开始读取遍历，在就是交集，不在就不是
方法2.将两个文件分别放到两个位图中，将两个位图进行与操作
位图中是用数组进行存储，数组中存储的都是0,1整型
将两个位图依次与，1与1为1,1与0为0，与操作后
数组中为1的就是交集，为0的表示没有交集。

1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

与上一个算法类似，操作两个位进行表示所有整数出现的次数
共四种状态，没有出现'00'表示，出现一次用'01'表示
出现2次出现用'10'表示，出现两次以上的用'11'表示

布隆过滤器+哈希切分

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

近似算法：创建一个布隆过滤器，将一个文件所以字符串放入布隆过滤器中，将另一个文件中值依次再布隆过滤器中查找，不在的肯定不在，在的可能在，但在的几率大，因为布隆有误判效果。

精确算法：使用哈希切分进行精确计算，下图有算法分析

如何扩展BloomFilter使得它支持删除元素的操作

为什么布隆过滤器不支持删除，是因为可以有不同的值映射
到相同的位置，如果你删除一个值可能会影响另一个值。
因此要加一个计数，用整型四个字节来计数。

如何扩展BloomFilter使得它支持计数操作

直接用一个整型指针计数，直接进行操作，相同位置每来一个
就++一次，直接访问引用计数就行。

倒排索引

给上千个文件，每个文件大小为1K—100M。给n个设计算法对每个词找到所有包含它的文件，你只有100K内存

*中描述的倒排索引：
倒排索引（英语：Inverted index），也常被称为反向索引、
置入档案或反向档案，是一种索引方法，被用来存储在全文搜索
下某个单词在一个文档或者一组文档中的存储位置的映射。
它是文档检索系统中最常用的数据结构。
由上面的定义可以知道，一个倒排索引包含一个字典的索引
和所有词的列表。其中字典索引中包含了所有的Term
(通俗理解为文档中的词)，索引后面跟的列表则保存
该词的信息(出现的文档号，甚至包含在每个文档中的位置信息)
下面我举一个简单的例子来说明倒排索引。

一共有四个文件，每个文件中都有自己的内容
如现在我们要对四篇文档建立索引(实际应用中，文档的数量是海量的)
建立好索引图如下：

在上面的索引中，存储了两个信息，文档号和出现的次数。建立好索引以后，我们就可以开始查询了。查询时可以通过词找相关文件