分治，分布式。BitMap(位圖)及其升級(jí)版bloom filter是處理海量數(shù)據(jù)常用的方法，這里先介紹BitMap概念及其c++實(shí)現(xiàn)。

一、BitMap位圖

該數(shù)據(jù)結(jié)構(gòu)描述了一個(gè)有限定義域內(nèi)的稠密集合，其中的每一個(gè)元素最多出現(xiàn)一次并且沒有其他任何數(shù)據(jù)與該元素相關(guān)聯(lián)。

即使這些條件沒有完全滿足（例如，存在重復(fù)元素或額外的數(shù)據(jù)），也可以用有限定義域內(nèi)的鍵作為一個(gè)表項(xiàng)更復(fù)雜的表格索引。

所謂的Bit-map就是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。

由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。

例如假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）。

那么我們就可以采用Bit-map的方法來達(dá)到排序的目的。

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

如下圖：

遍歷第一個(gè)元素4，則在第4為標(biāo)1：

以此來推，遍歷完所有后結(jié)構(gòu)：

我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是bit 1的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。

二、C++實(shí)現(xiàn)

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

由于計(jì)算機(jī)對(duì)位的操作比乘除法更有效率，這里計(jì)算i/32可以用位移操作：i>>5；計(jì)算i%32可以用1&31。

若是一個(gè)char數(shù)組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得到哪個(gè)元素，x/2^3得到那一個(gè)byte 
       int red=x&(7);//邏輯與，獲取進(jìn)準(zhǔn)位置,x&7==x%8.該Byte里第幾個(gè) 
       if(cur>gsize)return 0;
       bitmap[cur]|=1>>red;//賦值，1向右移動(dòng)red位，|表示該位賦值1
       return 1; 
                       }
};