海量数据面试题总结(3)-多层桶划分

本系列文章对海量数据面试题进行了归类和总结，给出海量数据处理问题的通用解决思路，后面附有例题，希望大家能够举一反三。

往期回顾：

• 海量数据面试题总结(1)-Hash映射+Hash统计+归并排序
• 海量数据面试题总结(2)-BitMap

模式三：多层桶划分

一、解决思路：

多层桶划分，本质思想还是分而治之，可以认为是BitMap的增强版。

基本原理：因为元素范围很大，内存超限，不能使用直接寻址表，所以通过多次划分，逐步确定范围，每次都在一个可以接受的范围内进行，逐步缩小。

使用场景：BitMap所需要的内存空间无法一次性满足。

常见问题：第K大数，中位数，不重复或重复的数字。

二、经典例题：

1. 找出5亿个int的中位数。

(1) 如果数据类型为int16，首先申请一块2^16个bit的内存区域，然后将5亿个数依次划分到这些区域中，依次统计落到各个区域里的数的个数，之后我们根据计算出中间位置的数应该落到那个区域，同时知道这个区域的第几个数刚好是中位数；然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

(2) 实际上，如果不是int16而是int64，2^64个Bit在内存中是存不下的，但可以经过3次划分降低到可以计算的程度。即可以先将2^64个区域分为2^24个较大的区域，然后确定区域的中部位于哪个区域内，再将该区域分成2^20个子区域，然后确定区域的中部位于哪个区域内，然后每个子区域里的数的个数只有2^20，就可以直接利用直接寻址表进行统计了。