演算法—BitMap
問題：
假設有3億個整數（範圍0-2億），如何判斷某一個樹是否存在。局限條件一台機器，記憶體500m。
常規的思路：我們可以將數據存到一個集合中，然後判斷某個數是否存在；或者用一個等長的數組來表示，每個數對應的索引位置，存在就標記為1，不存在0。當然如果設備條件允許，上面的這方案是可行的。
但是現在我們記憶體只有500m。Int類型4個位元組。
單單是這3億個數都已經：300000000*4/1024/1024 差不多1144m了。顯然已經遠超過記憶體限制了。
顯然在這種條件下面，我們想要將這些書完整的存儲下來已經是不現實的。只有另尋他經。
上面的第二種方案中提供一個很好思路，用標記來標註。我們只有尋求記憶體佔用更小的數據類型來標記了，1int=4byte，1byte = 8bit
如果我們用bit來打標記。就不可以很好的縮小記憶體佔用了嘛。1int=4byte，如果用bit那麼記憶體佔用就會縮小32倍，1144/32大概36m就可以了。
也就是說其實我們的一個int位置，可以表示32個數據存在與否。
Int 1的二進位完整表示：0000 0000 0000 0000 0000 0000 0000 0001，它是有32位，只不過平時前面的0都是沒有顯示的
我們聲明一個int類型的標記數組：flag[2億/32 +1]，數組長度2億/32 +1，就可以了，為什麼是2億/32，不是3億呢，因為這3億個數的範圍就是0-2億，所以我們的標記數組最大只需要對應2億即可。有的數，就將其標記為1。就是說數組的沒一個元素其實包含了32個數存在與否。
Flag[0] —>0-31
Flag[1] —>32-63
Flag[2] —>64-95
Flag[3] —>96-127
…….
我們怎麼來操作這個int類型裡面的32位呢，這就要用到我們的位運算：
<<：左移
>>：右移
&：同位上的兩個數都是1則位1，否則為0
|：同為上的兩個數只要有一個為1 則為1，否則為0
我們怎麼找到某個數的標記在數組的索引及其值的多少位呢？
假設3這個數
Index = 3 / 32 = 0
Location = 3 % 32 = 3
3的標記應該在flag[0] 的第三個位置，將其置為1：
flag[0] |= 1 << Location (位或是不會影響其他位置1的標記)
原本的flag[0] 0000 0000 0000 0000 0000 0000 0000 0011 原本已經有了0和1
| 0000 0000 0000 0000 0000 0000 0000 1000 1 << Location 之後的
得到： 0000 0000 0000 0000 0000 0000 0000 1011 現在有0,1,3了
這樣就可以所有的數據標記給保存下來了。
那麼判斷的時候怎麼判斷呢。
同理先找到某個數精確位置
還是3
Index = 3 / 32 = 0
Location = 3 % 32 = 3
現在我們的flag[0] -> 0000 0000 0000 0000 0000 0000 0000 1011
Exist = flag[0] & (1 << Location) != 0 &：相同位上的兩個數都是1則位1，否則為0
0000 0000 0000 0000 0000 0000 0000 1011
& 0000 0000 0000 0000 0000 0000 0000 1000
0000 0000 0000 0000 0000 0000 0000 1000
&運算之後結果不為0說明該數存在。
大致的思路就是這個樣子，下面用程式碼實現上述邏輯
package com.nijunyang.algorithm.math; /** * Description: * Created by nijunyang on 2020/5/5 22:33 */ public class BitMap { /** * 範圍中最大的那個數 */ private int max; private int[] flag; public BitMap(int max) { this.max = max; flag = new int[max >> 5 + 1]; //除以32也可以表示為>>5 } /** * 添加數據標記 * @param val */ public void put(int val) { //往bitmap裡面添加數字 int index = val / 32; // 計算數組索引位置 int location = val % 32; // 計算在32位int中的位置 flag[index] |= 1 << location; //標記位改成1 } /** * 判斷是否存在 * @param val * @return */ public boolean exist(int val) { int index = val / 32; int location = val % 32; int result = flag[index] & (1 << location); return result != 0; } /** * 移除標記 * @param val * @return */ public void remove(int val) { int index = val / 32; int location = val % 32; System.out.println(Integer.toBinaryString(flag[index])); flag[index] = flag[index] &~ (1 << location); //~取反1變0 0變1 System.out.println(Integer.toBinaryString(flag[index])); } public static void main(String[] args) { BitMap bitMap = new BitMap(200_000_000); bitMap.put(128); bitMap.put(129); System.out.println(bitMap.exist(127)); System.out.println(bitMap.exist(128)); bitMap.remove(128); System.out.println(bitMap.exist(128)); } }
雖然說用bitMap的這種思想可以解決上面的這個問題，但是它還是有缺點的，我們上面用的數字，如果是其他類型可能就需要hash之後得到hashcode再進行這個操作，對於hash衝突是無法解決的。因為標記只有0和1。數據量少的時候相對於普通的hash集合操作並沒有優勢。它對於那種數據量很大，且數據相對密集的，因為數組的長度是和最大的數據值有關，而不是和集合容量有關。
布隆過濾器就使用bitMap的思想。不過它同時會使用集中hash演算法來計算hashcode，來盡量解決hash衝突。Redis快取設計與性能優化 中有簡單的介紹。
JDK中也有一個BitSet類。
