五、布隆过滤器应用
1.找文件交集
给两个文件，分别有100亿个query，只有1G内存，如何找到两个文件交集？请给出近似算法和精确算法。
（1）近似算法
判断交集本质上是判断在不在，读取第一个query，将元素都映射到布隆过滤器中，再读取第二个文件中的query，判断每个query在不在布隆过滤器中，如果在就是交集。
（2）精确算法
假设每个query是20字节，100亿个query就是100亿*20个字节=2000亿KB=200GB，使用哈希切分
2.扩展布隆过滤器
如何扩展BloomFilter使得它支持删除元素的操作？
布隆过滤器本不支持删除，这是由于布隆过滤器判断一个元素在不在时可能会存在误判，删除它对应的bit位时会影响其他元素，且多个元素可能会映射到同一bit位，因此删除某一bit位时会影响其他元素，可能会导致其他元素也被删除。
不过可以采用以下方法让布隆过滤器支持删除元素：
在布隆过滤器中找到该元素后，由于使用多个位表示一个元素，因此可以对布隆过滤器的每一个bit位使用计数来代替0/1(在不在)，当有多个元素映射到该bit位时，该bit计数++ ，删除时，该bit计数--。
六、哈希应用
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？
1.找到出现次数最多的IP
（1）文件超过100G，不能加载到内存中，就需要将文件进行哈希切分，通过一个哈希函数，将log文件中的每个IP都转换为整数，如果IP相同，那么转换后的整数也相同，就会映射到同一个小文件中。
（2）切分成小文件后就可以加载到内存了，对于每次加载到内存的小文件，使用map<string,int>对该小文件中的所有IP进行次数统计，找出出现次数最多的IP。
（3）将每个文件中出现次数最多的IP再使用map<string,int>进行统计，就能找到出现次数最多的那个IP了。
另外：将文件切分为100个小文件，这100个小文件并不是均匀切分的，有的可能会小于1G，有的则可能会大于1G，当有几十个文件都大于1G时，可以考虑将文件直接切分为200份，而不是100份，这样每个小文件大约为512MB。
2. 找到top K的IP
（1）对100G的文件建堆，内存放不下，因此还是要切分成小文件，如上图中将100G的大文件利用哈希函数切分成100个小文件。
（2）将第一个文件加载到内存中，对第一个小文件建有K个元素的小堆，只要比堆顶元素大就进堆，最后堆里剩下的就是第一个小文件中出现次数最多的K个IP。
（3）将剩下的其它小文件依次加载到内存，每加载一个小文件，就将该小文件中的所有IP和堆顶元素进行比较，只要比堆顶元素大，就进堆。最后堆里留下的就是出现次数最多的K个IP。
3.用Linux系统命令实现找到top K的IP
假如有以下文件IP.log：
1. 192.168.1.5 2. 69.52.220.44 3. 10.152.16.23 4. 192.168.3.10 5. 192.168.1.4 6. 192.168.2.1 7. 192.168.0.9 8. 10.152.16.23 9. 192.163.0.9 10. 192.168.0.9 11. 69.52.220.44 12. 192.168.1.4 13. 192.168.1.5 14. 192.163.0.9 15. 192.168.2.1 16. 192.168.0.1 17. 192.168.0.2 18. 192.168.0.9 19. 9.9.9.9 20. 127.0.0.1 21. 192.168.0.90 22. 192.168.0.89 23. 192.168.0.8 24. 192.168.0.9 25. 192.163.0.9
（1）按行排序，并将结果输出到标准输出
sort 文件名
（2）统计并显示文本文件中出现的行或列的次数
uniq -c
（3）根据出现次数倒序排序
sort -r
（4）查看开头K行
head -k
显示出现次数最多的前K个IP
