哈希表的博客链接：http://www.jb51.cc/article/p-pdvyeclx-wr.html
位图的博客链接：http://www.jb51.cc/article/p-ouvdnatb-wr.html
题目1:
给一个超过100G大小的log file,log中存在着IP地址，设计算法找到出现此数最多的IP地址
1.这里首先想到的是切分，因为呢，100G太大，放不到内存中；
我们可以切分成1000个小文件，每个文件大概就是500M左右的样子；
2.可是，问题来了，如何才可以将相同的IP地址放入同一个文件当中呢？
3.这里就要用到哈希的思想，哈希切分；
每一个IP地址就是一个对应的字符串，我们可以算出key值，然后取余数，余数就表示的是存储的文件号
比如index = key% 1000;余数必定在 0~999，这样我们就可以将相同的IP地址放入同一个文件中啦
然后呢，依次将这些文件装载入内存，统计每个文件出现最多的IP，然后进行比较
即可求解
题目2:
给一个超过100G大小的log file,log中存在着IP地址，设计算法找到TopK的IP地址
1.说到TopK问题，立马想到了堆这个数据结构；
题目中求得是次数最多的前K个，那我们就可以建一个小堆；
2.还是利用到第一道题目，当我们得到第一个文件时，将第一个文件中前K个数据建小堆；
3.然后后面的元素依次和堆顶元素进行比较，如果比堆顶元素的次数多，那么堆顶出堆，该元素入堆
直到所有文件全部读完，留在该堆里面的元素便是TopK个最多的元素
题目3:
给定100亿个整数，设计算法找到只出现一次的整数
首先呢，32个字节所能表示的整数只有42亿多个，100亿个大大超过了42亿，肯定是有重复的；
全部装载到内存？肯定不合适，一个整数4个字节，100亿个整数就是400亿个字节；
由于40亿多的字节 约等于 4G，400亿字节大概就是40G，电脑的内存又有多大呢？
解法1:哈希切分
和前面的题目一样，用哈希切分，将相同的数划分到同一个文件中，然后分别统计各个小文件中出现一次的数据；
解法2:位图变形
1.之前位图是利用每一个比特位来存储数据，我们现在可以多用一个位，也就是两个比特位；
00代表该数没有出现过，01代表出现过一次，10代表出现了两次及以上；
2.当位图统计元素次数时，若没有出现或者出现了一次，则+1；否则不变；
这样我们可以根据位图的比特位来找到出现一次的数了；
3.一个数两个比特位，所有的数也只需要1个G
题目4:
给两个文件，分别有100亿个整数，我们只有1G的内存，如何找到这两个文件之间的交集
解法1:直接比较
首先将两个文件A，B划分成多个小文件A1,A2,A3...B1,B2,B3..，然后依次用一个小文件(如A1)，比较B类的所有小文件；
比较完后，再用A2比较B的所有小文件.....
但是，效率实在是太慢了╮(╯▽╰)╭
时间复杂度O(N* N)
解法2:哈希切分
如前面的题目所示，也是划分成多个小文件，但是数字划分到对应的小文件是通过哈希算法来切分的；
这样可以保证相同的数字只出现在A，B相同的编号中；
解法3:利用位图
32位的整数有42亿，可以用500多M的位图来存储；
出现了相同的数字便是出现了交集；
题目5:
1个文件中有100亿个int，用1G内存找到出现次数不超过两次的整数
与题目3类似，可以用哈希切分将这些整数划分到同一个文件当中
也可以用位图的变形，用两个位 00 01 10 11，存储完之后
题目6:
给两个文件，分别有100亿个query（我们可以认为是字符串），只有1G内存，我们如何找到交集；分别给出近似算法和精确算法
query，表示的是查询的意思，也就是一串字符串
该题目类似于第四题
精确算法：哈希切分
将两个文件用相同的字符串哈希算法，求出字符串对应的key值，然后取余，放入需要相同的文件中
近似算法：布隆过滤器
布隆过滤器利用的是位图，我们可以将A文件中的所有整数存入布隆过滤器中，
然后用B文件依次去比较判断是否存在
注意：布隆过滤器可能存在误判，所以是近似算法
题目7:
如何扩展布隆过滤器使之可以支持删除元素的操作
因为布隆过滤器是将一个数对应多个位，很可能存在冲突
在删除的时候，有可能这些位是由于其他数的存在而被置数的，并不是由于该数
所以一般情况下布隆过滤器不支持删除，如果需要删除，就需要增加计数操作
题目8:
如何扩展布隆过滤器使之支持计数操作
由于可以使用计数来使得布隆过滤器支持删除操作，但是由于一个int是4个字节，一个数用位图本需要1个字节，现在要增加4个字节，显然与我们使用位图相违背
因此呢，我们想到用vector来存储计数，然后用字符串哈希算法，转换后的整数作为vector的下标，每次出现即自增；
在删除时，若该位大于0，就可以自减来复位；
题目9:
给上千个文件，每个文件在1k~100M之间。给定n个词，设计算法找出包含他的文件，只利用100K的内存
刚拿到这道题目时，我是懵逼的，因为只有100K的内存，感觉实在太小了；
捋一捋这道题目需要注意的点：
@H_101_301@（1）文件里存储的是不定的单词，不能切分
（2）用一个Info的文件，用来保存N个词语以及文件的其他信息
（5）将内存的缓冲区分成两份，一份用来读取布隆过滤器，一份用来读文件进行比较
（6）读入一个单词时，依次读取布隆过滤器，判断是否存在该词语，若不存在，则读取下一个布隆过滤器，直到所有的布隆过滤器都被读完
题目10:
有一个字典，包含了N个英文单词，现在给出任意个字符串，设计算法找出包含该字符串的所有单词
这里我们要用到一种特殊的数据结构---字典树
字典树是哈希表的一个变种
假设我要查询的单词时hi，那么我只用判断以h打头的子树中是否存在hi中就可以了；
