BitMap

字面意思解釋為位圖荡碾，準(zhǔn)確翻譯為基于位的映射

What is 基于位的映射恃逻？

• 就是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value，而Key即是該元素椒袍；
  由于采用了bit為單位來存儲(chǔ)數(shù)據(jù)驼唱，因此可以大大節(jié)省存儲(chǔ)空間

舉個(gè)例子，立馬了解BitMap的基本思想

• 32位機(jī)器上驹暑，對(duì)于一個(gè)整型數(shù)玫恳，比如int a = 1 在內(nèi)存中占32 bit位，這是為了方便計(jì)算機(jī)的運(yùn)算优俘。但是對(duì)于某些應(yīng)用場景而言京办，這屬于一種巨大的浪費(fèi)，因?yàn)槲覀兛梢杂脤?duì)應(yīng)的32 bit位對(duì)應(yīng)存儲(chǔ)十進(jìn)制的0 - 31個(gè)數(shù)帆焕，而這就是Bit-map的基本思想

基于上述基本思想惭婿，Bit-map算法在處理大量數(shù)據(jù)的排序、查詢以及去重；以及在用戶群做交集和并集運(yùn)算的時(shí)候也有極大的便利财饥。

1. BitMap的應(yīng)用

1.1 快速的排序

假設(shè)要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）,就可以采用Bit-map的方法來達(dá)到排序的目的换吧。要表示 8個(gè)數(shù)，只需要8個(gè)Bit（1 Bytes）;
首先我們開辟1 Byte的空間钥星，將這些空間的所有Bit位都置為0

• 優(yōu)點(diǎn)：
  運(yùn)算效率高，不需要進(jìn)行比較和移位锅论；
  占用內(nèi)存少讼溺，比如N = 10000000，只需占用內(nèi)存為N/8 = 1250000Byte = 1.25M最易。
• 缺點(diǎn)：
  所有的數(shù)據(jù)不能重復(fù)怒坯。即不可對(duì)重復(fù)的數(shù)據(jù)進(jìn)行排序和查找。

利用BitMap實(shí)現(xiàn)的排序

//定義每個(gè)Byte中有8個(gè)Bit位
#include ＜memory.h＞
#define BYTESIZE 8
void SetBit(char *p, int posi)
{
    for(int i=0; i ＜ (posi/BYTESIZE); i++)
    {
        p++;
    }
 
    *p = *p|(0x01＜＜(posi%BYTESIZE));//將該Bit位賦值1
    return;
}
 
void BitMapSortDemo()
{
    //為了簡單起見藻懒，我們不考慮負(fù)數(shù)
    int num[] = {3,5,2,10,6,12,8,14,9};
 
    //BufferLen這個(gè)值是根據(jù)待排序的數(shù)據(jù)中最大值確定的
    //待排序中的最大值是14剔猿，因此只需要2個(gè)Bytes(16個(gè)Bit)
    //就可以了。
    const int BufferLen = 2;
    char *pBuffer = new char[BufferLen];
 
    //要將所有的Bit位置為0嬉荆，否則結(jié)果不可預(yù)知归敬。
    memset(pBuffer,0,BufferLen);
    for(int i=0;i＜9;i++)
    {
        //首先將相應(yīng)Bit位上置為1
        SetBit(pBuffer,num[i]);
    }
 
    //輸出排序結(jié)果
    for(int i=0;i＜BufferLen;i++)//每次處理一個(gè)字節(jié)(Byte)
    {
        for(int j=0;j＜BYTESIZE;j++)//處理該字節(jié)中的每個(gè)Bit位
        {
            //判斷該位上是否是1，進(jìn)行輸出鄙早，這里的判斷比較笨汪茧。
            //首先得到該第j位的掩碼（0x01＜＜j），將內(nèi)存區(qū)中的
            //位和此掩碼作與操作蝶锋。最后判斷掩碼是否和處理后的
            //結(jié)果相同
            if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j))
            {
                printf("%d ",i*BYTESIZE + j);
            }
        }
        pBuffer++;
    }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    BitMapSortDemo();
    return 0;
}

1.2 快速去重

• 問題:
  2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)陆爽，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。
• 分析：
  　　首先扳缕，根據(jù)“內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)”我們可以快速的聯(lián)想到Bit-map。下邊關(guān)鍵的問題就是怎么設(shè)計(jì)我們的Bit-map來表示這2.5億個(gè)數(shù)字的狀態(tài)了。其實(shí)這個(gè)問題很簡單躯舔，一個(gè)數(shù)字的狀態(tài)只有三種驴剔，分別為不存在，只有一個(gè)粥庄，有重復(fù)丧失。因此，我們只需要2 bits就可以對(duì)一個(gè)數(shù)字的狀態(tài)進(jìn)行存儲(chǔ)了惜互，假設(shè)我們?cè)O(shè)定一個(gè)數(shù)字不存在為00布讹，存在一次01，存在兩次及其以上為11训堆。那我們大概需要存儲(chǔ)空間幾十兆左右描验。
  　　接下來的任務(wù)就是遍歷一次這2.5億個(gè)數(shù)字，如果對(duì)應(yīng)的狀態(tài)位為00坑鱼，則將其變?yōu)?1膘流；如果對(duì)應(yīng)的狀態(tài)位為01，則將其變?yōu)?1鲁沥；如果為11呼股，,對(duì)應(yīng)的轉(zhuǎn)態(tài)位保持不變。
  　　最后画恰，我們將狀態(tài)位為01的進(jìn)行統(tǒng)計(jì)彭谁，就得到了不重復(fù)的數(shù)字個(gè)數(shù)，時(shí)間復(fù)雜度為O(n)允扇。

1.3 快速查詢

????????同樣马靠，我們利用Bit-map也可以進(jìn)行快速查詢，這種情況下對(duì)于一個(gè)數(shù)字只需要一個(gè)bit位就可以了蔼两，0表示不存在甩鳄，1表示存在。假設(shè)上述的題目改為额划，如何快速判斷一個(gè)數(shù)字是夠存在于上述的2.5億個(gè)數(shù)字集合中妙啃。
　　同之前一樣，首先我們先對(duì)所有的數(shù)字進(jìn)行一次遍歷俊戳，然后將相應(yīng)的轉(zhuǎn)態(tài)位改為1揖赴。遍歷完以后就是查詢，由于我們的Bit-map采取的是連續(xù)存儲(chǔ)（整型數(shù)組形式抑胎，一個(gè)數(shù)組元素對(duì)應(yīng)32bits）燥滑，我們實(shí)際上是采用了一種分桶的思想。一個(gè)數(shù)組元素可以存儲(chǔ)32個(gè)狀態(tài)位阿逃，那將待查詢的數(shù)字除以32铭拧，定位到對(duì)應(yīng)的數(shù)組元素（桶）赃蛛，然后再求余（%32），就可以定位到相應(yīng)的狀態(tài)位搀菩。如果為1呕臂，則代表改數(shù)字存在；否則肪跋，該數(shù)字不存在歧蒋。

2. 擴(kuò)展

• Bloom Filter(布隆過濾器)
  當(dāng)一個(gè)元素被加入集合中時(shí),通過k各散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的k個(gè)點(diǎn),并將這k個(gè)點(diǎn)全部置為1.
  有一定的誤判率--在判斷一個(gè)元素是否屬于某個(gè)集合時(shí),有可能會(huì)把不屬于這個(gè)集合的元素誤判為屬于這個(gè)集合.因此,它不適合那些"零誤判"的應(yīng)用場合.在能容忍低誤判的應(yīng)用場景下,布隆過濾器通過極少的誤判換區(qū)了存儲(chǔ)空間的極大節(jié)省.
  
  
  Bloom Filter使用k個(gè)相互獨(dú)立的哈希函數(shù)（Hash Function），它們分別將集合中的每個(gè)元素映射到{1,…,m}的范圍中州既。對(duì)任意一個(gè)元素x谜洽，第i個(gè)哈希函數(shù)映射的位置hi(x)就會(huì)被置為1（1≤i≤k）。注：如果一個(gè)位置多次被置為1吴叶，那么只有第一次會(huì)起作用阐虚，后面幾次將沒有任何效果。
  
  
  在判斷y是否屬于這個(gè)集合時(shí)晤郑，對(duì)y應(yīng)用k次哈希函數(shù)敌呈，若所有hi(y)的位置都是1（1≤i≤k），就認(rèn)為y是集合中的元素造寝，否則就認(rèn)為y不是集合中的元素磕洪。
  
  
  Bloom filter可以看做是對(duì)bit-map的擴(kuò)展（關(guān)于Bloom filter參見：海量數(shù)據(jù)處理之Bloom filter詳解）。

3. 實(shí)戰(zhàn)

• 適用范圍：可進(jìn)行數(shù)據(jù)的快速查找诫龙，判重析显，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下
• 基本原理及要點(diǎn)：使用bit數(shù)組來表示某些元素是否存在签赃，比如8位電話號(hào)碼
• 擴(kuò)展：bloom filter可以看做是對(duì)bit-map的擴(kuò)展

(1) 已知某個(gè)文件內(nèi)包含一些電話號(hào)碼谷异，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)锦聊。

• 8位最多99 999 999歹嘹，大概需要99m個(gè)bit，大概10幾m字節(jié)的內(nèi)存即可孔庭。 （可以理解為從0-99 999 999的數(shù)字尺上，每個(gè)數(shù)字對(duì)應(yīng)一個(gè)Bit位，所以只需要99M個(gè)Bit==1.2MBytes圆到，這樣怎抛，就用了小小的1.2M左右的內(nèi)存表示了所有的8位數(shù)的電話）

(2) 2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)芽淡。

• 將bit-map擴(kuò)展一下马绝， 采用2-Bitmap（每個(gè)數(shù)分配2bit，00表示不存在挣菲，01表示出現(xiàn)一次富稻，10表示多次掷邦，11無意義）進(jìn)行，共需內(nèi)存232*2bit=1GB內(nèi)存唉窃，還可以接受耙饰。然后掃描這2.5億個(gè)整數(shù)纹笼，查看Bitmap中相對(duì)應(yīng)位纹份，如果是00變01，01變10廷痘，10保持不變蔓涧。所描完事后，查看bitmap笋额，把對(duì)應(yīng)位是01的整數(shù)輸出即可元暴。

總結(jié)

使用Bit-map的思想，我們可以將存儲(chǔ)空間進(jìn)行壓縮兄猩，而且可以對(duì)數(shù)字進(jìn)行快速排序茉盏、去重和查詢的操作。Bloom Fliter是Bit-map思想的一種擴(kuò)展枢冤，它可以在允許低錯(cuò)誤率的場景下鸠姨，大大地進(jìn)行空間壓縮，是一種拿錯(cuò)誤率換取空間的數(shù)據(jù)結(jié)構(gòu)淹真。

引用

參考 1
參考 2
參考 3
參考 4： july
參考 5
參考 6