本文总结下位图法在数据去重方面的使用,全文分为三个部分:

  • 一是位图法的定义

  • 二是使用位图法判断数据是否存在

  • 三是使用位图法找出不重复的数据

最后,附上C++的实现。

位图法

假设我们有40亿的unsigned int 数据,若我们用unsigned int的方式加载到内存,那么需要:40亿 * 4 / 1024 / 1024 = 15258MB 的内存。若我们把每一个数字的值作为数组下标,用一个位数组来表示每个数字的状态,那么空间则缩短了32倍(假设int占用空间为4字节),即仅仅需要 15258 / 32 = ‭476MB 的内存。

这个方法就叫做位图法。

用位图法判断数据是否存在

基本方法为:申请一块内存,使得bit的数量和需要判断的数字的数量一样. 然后加载所有数字,把数字作为下标所对应的位置为1。

查找的时候,则判断对应的位是否为 1,是则存在,否则不存在。C++实现如下:

#include <bitset>
#define MAX_NUMS 1000000

bool findNumInBigData(vector<int> &array, int num){
    bitset<MAX_NUMS> bitArray;
    for (auto item : array)
        bitArray[item] = 1;
    return bitArray[num];
}

用位图法获取不重复数据

基本方法和上面相同,只不是这次用两位来表示一个数据的状态,若数据重复了则将两位置为11,只出现一次则将两位置为01,没有出现则两位为00

最后遍历位数组得到所有不重复的数字,C++实现如下:

#include <bitset>
#define MAX_NUMS 1000000

vector<int> findUnRepetitiveNums(vector<int> &array){
    bitset<MAX_NUMS * 2> bitArray;
    for(auto item : array){
        item *= 2;
        if (!bitArray[item] && !bitArray[item + 1])
            bitArray[item + 1] = 1;
        else{
            bitArray[item] = 1;
            bitArray[item+1] = 1;
        }
    }
    vector<int> result;
    for(int i = 0; i < bitArray.size(); i+=2){
        if (!bitArray[i] && bitArray[i+1])
            result.push_back(i / 2);
    }
    return result;
}