双层桶划分¶

双层桶不是一种数据结构，只是一种算法思维。分而治之思想。

当我们有一大推数据需要处理时，局限于各种资源限制 (主要说内存) 不能一次处理完成，这是需要将一大堆数据分成多个小段数据。通过处理各个小段数据完成最终任务。

双层这里是虚指，并不是一定把数据分成 2 份，也可能多份。比如下面几个问题：

第一个问题，2.5 亿 (2^32=4,294,967,296) 个数,我们将这 2^32 个数分到 2^8=256 个区域 (文件中)。每个文件中的平均数字个数差不多 2^24 个 (1 千 7 百万个)。 0~2^24 第一个文件，2^24~2^25 第二个文件

假设 32 位机，装下这些数字需要的内存是 2^24*4=2^26=64MB,也可以不用将文件一次性读入内存而是采用流式读取。

然后对每个文件使用 bitmap 处理，每 2bit(2-bitmap) 表示一个整数，00 表示整数未出现，01 表示出现一次，10 表示出现两次及其以上。这样，每个文件 2^24 个数字，最大数 2^32/(8/2)=2^30=1GB 内存

这个问题倒是更新是 bitmap 的应用，没有很好体现双层桶分治的优势。

第二个问题，首先我们将 int 划分为 2^16 个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

适用问题领域是：top-k，中位数，不重复或重复的数字