01 前言
这又是一个新的系列，为阅读「程序员代码面试指南」所做之笔记。尽量以一个小白能看懂的话讲。
每个问题分为几个部分：
- 题目
- 具体解决方案
- 思路重点
- 最后尝试用一句话来说完整个思路
只用2GB在20亿个整数中找到出现次数最多的数
题目
内存限制2GB，有一个包含20亿个全是32bit整数的大文件，找到出现次数最多的数。
具体方案
首先考虑所有数字都一样的情况，同一个数字的出现次数将达到20亿，我们使用一个32bit的整数足够记录。
假设我们使用哈希表，key为整数，value为出现次数，一个键值对共占用8Byte。由于当出现2亿个数的时候，内存占用为1.6G，在此我们假定每次能够比较的最大数字个数就为2亿个。
那么我们的下一步希望能够把大文件根据某种条件分散到n个文件中，每个文件中的数字个数最多为2亿。
考虑先根据哈希函数把整数分散到16个不同的文件中，这里假设我们的分类哈希函数足够秀，不会让其中某个文件的数字个数超过2亿。
这里需要一个 注意 点，就是不要混淆哈希函数跟哈希表的区别。
哈希函数实际上是对一堆信息的抽样，把任意的数据变成固定长度的信息。
灵魂拷问：
- 为什么我们需要哈希函数？这是为了把不同大小的文件都缩减称为同等长度的哈希值，便于接下来的计算。
- 为什么我们需要为什么上面说到哈希函数要足够 优秀？这是为了尽量保证每个数据算出来的哈希值要不一样。（极端情况下，所有文件的哈希值一样，肯定会被分到同一个文件）。
- 用哈希值怎么分成十六个文件？用公式 $hash(data)$ % 16 就可以。
最后，我们分别统计16个文件中出现次数最多的数字（可以同一台计算机统计16次，或者直接分发到16台计算机中分别统计）。得到了每个文件中出现次数最多的数之后，我们再找出这16个数字中出现次数最多者，即可得到答案。
思路重点
如何把大文件分为若干个小文件，条件是什么。
一句话
把大文件中的数字按照某种条件分类成若干小文件，保证同一个数字只会出现在一个小文件中，再分别统计小文件中出现个数最多者。
bit map的应用
bit map，key是data，value是bit类型或者bit数组。
常用于检测大数据中某个数据是否存在。
找出数组中未出现的数
给定无序的海量数据数组长度为40亿，类型是unsigned int，范围是0 ~ 4 294 967 295。找出数组中，范围0 ~ 4 294 967 295内没出现过的数。
解决方案：
新建一个bit map，类型<unsigned int, bit>，遍历数组，只要数字出现过，就把对应的bit map位设置为1。
遍历完数组之后遍历bit map，找到所有value为0的条目，即为没有出现过的数字。
找出数组中出现过两次的数
只需要计算两次，所以只需要两个bit来记录出现的次数就够了。建立mapHashMap<unsigned int, bit*>。当数字出现了一次，把value设置为01，出现过两次，设置为10。
最后遍历bit map，找到所有value为10的key。
一致性哈希算法
服务器有时候需要把用户的id做哈希，然后分配到不同服务器做处理，来做 负载均衡 。如果采用上面提到的哈希函数分割法，每个用户确实可以顺利被分散到不同服务器上，但是如果增加或者减少了服务器的数量，所有用户的数据都需要全部重新分配（ 因为 被除数变了，余数会发生变化）。
为了解决这个问题，我们避免采用对哈希值求余的方法来求得其应所在的服务器序号。
取而代之地，我们设想哈希值的范围，假设在[0, 232 - 1]内，我们把这个范围绕成一个环，然后把服务器均匀分布在上面。求得数据的哈希值之后，把数据交给环上顺时针的下一个服务器处理。
这样，当增加一个服务器的时候，只需要移动 一部分 数据到新服务器上。
