C++如何實現BitMap數據結構

Posted on by

分治，分佈式。BitMap(位圖)及其升級版bloom filter是處理海量數據常用的方法，這裡先介紹BitMap概念及其c++實現。

一、BitMap位圖

該數據結構描述瞭一個有限定義域內的稠密集合，其中的每一個元素最多出現一次並且沒有其他任何數據與該元素相關聯。

即使這些條件沒有完全滿足（例如，存在重復元素或額外的數據），也可以用有限定義域內的鍵作為一個表項更復雜的表格索引。

所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。

由於采用瞭Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。

例如假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這裡假設這些元素沒有重復）。

那麼我們就可以采用Bit-map的方法來達到排序的目的。

要表示8個數，我們就隻需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，

如下圖：

遍歷第一個元素4，則在第4為標1：

以此來推，遍歷完所有後結構：

我們現在遍歷一遍Bit區域，將該位是bit 1的位的編號輸出（2，3，4，5，7），這樣就達到瞭排序的目的。

二、C++實現

我們可以用一個unsigned int類型的數組或者向量來表示位圖，假設我們定義vector<unsigned int> a，則 第i位可表示為a[i/32]的i%32位（其中，32*N+r = i，r為i%32，也就是i/32的餘數）。

由於計算機對位的操作比乘除法更有效率，這裡計算i/32可以用位移操作：i>>5；計算i%32可以用1&31。

若是一個char數組str，則str的第i位為i/8(i>>3)地址塊的第i%8(i&7)位.下面以char為例說明，int類比可知。

#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
class BitMap{
private:
        char *bitmap;
        int gsize;
public:
       BitMap(){
       gsize=(10000>>3)+1;//default 10000
       bitmap= new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                }
       BitMap(int n){
       gsize=(n>>3)+1;
       bitmap=new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                  }
       ~BitMap(){delete []bitmap;}
       int get(int x){
       int cur=x>>3;
       int red=x&7;
       if(cur>gsize)return -1;
       return (bitmap[cur]&=1>>red); 
                      }
       bool set(int x){
       int cur=x>>3;//獲取元素位置,除8得到哪個元素，x/2^3得到那一個byte 
       int red=x&(7);//邏輯與，獲取進準位置,x&7==x%8.該Byte裡第幾個 
       if(cur>gsize)return 0;
       bitmap[cur]|=1>>red;//賦值，1向右移動red位，|表示該位賦值1
       return 1; 
                       }
};

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：