1. hash函数分流
使用hash函数将海量数据按照种类均匀分散来，去处理
2. 布隆过滤器
使用布隆过滤器，用于集合的建立和查询，节省内存空间
1.4.1 布隆过滤器
3. 一致性hash
通常用来解决数据服务器负载问题，详情见
3.一致性hash
4. 并查集
使用并查集结构做并行计算，详情见
并查集
例如：岛问题
5. 位图
使用位图，解决某一范围上数字出现情况，并可以大量节省空间
题目：32位无符号的整数范围时0～42.9亿，现在有40亿个无符号整数，最多使用1G内存，找出所有出现了2次的数字
思路：可以使用hash分流的方式处理，也可以使用位图来记录，这里说下位图记录的步骤
- 使用2bit位来记录数字出现的次数。00代表没有出现过，01代表1次，10代表出现了2次，11代表出现了2次以上
- 40亿数字，大约需要40亿 * 2bit < 2^32 * 2 bit = 1G
- 1G的位图，每2位一个数，写入和查询数字对应的位图下标可以写一个统一的函数来处理
6. 分段统计思想
题目：使用10KB的内存，找出40亿个无符号整数的中位数
思路：使用位图记录某一个range出现的次数，然后找出接近
- 由于我们要记录出现的次数，所以需要一个4字节的内存来记录词频率，4字节=32位
- 10kb的内存，可以分为2560（10KB/4b=2560）个区间，即将这40亿个数字汇总到2560个区间内进行次数统计
- arr[0]代表就是0～40亿/2560这些数据出现的次数，arr[1]代表就是 40亿/2560 ～ 40亿/2560 * 2 以此类推
- 统计完成后，我们找20亿（中位数）在那个区间范围内x，代表中位数一定在
arr[x] - 将40亿/2560 * x +1 ～ 40亿/2560 * (x+1) 这些数字，重新分配到10kb的内存的arr中，重复1-4步骤，知道找出具体的中位数
题目：使用10KB的内存，将10G的文件（无符号整数，无序的），进行排序并输出到一个新文件中
思路：将数据分段统计和排序，数据结构使用小根堆
- 小根堆的size=1280，10KB / int记录数据 + int记录词频 = 10KB/8b = 1280
- 使用有限的内存将数据分组处理
- 遍历大文件，将0-2^32/1280-1的数据记录到小根堆，不在这个范围的数据不处理，
- 统计完成后，按照数字和出现的次数，写到输出文件中，eg: 1出现了2次，5出现了1次，7出现了3次，就是：1，1，5，7，7，7的顺序写到文件
- 重复3-4的步骤，依次将 2^32/1280 * x ~ 2^32/1280 * (x+1) -1 的数据进行处理
- 最后输出的文件就是有序的
7. 利用堆、外排序来处理
在遇到一些大文件或者大数据，需要汇总信息的，通常使用堆这种数据结构来处理
7.1 Top100
题目：某搜索公司一天用户搜索的词汇在百亿级别，请设计一种求出每天热门Top100词汇的可行办法
思路：
- 使用hash分流，将这些海量数据分成64组（具体的组数量，要根据内存要求来）
- 对每一组上进行统计汇总，将词和词频 保存在一个大顶堆中
- 将这64个大顶堆中的数据，重新加入一个容量为100的大顶堆中（可以称为总堆）
- 最后，top100的词汇就是总堆中的数据
7.2 最小的3个数
题目：找出40亿个无符号整数的最小的3个数
思路：使用大顶堆进行保存数据
- 建立一个大顶堆，size=3，保存：数字和出现的次数
- 遍历40亿，并构建大根堆，如果数据大于堆顶元素直接pass，小于堆顶元素，那么加入堆，如果该元素是第一次加入，那么此时会更新堆顶元素
- 最后，取出堆中元素，找出最小的3个数字即可
进阶：上面的方案，在遍历过程中会直接将40亿数据加载进内存，如果有内存限制，可以按照文件进行分段处理。
