點陣圖法定義
所謂bitmap，就是用每一位來存放某種狀態，適用於大規模數據，但數據狀態又不是很多的情況。通常是用來判斷某個數據存不存在的。例如，要判斷一千萬個人的狀態，每個人只有兩種狀態：男人，女人，可以用0，1表示。那么就可以開一個int數組，一個int有32個位，就可以表示32個人。操作的時候可以使用位操作。
點陣圖法套用
一、給40億個不重複的unsignedint的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中申請512M的記憶體
一個bit位代表一個unsignedint值
讀入40億個數，設定相應的bit位
讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在
二、使用點陣圖法判斷整形數組是否存在重複
判斷集合中存在重複是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。
點陣圖法比較適合於這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然後再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重複。這種給新數組初始化時置零其後置一的做法類似於點陣圖的處理方法故稱點陣圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。
示例代碼如下：
packagecom.sitinspring;
publicclassDuplicatedArrayTest{
publicstaticvoidmain(String[]ARGs){
int[][]arr={
{1,2,3,5,3,5,56,534,3,32},
{1,2,3,5},
{1,2,3,5,3,5},
{0,0,1,2,3,5,56,534,78,32},
};
for(inti=0;i<arr.length;i++){
System.out.print("數組:");
for(inttemp:arr[i]){
System.out.print(temp+",");
}
System.out.print("中");
System.out.print(hasDuplicatedItem(arr[i])?"存在":"不存在");
System.out.print("重復元素.\n");
}
}
/**
*判斷整形數組中是否有重複數據，時間複雜度為O（n）
*@paramarr
*@return
*/
publicstaticbooleanhasDuplicatedItem(int[]arr){
//掃描數組找最大值
intmax=arr[0];
for(inti=1;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
}
//按最大值創建一個新數組
int[]bitArray=newint[max+1];
//按值向新數組中添值，如value為3則bitArray[3]=1
for(intvalue:arr){
if(bitArray[value]!=0){
//如果value指向的位置已經不是零，說明之前已經給這一塊置1了，立即返回true表示數組有重複
returntrue;
}
else{
//value指向的位置是零,則置為1表示這一位已經有數存在了
bitArray[value]=1;
}
}
returnfalse;
}
}
輸出：
數組:1,2,3,5,3,5,56,534,3,32,中存在重複元素.
數組:1,2,3,5,中不存在重複元素.
數組:1,2,3,5,3,5,中存在重複元素.
數組:0,0,1,2,3,5,56,534,78,32,中存在重複元素.
三、使用點陣圖法進行整形數組排序
packagecom.heyang;
publicclassBitmapSorter{
publicstaticvoidmain(String[]args){
int[]arr={1,7,-3,0,0,6,6,9,-11};
bitmapSort(arr);
for(inti:arr){
System.out.print(i+",");
}
}
/**
*使用點陣圖法進行排序
*@paramarr
*/
publicstaticvoidbitmapSort(int[]arr){
//找出數組中最值
intmax=arr[0];
intmin=max;
for(inti:arr){
if(max<i){
max=i;
}
if(min>i){
min=i;
}
}
//得到點陣圖數組
int[]newArr=newint[max-min+1];
for(inti:arr){
intindex=i-min;
newArr[index]++;
}
//重整arr中的元素
intindex=0;
for(inti=0;i<newArr.length;i++){
while(newArr[i]>0){
arr[index]=i+min;
index++;
newArr[i]--;
}
}
}
}
四、點陣圖法存數據
在8K位元組的記憶體空間內，如何存unsignedshort類型數據？
一般做法：
定義一個數組：unsignedshortarrNormal[4096];
這樣做，最多只能存4K個unsignedshort數據。
利用點陣圖法：
定義一個數組：unsignedchararrBit[8192];
這樣做，能存8K*8=64K個unsignedshort數據。
rrBit存放的位元組位置和位位置（位元組0~8191，位0~7）
比如寫1234，位元組序：1234/8=154;位序：1234&0b111=2，那么1234放在arrBit的下標154位元組處，把該位元組的2號位（0~7）置為1
位元組位置：intnBytePos=1234/8=154;
位位置：intnBitPos=1234&7=2;
//把數組的154位元組的2位置為1
unsignedshortval=1<<nBitPos;
arrBit[nBytePos]=arrBit[nBytePos]|val;//寫入1234得到arrBit[154]=0b00000100
此時再寫入1236，
位元組位置：intnBytePos=1236/8=154;
位位置：intnBitPos=1236&7=4
.///把數組的154位元組的4位置為1
val=1<<nBitPos;
arrBit[nBytePos]=arrBit[nBytePos]|val;//再寫入1236得到arrBit[154]=0b00010100
讀數據元素：按位讀取arrBit，取得位為1的位元組位置和位位置。元素值為8*nBytePos+nBitPos
for(i=0;i<8192;i++)
{
for(j=0;j<8;j++)
{
if(arrBit[i]&(1<<j))
{
cout<<"arrBit:"<<i<<""<<j<<""<<8*i+j<<endl;
}
}
}
會輸出：
arrBit:15421234
arrBit:15441236
刪除元素：計算待刪除元素的位元組位置和位位置：arrBit[nBytePos]&=~(1<<nBitPos);
比如刪除1234：arrBit[154]&=~(1<<2);
