海量数据处理算法题

Bitmap

bitmap是一种对位进行操作的“数据结构”，它由许多的比特位组成，每一个位表示某一个元素的信息，这种“数据结构”可以大大地节约内存的使用，特别适合用于海量数据处理的场合。

题目1

已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。比如12345678、12345678、98765432，这三个号码，不同号码的个数是2个。

解题思路

使用Bitmap，每一个号码对应一个比特位，比如第一个比特位对应的电话号码是00000000。8位数字最大就是99999999，总共有100000000个8位数电话号码，所以就有100000000/8/1024/1024大约12M，用12M就能表示所有的8位电话号码。
遍历每一个电话号码并设置相应的比特位，最后在Bitmap中有多少个1就有多少个不同的电话号码。

题目2

2.5亿个整数中找出只出现一次的整数的个数，注意内存空间不足以容纳2.5亿个整数，且这些整数都是32位整数

解题思路

使用Bitmap，所有整数共月44亿不到，44亿个比特位大约需要522M空间，我们使用2个Bitmap表示1个数，这样大约需要1G空间。这2个Bitmap相同下标下的位构成几种情况，00表示未出现，01表示出现1次，11表示出现2次及以上。遍历这些数，如果对应的位置是00，则将其置01；如果是01，将其置11；如果是11，保持不变。对应关系函数是：

    int position = 0;//bitmap的下标
    if(整数 < 0){
        position = 整数 * -1;     
    }else if(整数 > 0){
        position = 整数 + Integer.MAX_VALUE + 1;
    }else{
        position = 0;
    }

题目3

有一个日志文件，里面每一行记录了在某天每一位用户访问网站的时间点，请问如何找出访问网站次数最多的用户？注意：日志文件中的记录超过1亿条,内存被限制在2G

思路

先hash分组, 把落在同一个组topK先算好，再综合算所有组的topK。
具体地说，假设用户ID是9位数字，比如123456789，根据用户ID的第一位数字将记录分为10组，落在同一个组里的记录计算出TOP1，最后计算10组的TOP1中的TOP1。