海量數據處理第二談-----位圖BitMap

位圖的概念：

    在C++中，位圖是以位來表示整數的結構，普通的整數一個數需要用4個字節來表示，我們可以換種思想，在整個整數的集合范圍內，某個整數存在與否，只有兩種情況，在或者不在，那么，我們可以考慮只用一個bit位，來表示該整數存在的狀態，從而達到節省內存的目的。

位圖實例分析：

    給一個實際的例子，給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中

    我們可以簡單計算一下，40億個整數全部放到內存，需要160億個字節，粗略計算，大致需要16G的內存，如果我們把每個整數是否出現，轉換成用一位來表示它存在的狀態，需要5億個字節，也就是大約500M的內存，對于計算機而言，對內存的節省亦常地重要，這就是位圖的一個重要應用。

位圖模擬實現：

    首先我們考慮位圖的結構，實際上也是對數組的封裝，只不過我們這里需要的是以bit位為單位進行存放，每一位的狀態只有0和1兩種，這里用來表示該整數是否在位圖內。

    我們以一個×××為例，在一個×××的空間，存儲【1 6 9 4 12 10】這些數，存儲結果應該如下：

    這個只給出了兩個字節，全可以表示上面的6個整數。

    關于位圖的底層，這里我們使用vector來模擬實現。

#include <vector>
#include<iostream>
using namespace std;
class BitMap
{
public:
    BitMap(const size_t& range)
    {
        int sz = (range >> 5) + 1;
        _vec.resize(sz);
    }
    void BitSet(const size_t& x)
    {
        int index = x >> 5; // index是x對應位所在的下標
        int num = x % 32; // num是x對應該×××的第多少位
        _vec[index] |= 1 << num;
    }
    void BitReSet(const size_t& x)
    {
        int index = x >> 5; // index是x對應位所在的下標
        int num = x % 32; // num是x對應該×××的第多少位
        _vec[index] &= (~(1 << num));
    }
    bool BitTest(const size_t& x)
    {
        int index = x >> 5; // index是x對應位所在的下標
        int num = x % 32; // num是x對應該×××的第多少位
        return _vec[index] & (1 << num);
    }
protected:
    vector<int> _vec;
};

    位圖的實現實際上就是進行一系列的位操作，通過位操作找到該×××對應的位，下面給出一組簡單的測試用例
    

void TestBitMap()
{
    BitMap  mp(100);
    mp.BitSet(1);
    mp.BitSet(2);
    mp.BitSet(11);
    mp.BitSet(22);
    cout << "test --<1>" << mp.BitTest(1) << endl;
    cout << "test --<2>" << mp.BitTest(2) << endl;
    cout << "test --<11>" << mp.BitTest(11) << endl;
    cout << "test --<22>" << mp.BitTest(22) << endl<<endl;
    mp.BitReSet(2);
    cout << "test --<1>" << mp.BitTest(1) << endl;
    cout << "test --<2>" << mp.BitTest(2) << endl;
    cout << "test --<11>" << mp.BitTest(11) << endl;
    cout << "test --<22>" << mp.BitTest(22) << endl << endl;
}

源碼庫中的位圖：

    在源碼庫中，有這樣一個容器 bitset，和我們這里的bitmap性質基本是一樣的，當然，功能要比上面實現的位圖大得多。

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1, true or false, ...).

The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).

Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

Because no such small elemental type exists in most C++ environments, the individual elements are accessed as special references which mimic bool elements:

    庫中提供了一系列的函數操作，除了set、reset、test之外，常用的還有filp<取反操作>，count<統計位為1的個數>。關于bitset的操作，都包含在

#include <bitset>

的頭文件中。

位圖的分析與擴展：

    位圖的確用起來會很方便，但并不是任何情況下都需要使用到位圖的，位圖通常是為了處理大量數據，內存中不足以存放所有的數字才使用的一種數據結構，因為位圖也有著一定的缺陷：

    1> 它的可讀性差

    2> 位圖在視圖節約空間的時候，也伴隨著一定的消耗，它要求給最大值和最小值之間的所有數都要占用一個bit位，當數據過于分散而數據量又不至太大的情況，位圖其實是一種比較浪費空間的做法。如果最小值為10000，位圖開辟出來的前10000個bit位其實就空了出來，沒有利用到，之前我們舉得例子，40億個整數，因為無符號整數的最大值就到42.9億左右，大部分的整數值確定都已經被取到，因此我們采用了位圖來實現。

    3> 當位圖用來存儲有符號整數時，有兩種解決方案，一種是我們約定好最小值不再從0開始，所有的計算都需要減去有符號整數的最大值，另一種是這里采用兩位來存儲一個數，用兩位來表示正數、負數、不存在三種狀態。

    試想，如果我們要求統計40億個無符號整數中，出現兩次以上的數該如何處理？

。。。。。。

    同樣，多加一位標志位，用兩個bit位來進行處理，那這樣的話，就需要我們自己來實現一個基本的兩位為一個單元的位圖結構。

    除此之外，位圖還可用來排序，判重，當然這里僅僅限于無符號整數，和上一節的哈希一樣，受限于整數范圍確實是個不好的地方，下一談會提到字符串哈希算法與布隆過濾器，正是由于字符串哈希算法，才使得這些數據結構得以大范圍的使用。

關于哈希算法：
    http://muhuizz.blog.51cto.com/11321490/1870717

                            -----muhuizz整理