所謂bitmap，就是用每一位來存放某種狀态，适用于大規模資料，但資料狀态又不是很多的情況。通常是用來判斷某個資料存不存在的。
設計原則：
盡可能的最大化利用記憶體，極限挖掘、利用、發揮Java的性能。
設計思路：
使用long型數組來用作存儲，
故位圖Bitmap類的大小size使用long型（int型不夠極限），是以理論上0<=size<=2^63-1；
又Java數組的長度最長為2^31-1（即int型字面量最大值），是以long類型的數組最多可以存儲64*(2^31-1)個點（以隻有兩種狀态的點來計算，即1bit表示一個點的狀态），是以Bitmap的size不可能大于64*(2^31-1)，故實際0<=size<=64*(2^31-1)；
再繼續分析位圖中每個點不可能隻有兩種狀态，是以需要設計出來的Bitmap可以自定義點的狀态數量state，即1<state<=2^63-1（大于1是因為狀态不可能隻有1種，隻有一種的話使用位圖就失去了意義，小于等于2^63-1是因為2^63-1是long型字面量最大值，沒有比該值還要大的整數值，符合宗旨：探索挖掘Java的極限使用）;
此外自定義的點的狀态數量需要使用多少位數來表示也是一個問題，自定義點的狀态數量位數stateBitNum=（state的二進制表示的位數）
（
先做簡單推導：
2種狀态需要1bit，[0,1]
3~4種狀态需要2bit，[00,01,10,11]
5~8種狀态需要3bit，[000,001,010,011,100,101,110,111]
9~16種狀态需要4bit，[...,...]
這裡給出計算公式：stateBitNum=64 - Long.numberOfLeadingZeros(state - 1)；
Long.numberOfLeadingZeros(long i)方法是計算i的補碼形式最高位的1的左面的0的數量，
也就是補碼中從左往右數0的個數，數到第一個非0的位置停止，0的數量即為該方法的傳回值，舉例：Long.numberOfLeadingZeros(2)=62，2的補碼為10，故用64位補碼（因為i是long型的）表示10前面還有62個0；是以64- Long.numberOfLeadingZeros(2)=2，而2種狀态（state=2）其實隻要用1位表示，是以state再傳入該方法時要減一（因為0本身在計算機中就可以表示一種狀态，比如8種狀态可以用數字0~7來表示一樣）；
再繼續深挖會發現64位其實可以表示2^64種狀态，但是Java的最大字面量值為2^63-1，是以最大狀态數量state=2^63-1種狀态需要63位儲存，一個long型足以，這裡還有一個坑Long.numberOfLeadingZeros(0)=64，但是我們在使用時不可能出現這種情況因為state最小為2，state-1最小為1，避免了這種情況；
至此結束！
）；
其餘Bitmap的各種操作，實作時說明。
實作：
/**
* 位圖類：
* 1.最多可以儲存（2^37-2^6）個2種狀态值的點;
* 2.理論上有（2^37-2^6）個位空間，實際上可能不能完全使用（見無參構造器中的介紹），
* 故使用時所選的點的狀态值種數（stateNum）最好滿足 64% ⌈ log2(stateNum) ⌉ = 0，即stateNum的補碼的位數正好是64的因數；（聽不明白的話，自行體會）
* 3.沒有删除點的方法，隻有增加，更新，查找操作；（問為什麼沒有删除方法的人不是腦子有病，就是腦子有病。。。）
* 4.回答3中問題：首先不是實作不了，是沒有必要，因為删除一個點需要在數組中通過移位來填充被删除的位置，由于資料量過大可能會極其浪費時間，
* 而且位圖本身存在的意義是表示海量資料中每一條資料的可能性，對于海量資料而言，出現極個别錯誤并不會影響其最終統計結果（對于偷跑，出錯的資料仍然可以在下一層中進行重新過濾，要是聽不懂就算了。。。），
* 這裡建議使用update方法将不需要的點置0，用于表示該點被棄用，具體的邏輯需要使用者自己去編輯；
* 5.該類所花費的理論持久存儲空間大約為260MB也就是elementData數組的大小的極限值，實際可能會多一點，但幾乎可以忽略不計，最終實作存儲2種狀态值的點的數量大約20億個，
* 也可以自定義每個點的狀态值種數stateNum和點的數量length最大可以設定成（2^63-1）個，但最終要滿足 length > ⌈ log2(stateNum) ⌉（向上取整） / 64 * Integer.MAX_VALUE，
* 對于日常使用一定是足夠的；（在這裡，總有杠精會問超過了怎麼辦？就算是2種狀态值的點有20億個話，我還是不夠用啊？）
* 6.回答5中的問題：你不會搞個數組嗎？你不能多new幾個一起用嗎！！！
*/
public class Bitmap {
/*
*使用long型數組儲存點
*/
private final long[] elementData;
/*
* 位圖中能存儲的所有點的位數之和的最大值MAX_STATE_SIZE=137,438,953,408；
* 64（MAX_STATE_SIZE=long類型的位數） * 0x7fffffff（int類型的最大值Integer.MAX_VALUE）= MAX_STATE_SIZE （2^37-2^6）
*/
// private static final long MAX_STATE_SIZE = 0x1fffffffc0L;//結果沒用上，大意了。。。
/*
位圖儲存的點的狀态種數
*/
private final long stateNum;
/*
存儲一個位圖儲存的點的狀态值所需要的位數
*/
private final int stateBitNum;
/*
位圖可以儲存的最大點數，初始化Bitmap類時指定
*/
private final long MAX_SIZE;
/*
一個long型變量可以儲存的點的數量
*/
private final long numOfOneLong;
/*
該位圖已經儲存的點的數量
*/
private long size;
/**
* @param stateNum 位圖中點的狀态數量,state>1
* @param length 位圖大小,0<length
* 如果 length > ⌈ log2(stateNum) ⌉（向上取整） / 64 * Integer.MAX_VALUE，則說明該 Bitmap 類無法儲存 length 個 stateNum 種數的點，抛出異常
*/
public Bitmap(long stateNum, long length) {
if (stateNum > 1 && length > 0) {
/*
計算狀态值需要多少位來表示
*/
stateBitNum = 64 - Long.numberOfLeadingZeros(stateNum - 1);
/*
計算一個long型裡面最多可以存放幾個狀态值，
如果不能整除的話，就舍棄餘下位數，
因為在數組中跨元素進行位值的存取計算極其複雜，故舍棄部分位空間，友善位圖的各項操作
*/
numOfOneLong = 64 / stateBitNum;
/*
一個long型最多可以存儲numOfOneLong個狀态值，
是以該位圖最大能存取numOfOneLong*Integer.MAX_VALUE個點，
如果需要存儲的數量length大于位圖的最大存儲數（numOfOneLong*Integer.MAX_VALUE）就說明該類Bitmap無法滿足要求，抛出異常
*/
if (length > numOfOneLong * Integer.MAX_VALUE)
throw new RuntimeException("初始化的位圖過大，無法存儲！！！");
this.stateNum = stateNum;
MAX_SIZE = length;
if (length % numOfOneLong == 0)
elementData = new long[(int) (length / numOfOneLong)];
/*
如果length個點不能被數組正好放下，就需要多添加一個數組元素來存儲點
*/
else elementData = new long[((int) (length / numOfOneLong)) + 1];
} else
throw new RuntimeException("位圖類的初始化傳入參數值中沒有負整數！！！");
}
/**
* 順序添加點
*
* @param state 點的狀态
* @return true表示添加成功，産生false的情況有：位圖滿了；狀态值越界
*/
public boolean add(long state) {
if (state > stateNum - 1 || state < 0 || size == MAX_SIZE)
return false;
int index = (int) (size / numOfOneLong);
int left = (int) (size % numOfOneLong);
elementData[index] |= state << (64 - stateBitNum * (1 + left));
++size;
return true;
}
public long find(long index) {
if (index < 0 || index > size - 1)
return -1;
/*
計算數組中哪一個元素儲存着index索引對應的點
*/
int arrayIndex = (int) (index / numOfOneLong);
/*
計算元素中從哪一位開始的位儲存着index索引對應的點
*/
int elementIndex = (int) (index % numOfOneLong);
/*
通過左移，清空掉左邊無用的位，再通過無符号右移清空掉右邊無用的位，最終正好是需要查找的index位置對應的state值
*/
return elementData[arrayIndex] << (stateBitNum * elementIndex) >>> (64 - stateBitNum);
}
public boolean update(long index, long state) {
if (index < 0 || index > size - 1 || state > stateNum - 1 || state < 0)
return false;
int arrayIndex = (int) (index / numOfOneLong);
int left = (int) (index % numOfOneLong);
elementData[arrayIndex] |= state << (64 - stateBitNum * (1 + left));
return true;
}
/**
* 傳回位圖中點的狀态數量
*/
public long getStateNum() {
return stateNum;
}
/**
* 傳回位圖可以存儲的點的最大數量
*/
public long getMaxSize() {
return MAX_SIZE;
}
/**
* 傳回位圖中實際已使用的數量
*/
public long getSize() {
return size;
}
/**
* 輔助toString()方法，主要用于列印位圖的具體顯示
*/
private String elementDataToString() {
StringBuilder result = new StringBuilder("[\n");
for (long element : elementData) {
String eleString = Long.toBinaryString(element);
StringBuilder one = new StringBuilder();
for (int i = 0; i < 64 - eleString.length(); i++)
one.append("0");
one.append(eleString);
for (int i = 0; i < numOfOneLong + 1; i++)
one.insert((stateBitNum + 1) * i, ',');
result.append(one.substring(1, one.lastIndexOf(","))).append(",\n");
}
return result.append("]").toString();
}
@Override
public String toString() {
return "Bitmap{\n" +
"elementData=" + elementDataToString() +
", \nstateNum=" + stateNum +
", \nstateBitNum=" + stateBitNum +
", \nMAX_SIZE=" + MAX_SIZE +
", \nsize=" + size +
"\n}";
}
}
測試：
public class test {
public static void main(String[] args) {
Bitmap bitmap = new Bitmap(16, 10);
System.out.println(bitmap.add(2));
System.out.println(bitmap.add(3));
System.out.println(bitmap.add(4));
System.out.println(bitmap.add(5));
System.out.println(bitmap);
System.out.println(bitmap.update(3, 7));
System.out.println(bitmap);
System.out.println(bitmap.find(3));
}
}
總結：
位圖類： 1. 最多可以儲存（2^37-2^6）個2種狀态值的點; 2. 理論上有（2^37-2^6）個位空間，實際上可能不能完全使用（見無參構造器中的介紹），故使用時所選的點的狀态值種數（stateNum）最好滿足 64% ⌈ log2(stateNum) ⌉ = 0，即stateNum的補碼的位數正好是64的因數；（聽不明白的話，自行體會） 3. 沒有删除點的方法，隻有增加，更新，查找操作；（問為什麼沒有删除方法的人不是腦子有病，就是腦子有病。。。） 4. 回答3中問題：首先不是實作不了，是沒有必要，因為删除一個點需要在數組中通過移位來填充被删除的位置，由于資料量過大可能會極其浪費時間，而且位圖本身存在的意義是表示海量資料中每一條資料的可能性，對于海量資料而言，出現極個别錯誤并不會影響其最終統計結果（對于偷跑，出錯的資料仍然可以在下一層中進行重新過濾，要是聽不懂就算了。。。），這裡建議使用update方法将不需要的點置0，用于表示該點被棄用，具體的邏輯需要使用者自己去編輯； 5. 該類所花費的理論持久存儲空間大約為260MB也就是elementData數組的大小的極限值，實際可能會多一點，但幾乎可以忽略不計，最終實作存儲2種狀态值的點的數量大約20億個，也可以自定義每個點的狀态值種數stateNum和點的數量length最大可以設定成（2^63-1）個，但最終要滿足 length > ⌈ log2(stateNum) ⌉（向上取整）/ 64 * Integer.MAX_VALUE，對于日常使用一定是足夠的；（在這裡，總有杠精會問超過了怎麼辦？就算是2種狀态值的點有20億個話，我還是不夠用啊？） 6. 回答5中的問題：你不會搞個數組嗎？你不能多new幾個一起用嗎！！！