【什么是Bit-map】
所謂的Bit-map就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。
如果說(shuō)了這么多還沒明白什么是Bit-map，那么我們來(lái)看一個(gè)具體的例子，假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）。那么我們就可以采用Bit-map的方法來(lái)達(dá)到排序的目的。要表示8個(gè)數(shù)，我們就只需要8個(gè)Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0(如下圖：)
然后遍歷這5個(gè)元素，首先第一個(gè)元素是4，那么就把4對(duì)應(yīng)的位置為1（可以這樣操作 p+(i/8)|(0x01<<(i%8)) 當(dāng)然了這里的操作涉及到Big-ending和Little-ending的情況，這里默認(rèn)為Big-ending）,因?yàn)槭菑牧汩_始的，所以要把第五位置為一（如下圖）：
然后再處理第二個(gè)元素7，將第八位置為1,，接著再處理第三個(gè)元素，一直到最后處理完所有的元素，將相應(yīng)的位置為1，這時(shí)候的內(nèi)存的Bit位的狀態(tài)如下：
然后我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是一的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。下面的代碼給出了一個(gè)BitMap的用法：排序。
//定義每個(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()
{
//為了簡(jiǎn)單起見，我們不考慮負(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;
}
【適用范圍】
可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來(lái)說(shuō)數(shù)據(jù)范圍是int的10倍以下
【基本原理及要點(diǎn)】
使用bit數(shù)組來(lái)表示某些元素是否存在，比如8位電話號(hào)碼
【擴(kuò)展】
Bloom filter可以看做是對(duì)bit-map的擴(kuò)展
【問題實(shí)例】
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ò)展一下，用2bit表示一個(gè)數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時(shí)候，如果對(duì)應(yīng)位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變。或者我們不用2bit來(lái)進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map，都是一樣的道理。
bitmap的C語(yǔ)言實(shí)現(xiàn)
bitmap.h
/*
*bitmap的c語(yǔ)言實(shí)現(xiàn)
*/
#ifndef _BITMAP_H_
#define _BITMAP_H_
/*
*功能：初始化bitmap
*參數(shù)：
*size：bitmap的大小，即bit位的個(gè)數(shù)
*start：起始值
*返回值：0表示失敗，1表示成功
*/
int bitmap_init(int size, int start);
/*
*功能：將值index的對(duì)應(yīng)位設(shè)為1
*index:要設(shè)的值
*返回值：0表示失敗，1表示成功
*/
int bitmap_set(int index);
/*
*功能：取bitmap第i位的值
*i：待取位
*返回值：-1表示失敗，否則返回對(duì)應(yīng)位的值
*/
int bitmap_get(int i);
/*
*功能：返回index位對(duì)應(yīng)的值
*/
int bitmap_data(int index);
/*釋放內(nèi)存*/
int bitmap_free();
#endif
bitmap.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bitmap.h"
unsigned char *g_bitmap = NULL;
int g_size = 0;
int g_base = 0;
int bitmap_init(int size, int start)
{
g_bitmap = (char *)malloc((size/8+1)*sizeof(char));
if(g_bitmap == NULL)
return 0;
g_base = start;
g_size = size/8+1;
memset(g_bitmap, 0x0, g_size);
return 1;
}
int bitmap_set(int index)
{
int quo = (index-g_base)/8 ;
int remainder = (index-g_base)%8;
unsigned char x = (0x1<<remainder);
if( quo > g_size)
return 0;
g_bitmap[quo] |= x;
return 1;
}
int bitmap_get(int i)
{
int quo = (i)/8 ;
int remainder = (i)%8;
unsigned char x = (0x1<<remainder);
unsigned char res;
if( quo > g_size)
return -1;
res = g_bitmap[quo] & x;
return res > 0 ? 1 : 0;
}
int bitmap_data(int index)
{
return (index + g_base);
}
int bitmap_free()
{
free(g_bitmap);
}
測(cè)試程序bitmap_test.c：
#include <stdio.h>
#include "bitmap.h"
int main()
{
int a[] = {5,8,7,6,3,1,10,78,56,34,23,12,43,54,65,76,87,98,89,100};
int i;
bitmap_init(100, 0);
for(i=0; i<20; i++)
bitmap_set(a[i]);
for(i=0; i<100; i++)
{
if(bitmap_get(i) > 0 )
printf("%d ", bitmap_data(i));
}
printf("/n");
bitmap_free();
return 0;
}
