hash分桶法

方法的本质是化大为小，用磁盘空间换内存空间

关键词：内存不足

本质：map-reduce思想
map阶段把数据map到不同的桶（机器）里，不同的机器处理子问题
reduce阶段将各个机器的结果汇总，得到结论

有一个超过100G大小的日志，从中找出出现次数最多的IP地址

如果内存足够大，这个问题该如何解决？不是top k，是top 1

用hash表就好了，以ip地址为key，以次数为value，扫描一遍hash表就可以了。

时间复杂度： O(N*read次数）
空间复杂度：O（不同的IP数量）
最大内存： 2^32个ip地址，每个用int保存，所以需要最多是 4G * 4 =16G的内存

如果内存不够怎么办？假设只有10m

大数据屡试不爽的方法是Hash分桶法，其实也是map reduce的思路

1、首先把100g的文件分成10000份，其实就是10000个桶；
2、然后把每个ip地址映射到一个桶里去，方法
file_id = hash(ip) % 10000
3、在每个文件中都找出出现频率最高的ip以及次数；
4、把这10000个最高频的ip进行合并，得到最终结果

时间复杂度：O（2n * read + nwrite)
空间复杂度：O（不同IP数量/10000)

和上题相同，不过要找top k

命令行方式
sort log_file | uniq -c | sort -nr k1,1 | head -10

HashMap+堆

把数据分发到不同桶
每个桶分别统计top k
最后top k 汇总

5亿个整数，找出不重复的数的个数

如何做distinct

还是hash分桶法，相同的数据肯定会被分到相同的桶里，然后分别统计每个桶中不同的数字的个数，最后汇总就可以了。
另外，这个题有个关键字——整数，所以我们可以按照整数的区间去做分桶，而不一定要用hash分桶。

类似题目：
给你一天的query log，找到最高频的top k个query
给qq登录数据，找到次数最多的qq号
给你购物数据，找出最多的物品

Bitmap

这是处理整数问题最有用的方法

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

方法1：hash分桶法
如果不是数字，而是query、商品，这时可以用分桶法，因为相同的内容可能会被分到相同的桶里，所以我们就生成两组桶，然后桶桶合并就好了。

方法2：针对整数
hash法虽然有效，但是要借助外存。而这个问题有个关键字——整数，所以我们是可以用bitmap来做的。

关键字：整数，1g内存

bitmap思想：可以用每个二进制位代表一个数字是否出现。
一个int变量有32位，可以表示32个整数。
而全部的整数不过是 4G个。如果原样保存，需要4*4 =16G的内存。而现在表示全部整数需要 4g /32 =500m内存就够了。

一个文件有100亿个int，1g内存，找出出现次数不超过2次的所有整数。

思想还是一样：用bitmap，只是之前用1位表示一个数字的出现或者不出现，这次用2位表示一个数字的出现次数，0不出现、1出现1次，2出现2次或者以上。

Bloomfilter

有两个文件，分别有100亿个query，只有1g内存，如何找到两个文件的交集。

方法1：hash分桶法

缺点，频繁磁盘读写

方法2：bloomfilter
首先，bloomfilter是个近似算法，不是精确算法，所以，需要先确认，是需要近似解还是精确解。如果是精确解，就只能用hash分桶法。

位数组和k个独立的hash函数，将hash函数对应的位数组的位置置为1。

查找时，如果发现所有hash函数对应的位置都是1，就说明存在。
韩显然这个过程不能保证查找的结果都是100%的正确。

只能说在这里的一定能找到，但是找到的不一定真的在这里。