本系列文章对海量数据面试题进行了归类和总结,给出海量数据处理问题的通用解决思路,后面附有例题,希望大家能够举一反三。
往期回顾:
多层桶划分,本质思想还是分而治之,可以认为是BitMap的增强版。
基本原理:因为元素范围很大,内存超限,不能使用直接寻址表,所以通过多次划分,逐步确定范围,每次都在一个可以接受的范围内进行,逐步缩小。
使用场景:BitMap所需要的内存空间无法一次性满足。
常见问题:第K大数,中位数,不重复或重复的数字。
(1) 如果数据类型为int16,首先申请一块2^16个bit的内存区域,然后将5亿个数依次划分到这些区域中,依次统计落到各个区域里的数的个数,之后我们根据计算出中间位置的数应该落到那个区域,同时知道这个区域的第几个数刚好是中位数;然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
(2) 实际上,如果不是int16而是int64,2^64个Bit在内存中是存不下的,但可以经过3次划分降低到可以计算的程度。即可以先将2^64个区域分为2^24个较大的区域,然后确定区域的中部位于哪个区域内,再将该区域分成2^20个子区域,然后确定区域的中部位于哪个区域内,然后每个子区域里的数的个数只有2^20,就可以直接利用直接寻址表进行统计了。