BitMap(位图)

微信扫一扫

028-83195727 , 15928970361
business@forhy.com

BitMap(位图)

大数据处理2016-11-08

1K=1024byte

1M=1024K=1024*1024byte(约100万个字节)

1G=1024M=1024*1024K=1024*1024*1024byte(约10亿个字节)

假设现在有40亿个不重复且无序的无符号整数，现在给你一个整数让你快速判断它是否在这40亿个数里面？？？（假设现在只有4G的内存）

这道题的解决办法很简单，就是用这个数到这40个数中去找就行了，如果找到就是存在，找不到就是不存在。那么问题来了，40亿个无符号整形共有160亿个byte，也就是至少需要16G才能放得下，我么应该怎么才能将这40亿个整数加载到内存中呢？

方法一：分割文件

对于这种大数据问题，通用的方法就是对大文件切分，切分成若干个小文件，再对小文件应用数据结构求解。

方法二：bitmap(位图)

对于这种问题，我们通常还有一种更好的方法，那就是位图，位图也是hash的一种应用。

对于这些无符号整数我们完全没有必要用4个字节来表示，因为现在我们只需要找这个数存在还是不存在，只有两种状态，所以我们可以用一个bit位来表示一个数存在还是不存在，0表示不存在，1表示存在。所以现在40亿个无符号整数只需要500M就可以表示了。要找这个数存在还是不存在，只需要计算这个数在bitmap中的位置，再看这一位是0还是1就可以了。

#pragma once
#include<vector>
using namespace std;
class BitMap
{
public:
       BitMap(size_t range)                 //给定位图所能表示的范围
       {
              _bitmap.resize(range/32+1);      //设置大小
       }
       void Set(size_t num)         //置1
       {
              size_t index = num / 32;     //计算所在下标
              size_t bit = num % 32;       //得位所在位置
              _bitmap[index] |= (1 << bit);
       }
       void ReSet(size_t num)           //置零
       {
              size_t index = num / 32;         //计算所在下标
              size_t bit = num % 32;          //得位所在位置
              _bitmap[index] &= (~(1 << bit));
       }
       bool Test(size_t num)
       {
              size_t index = num / 32;         //计算所在下标
              size_t bit = num % 32;          //得位所在位置
              return (_bitmap[index]>>num)&1;
       }
private:
       vector<size_t> _bitmap;
};

扩展：

假设现在有100亿个无符号整数，现在要你找出只出现1次的数。(无符号整数所能表示的范围就是42亿9千万左右 )

解析：

这里一个数不止出现一次，所以我们用一个bit位是不能解决这个问题的。因为一个数出现的状态有三种即：出现0次，出现1次，出现多次。要表示三种状态我们至少需要两个bit位才可以。假设现在用：00表示没出现，01表示出现1次，11(或10)表示出现多次。这样算下来也只需要1G左右的内存。