分桶法简介
其实本质上还是分而治之的思想，重在”分”的技巧上！
- 适用范围：第 k 大，中位数，不重复或重复的数字；
- 基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
相关题目
2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这 2.5 亿个整数
有点像鸽巢原理，整数个数为 2^32，也就是我们可以将这 2^32 个数，划分为 2^8 个区域（比如用单个文件代表一个区域），然后将数据分离到不同的区域，然后不同的区域再利用 bitmap 就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
5 亿个 int 找它们的中位数
思路一
这个例子比上面那个更明显。首先我们将 int 划分为 2^16 个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到哪个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是 int 而是 int64，我们可以经过 3 次这样的划分即可降低到可以接受的程度。即可以先将 int64 分成 2^24 个区域，然后确定区域的第几大数，再将该区域分成 2^20 个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有 2^20，就可以直接利用 direct address table（直接寻址表）进行统计了。
思路二
同样需要做两遍统计，如果数据存在硬盘上，就需要读取 2 次。
方法同基数排序有些像，开一个大小为 65536 的 int 数组，第一遍读取，统计 int32 的高 16 位的情况，也就是 0-65535 都算作 0，65536 - 131071 都算作 1，就相当于用该数除以 65536。int32 除以 65536 的结果不会超过 65536 种情况，因此开一个长度为 65536 的数组计数就可以。每读取一个数，数组中对应的计数 +1，考虑有负数的情况，需要将结果加 32768 后记录在相应的数组内。
第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间 k，那么 0 - k-1 的区间里数字的数量 sum 应该 < n/2（2.5 亿），而 k+1 - 65535 的计数和也 < n/2。第二遍统计同上面的方法类似，但这次只统计处于区间 k 的情况，也就是说 (x / 65536) + 32768 = k。统计只统计低 16 位的情况，并且利用刚才统计的 sum，比如 sum = 2.49 亿，那么现在就是要在低 16 位里面找 100 万个数（2.5 亿 - 2.49 亿）。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。
系列导航
- 上一篇：大数据处理：分治、Hash、排序
- 下一篇：大数据处理：Bitmap & Bloom Filter
- 相关篇：大数据处理：Overview、大数据处理：分治、Hash、排序（双层桶本质也是分而治之）