哈希表—位圖

原文鏈接：http://blog.csdn.net/qq_38646470/article/details/79427038
[1.什么是位圖？<br/>2.位圖的用處？<br/>3.位圖的結(jié)構(gòu)<br/>4.位圖題目操練<br/>5.總結(jié)（優(yōu)缺點(diǎn)分析）]
1.什么是位圖？
位圖就是bitmap的縮寫。所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的。在STL中有一個(gè)bitset容器，其實(shí)就是位圖。

所以我們可以了解到，位圖就是一個(gè)只用每一位來保存數(shù)的狀態(tài)的結(jié)構(gòu)。

2.位圖的用處？
位圖主要用于海量數(shù)據(jù)處理，索引，數(shù)據(jù)壓縮等方面有廣泛應(yīng)用
3.位圖的結(jié)構(gòu)
關(guān)于位圖的結(jié)構(gòu)，類似于哈希，位圖就是一個(gè)用每一位的0，1來表示一個(gè)數(shù)的狀態(tài)。

比如，我們現(xiàn)在有一個(gè)文件，這個(gè)文件中有數(shù) 1，5，4294967295。我們就把第1位，第5位，第4294967295位改為狀態(tài)1。

4.位圖題目操練
給4 0 億個(gè)不重復(fù)的無符號(hào)整數(shù)，沒排過序。給一個(gè)無符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這4 0 億個(gè)數(shù)中。

題目分析：這是一道關(guān)于海量數(shù)據(jù)查找的題，其實(shí)這道題，我們就可以和哈希表聯(lián)系在一起，為何說是海量數(shù)據(jù)呢，對(duì)于一個(gè)40億整數(shù)，我們?nèi)绻娴脑挘凑諢o符號(hào)整數(shù)來存儲(chǔ)，那么下來，大概就需要40億*4這么些字節(jié)，下來大概就是16G的 內(nèi)存。

對(duì)于現(xiàn)在的64位機(jī)，普遍標(biāo)配內(nèi)存也就是4-8G的內(nèi)存，顯而易見，16G是沒有辦法一次性處理的。那么我們?nèi)绾问呛?？進(jìn)行拆分？這樣顯然也是不好的，怎么拆，還有效率問題。
所以在這里我們采取一種新的思路，這種思路就是位圖。
位圖結(jié)構(gòu)定義

typedef struct BitMap
{
    size_t* _bits;
    size_t _range;
}BitMap;

位圖相關(guān)接口

void BitMapInit(BitMap *bm,size_t range) //初始化
{
    assert(bm);
    bm->_bits = NULL;
    bm->_range = range;
    bm->_bits = (size_t *)malloc(sizeof(char)*bm->_range/8);
    assert(bm->_bits);
    memset(bm->_bits,0,sizeof(char)*bm->_range/8);
}

void BitMapSet(BitMap *bm,size_t x)//標(biāo)記相應(yīng)位
{
    size_t num = x>>5;
    size_t bit = x%32;

    bm->_bits[num] |=(1<<bit);
}

void BitMapReset(BitMap *bm,size_t x)//恢復(fù)相應(yīng)位
{
    size_t num = x>>5;
    size_t bit = x%32;

    bm->_bits[num] &= (~(1<<bit));
}

int BitMapTest(BitMap *bm,size_t x)
{
    size_t num = x>>5;
    size_t bit = x%32;

    if ((1<<bit)&bm->_bits[num])
        return 0;
    return -1;
}

測(cè)試案例及結(jié)果截圖：

void TestBitMap()
{
    BitMap bm;
    BitMapInit(&bm,-1);
    BitMapSet(&bm,5);
    BitMapSet(&bm,6);
    BitMapSet(&bm,7);
    BitMapSet(&bm,8);
    BitMapSet(&bm,-1);

    printf("%d\n",BitMapTest(&bm,4));
    printf("%d\n",BitMapTest(&bm,5));
    printf("%d\n",BitMapTest(&bm,6));
    printf("%d\n",BitMapTest(&bm,7));
    printf("%d\n",BitMapTest(&bm,8));
    printf("%d\n",BitMapTest(&bm,-1));
}

這道題中位圖結(jié)構(gòu)代碼不難，注意理解思路，必須熟練掌握位運(yùn)算。

5.總結(jié)
優(yōu)缺點(diǎn)：
(1)可讀性差
(2)位圖存儲(chǔ)的元素個(gè)數(shù)雖然比一般做法多，但是存儲(chǔ)的元素大小受限于存儲(chǔ)空間的大小。位圖存儲(chǔ)性質(zhì)：存儲(chǔ)的元素個(gè)數(shù)等于元素的最大值。比如， 1K 字節(jié)內(nèi)存，能存儲(chǔ) 8K 個(gè)值大小上限為 8K 的元素。（元素值上限為 8K ，這個(gè)局限性很大?。┍热纾鎯?chǔ)值為 65535 的數(shù)，就必須要 65535/8=8K 字節(jié)的內(nèi)存。要就導(dǎo)致了位圖法根本不適合存 unsigned int 類型的數(shù)（大約需要 2^32/8=5 億字節(jié)的內(nèi)存）。
(3)位圖對(duì)有符號(hào)類型數(shù)據(jù)的存儲(chǔ)，需要 2 位來表示一個(gè)有符號(hào)元素。這會(huì)讓位圖能存儲(chǔ)的元素個(gè)數(shù)，元素值大小上限減半。 比如 8K 字節(jié)內(nèi)存空間存儲(chǔ) short 類型數(shù)據(jù)只能存 8K*4=32K 個(gè)，元素值大小范圍為 -32K~32K 。