1. 查找
1.1 二分
查找 40亿个不重复的unsigned int的整数，未排序，然后再给一个数，如何快速判断这个数是否在40亿个数当中： 0-1二分
该数如果是0开头，就去掉40亿中的1的部分；再比较第二高位，如果是0开头，继续去掉第二高位为1的部分，…，直到文件为空，或者剩下该元素。时间复杂度为O(logn)。
1.2 bloom filter
查找 URL 是否存在：bloom filter
根据样本量和失误率，确定布隆过滤器bit数组大小，和hash个数 k
查找 两个URL的文件 共同的URL： bloom filter
根据a文件的50亿个url，得到一个1000亿的bit数组，用a文件先进行k个hash，然后在用b文件进行k个hash，看是否已存在。
1.3 堆
查找 最大数的TopK ：小根堆
2. 统计
2.1 bitmap
查找 没有出现的数 ：bitmap，bit为0的数
统计 不重复元素个数： bitmap，1的个数
统计 已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数： bitmap
8位最多99 999 999，需要100M个bit，不到100M字节的内存即可。然后统计二进制1的个数。
统计 2.5亿个整数中找出不重复的整数的个数： bitmap
2.5亿需要240M字节的内存。然后统计二进制1的个数。
2.2 hash映射 hashmap
统计 出现次数最多的元素：hash映射 hashmap
类似词频统计，hash映射成多个小文件，hashmap统计每部分出现次数最多的数，比较每部分的次数
统计 重复的URL： hash映射 hashmap
hash映射成多个小文件，hashmap统计
统计 URL次数的topK ： hash映射 hashmap 小根堆
hash映射成多个小文件，hashmap统计，每个小文件构建一个小根堆，合并所有的小根堆，得到全局的小根堆，最终得到topK。
统计 海量日志数据，提取出某日访问百度次数最多的那个IP
先把访问百度的ip全部筛选出来，
再将ip地址hash到多个小文件
再hashmap统计各个ip的次数
最后比较各个小文件的最大次数
2.3 划区域
找到中位数：40亿个非负整数，10MB内存
- 32位的int的范围是0-4294967295，10MB能容纳一个size为2M的数组，数组元素为int，一共为8MB。不需要key，只需要value，因为key是按顺序的。
- 4 2^30 /2M = 2^32 /(2 2^20)=2048，分成2048个区间
- 遍历40亿个元素，统计每个区间的元素个数
- 找到中位数所在的区间k，和第几个数为中位数
- 遍历40亿个元素到第k个区间，用2M的int数组作为统计个数，找到中位数。
Reference
http://blog.csdn.net/v_july_v/article/details/7382693
