什麼是Bitmap
所謂的BitMap就是用一個bit位來标記某個元素所對應的value，而key即是該元素，由于BitMap使用了bit位來存儲資料，是以可以大大節省存儲空間。
重要特性
1.存儲空間小
由于Bitmap是通過bit來辨別狀态，資料将會高度壓縮是以占用存儲空間極小，存儲變小也可以帶來很多其它性能紅利，如：記憶體、磁盤IO、網絡帶寬等。
如果用int類型表示一個整數，占用空間為（4byte = 32bit）。若用bitmap表示一個整數，占用空間為1bit。 記憶體節省了32倍。假設需要對10億個整數進行排序（10億個資料不重複，且範圍在0 ~ 2^32）
如果用int類型表示需要占用空間：3.72G 左右
如果用bitmap類型表示需要占用空間：510MB 左右
如果bitmap加上對應的壓縮算法roaringbitmap： 360MB 左右
2.計算速度快
由于BitMap是通過bit位來表示的，是以後面的計算都是基于位運算的，速度都會得到大幅度提升。
基本思想
我們用一個具體例子來說明Bitmap的原理。假設我們要對0-7内的8個元素中的(6,2,7,1)四個元素進行排序(這裡假設元素沒有重複)。我們可以使用Bitmap算法達到排序目的。
1.開辟1 Byte空間（要表示8個數，我們需要8個bit（1Byte）），将這些空間所有的bit都設定為0，如下圖：
2.然後依次将四個元素根據Value的值将對應的bit位置設定為 1，最終8個bit位狀态如下圖：
3.現在我們周遊一次，把值為1的bit的位置輸出(1,2,6,7)，這樣便達到了排序的目的。
從上面的例子我們可以看出，BitMap算法的思想還是比較簡單的，關鍵的問題是如何确定10進制的數到2進制的映射圖，接下來我們研究一下map映射。
注意：由于BitMap是用角标來記錄對應的值，而角标是從0開始計數的，是以普通的BitMap隻适用于非負數的排序或者去重操作。
MAP映射
BitMap中1bit代表一個數字，1個int = 4Bytes = 4*8bit = 32 bit，假設現有N個非負整數，取值範圍[0,N-1]，那麼N個數需要N/32 int空間，其中：a[0]在記憶體中占32為可以對應十進制數0-31，依次類推如下圖：
a[0]--------->[0]~[31] ->bit表示[0000000000000000000000000000000000000]
a[1]--------->[32]~[63] ->bit表示[0000000000000000000000000000000000000]
a[2]--------->[64]~[95] ->bit表示[0000000000000000000000000000000000000]
.
.
.
.
.
a[n]--------->[N-32]~[N-1]
說明：n = (N/32) - 1
注意：這裡需要提醒一下，a數組的size是由待排序數中的最大值決定，而不是待排序數個數決定的。例如：待排序數組是[3，1，35]，這個數組隻有三個數字，但是在開辟BitMap空間時應該根據最大值35，是以需要開辟2個int空間，這個地方大家可以思考一下。自己在學習過程中，發現網絡上多篇文章在這個地方都是錯誤的，是以特意提醒！
接下來介紹如何用位運算将十進制數轉換為對應的bit位：
1.求十進制數在對應數組a中的下标
十進制數0-31，對應在數組a[0]中，32-63對應在數組a[1]中，64-95對應在數組a[2]中………，使用數學歸納分析得出結論：對于一個十進制數n，其在數組a中的下标為：a[n/32]
2.求出十進制數在對應數a[i]中bit位的下标
例如十進制數1在a[0]的bit位下标為1，十進制數31在a[0]的bit位下标為31，十進制數32在a[1]的bit位下标為0。十進制0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得在對應數組a[i]中的bit位下标。
3.位移運算
對于一個十進制數n,對應在數組a[n/32][n%32]中，但數組a畢竟不是一個二維數組，我們通過移位操作實作将對應的bit位置 1。
位運算公式：a[n/32] |= 1 << (n % 32)，即 a[n/32] = a[n/32] ｜(1 << (n % 32))
公式還有一個可以優化的地方，n % 32 等價于 n & 0x1F，解釋：(n & 0x1F) 保留n的後五位 相當于 n % 32
至此，整個MAP映射過程結束。需要注意的是，本示例中底層使用的存儲是int[]，如果換做其它類型數組，如：long，則對應公式需要做相應調整。
代碼實作
根據上面介紹的算法原理，代碼實作如下：
package com.zhouj.endless.ds;
import java.util.ArrayList;
import java.util.List;
/**
* @author zhouj
* @date 2021-07-20 22:28
* @desc BitMap實作
*/
public class BitMap {
// 最大值
private static final int N = Integer.MAX_VALUE;
// [0,2147483647]
private int[] a = new int[N / 32 + 1];
/**
* 設定bit位為1
*
* @param n
*/
public void setBit(int n) {
//row = n / 32 求十進制數在數組a中的下标
int row = n >> 5;
//相當于 n % 32 求十進制數在數組a[i]中的下标
a[row] |= 1 << (n & 0x1F);
}
// 判斷所在的bit為是否為1
public boolean exits(int n) {
int row = n >> 5;
return (a[row] & (1 << (n & 0x1F))) != 0;
}
/**
* 展示前row個數組
*
* @param row
*/
public void display(int row) {
System.out.println("BitMap位圖展示前N組");
for (int i = 0; i < row; i++) {
List<Integer> list = new ArrayList<>();
int temp = a[i];
for (int j = 0; j < 32; j++) {
list.add(temp & 1);
temp >>= 1;
}
System.out.println("a[" + i + "]--------->" + 32 * i + "~" + (32 * (i + 1) - 1) + "->bit表示" + list);
}
}
/**
* 展示第N個數組
*
* @param n
*/
public void displayN(int n) {
System.out.println("BitMap位圖展示第N組");
List<Integer> list = new ArrayList<>();
int temp = a[n - 1];
for (int j = 0; j < 32; j++) {
list.add(temp & 1);
temp >>= 1;
}
System.out.println("a[" + (n - 1) + "]--------->" + 32 * (n - 1) + "~" + (32 * n - 1) + "->bit表示" + list);
}
public static void main(String[] args) {
int num[] = {1, 5, 30, 31, 64, 56, 159, 120, 21, 17, 35, 45, Integer.MAX_VALUE};
BitMap map = new BitMap();
for (int i = 0; i < num.length; i++) {
map.setBit(num[i]);
}
map.display(6);
int temp = Integer.MAX_VALUE;
if (map.exits(temp)) {
System.out.println("temp:" + temp + " exists");
}
map.displayN(Integer.MAX_VALUE / 32 + 1);
}
}
運作結果如下：
本文給出的隻是BitMap原來簡單實作，在實際應用中有更複雜的情況。JDK中，是直接提供的BitMap集合的實作類的：java.util.BitSet，有興趣的可以去研究一下。另外介于篇幅原因，針對BitMap的應用将在下一篇文章進行介紹和分析。
感謝閱讀！