Bit-map的基本思想就是用一個bit位來标記某個元素對應的Value，而Key即是該元素。由于采用了Bit為機關來存儲資料，是以在存儲空間方面，可以大大節省。（PS：劃重點 節省存儲空間）
假設有這樣一個需求：在20億個随機整數中找出某個數m是否存在其中，并假設32位作業系統，4G記憶體
在Java中，int占4位元組，1位元組=8位（1 byte = 8 bit）
如果每個數字用int存儲，那就是20億個int，因而占用的空間約為 (20000000004/1024/1024/1024)≈*7.45**G
如果按位存儲就不一樣了，20億個數就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.2**33**G
高下立判，無需多言！
那麼，問題來了，如何表示一個數呢？
剛才說了，每一位表示一個數，0表示不存在，1表示存在，這正符合二進制
這樣我們可以很容易表示{1,2,4,6}這幾個數：
計算機記憶體配置設定的最小機關是位元組，也就是8位，那如果要表示{12,13,15}怎麼辦呢？
當然是在另一個8位上表示了：
這樣的話，好像變成一個二維數組了
1個int占32位，那麼我們隻需要申請一個int數組長度為 int tmp[1+N/32] 即可存儲，其中N表示要存儲的這些數中的最大值，于是乎：
tmp[0]：可以表示0~31
tmp[1]：可以表示32~63
tmp[2]：可以表示64~95
。。。
如此一來，給定任意整數M，那麼M/32就得到下标，M%32就知道它在此下标的哪個位置。
添加
這裡有個問題，我們怎麼把一個數放進去呢？例如，想把5這個數字放進去，怎麼做呢？
首先，5/32=0，5%32=5，也是說它應該在tmp[0]的第5個位置，那我們把1向左移動5位，然後按位或
這就相當于 86 | 32 = 118
86 | (1<<5) = 118
b[0] = b[0] | (1<<5)
也就是說，要想插入一個數，将1左移帶代表該數字的那一位，然後與原數進行按位或操作
化簡一下，就是 86 + (5/8) | (1<<(5%8))
是以，公式可以概括為：p + (i/8)|(1<<(i%8)) 其中，p表示現在的值，i表示待插入的數。
清除
以上是添加，那如果要清除該怎麼做呢？
還是上面的例子，假設我們要6移除，該怎麼做呢？
從圖上看，隻需将該數所在的位置為0即可
1左移6位，就到達6這個數字所代表的位，然後按位取反，最後與原數按位與，這樣就把該位置為0了
b[0] = b[0] & (~(1<<6))
b[0] = b[0] & (~(1<<(i%8)))
查找
前面我們也說了，每一位代表一個數字，1表示有（或者說存在），0表示無（或者說不存在）。通過把該為置為1或者0來達到添加和清除的小夥，那麼判斷一個數存不存在就是判斷該數所在的位是0還是1
假設，我們想知道3在不在，那麼隻需判斷 b[0] & (1<<3) 如果這個值是0，則不存在，如果是1，就表示存在。
2、Bitmap有什麼用
大量資料的快速排序、查找、去重。
快速排序
假設我們要對0-7内的5個元素(4,7,2,5,3)排序（這裡假設這些元素沒有重複）,我們就可以采用Bit-map的方法來達到排序的目的。
要表示8個數，我們就隻需要8個Bit（1Bytes），首先我們開辟1Byte的空間，将這些空間的所有Bit位都置為0，然後将對應位置為1。
最後，周遊一遍Bit區域，将該位是一的位的編号輸出（2，3，4，5，7），這樣就達到了排序的目的，時間複雜度O(n)。
優點：
運算效率高，不需要進行比較和移位；
占用記憶體少，比如N=10000000；隻需占用記憶體為N/8=1250000Byte=1.25M
缺點：
所有的資料不能重複。即不可對重複的資料進行排序和查找。
隻有當資料比較密集時才有優勢
快速去重
20億個整數中找出不重複的整數的個數，記憶體不足以容納這20億個整數。
首先，根據“記憶體空間不足以容納這05億個整數”我們可以快速的聯想到Bit-map。下邊關鍵的問題就是怎麼設計我們的Bit-map來表示這20億個數字的狀态了。其實這個問題很簡單，一個數字的狀态隻有三種，分别為不存在，隻有一個，有重複。是以，我們隻需要2bits就可以對一個數字的狀态進行存儲了，假設我們設定一個數字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲空間2G左右。
接下來的任務就是把這20億個數字放進去（存儲），如果對應的狀态位為00，則将其變為01，表示存在一次；如果對應的狀态位為01，則将其變為11，表示已經有一個了，即出現多次；如果為11，則對應的狀态位保持不變，仍表示出現多次。
最後，統計狀态位為01的個數，就得到了不重複的數字個數，時間複雜度為O(n)。
快速查找
這就是我們前面所說的了，int數組中的一個元素是4位元組占32位，那麼除以32就知道元素的下标，對32求餘數（%32）就知道它在哪一位，如果該位是1，則表示存在。
小結&回顧
Bitmap主要用于快速檢索關鍵字狀态，通常要求關鍵字是一個連續的序列（或者關鍵字是一個連續序列中的大部分）， 最基本的情況，使用1bit表示一個關鍵字的狀态（可标示兩種狀态），但根據需要也可以使用2bit（表示4種狀态），3bit（表示8種狀态）。
Bitmap的主要應用場合：表示連續（或接近連續，即大部分會出現）的關鍵字序列的狀态（狀态數/關鍵字個數 越小越好）。
32位機器上，對于一個整型數，比如int a=1 在記憶體中占32bit位，這是為了友善計算機的運算。但是對于某些應用場景而言，這屬于一種巨大的浪費，因為我們可以用對應的32bit位對應存儲十進制的0-31個數，而這就是Bit-map的基本思想。Bit-map算法利用這種思想處理大量資料的排序、查詢以及去重。
補充1
在數字沒有溢出的前提下，對于正數和負數，左移一位都相當于乘以2的1次方，左移n位就相當于乘以2的n次方，右移一位相當于除2，右移n位相當于除以2的n次方。
<< 左移，相當于乘以2的n次方，例如：1<<6 相當于1×64=64，3<<4 相當于3×16=48
>> 右移，相當于除以2的n次方，例如：64>>3 相當于64÷8=8
^ 異或，相當于求餘數，例如：48^32 相當于 48%32=16
補充2
不使用第三方變量，交換兩個變量的值
1 // 方式一
2 a = a + b;
3 b = a - b;
4 a = a - b;
5
6 // 方式二
7 a = a ^ b;
8 b = a ^ b;
9 a = a ^ b; 3、BitSet
BitSet實作了一個位向量，它可以根據需要增長。每一位都有一個布爾值。一個BitSet的位可以被非負整數索引（PS：意思就是每一位都可以表示一個非負整數）。可以查找、設定、清除某一位。通過邏輯運算符可以修改另一個BitSet的内容。預設情況下，所有的位都有一個預設值false。
可以看到，跟我們前面想的差不多。
用一個long數組來存儲，初始長度64，set值的時候首先右移6位（相當于除以64）計算在數組的什麼位置，然後更改狀态位
别的看不懂不要緊，看懂這兩句就夠了：
1 int wordIndex = wordIndex(bitIndex);
2 words[wordIndex] |= (1L << bitIndex); 4、Bloom Filters
Bloom filter 是一個資料結構，它可以用來判斷某個元素是否在集合内，具有運作快速，記憶體占用小的特點。
而高效插入和查詢的代價就是，Bloom Filter 是一個基于機率的資料結構：它隻能告訴我們一個元素絕對不在集合内或可能在集合内。
Bloom filter 的基礎資料結構是一個 比特向量（可了解為數組）。
主要應用于大規模資料下不需要精确過濾的場景，如檢查垃圾郵件位址，爬蟲URL位址去重，解決緩存穿透問題等
如果想判斷一個元素是不是在一個集合裡，一般想到的是将集合中所有元素儲存起來，然後通過比較确定。連結清單、樹、散清單（哈希表）等等資料結構都是這種思路，但是随着集合中元素的增加，需要的存儲空間越來越大；同時檢索速度也越來越慢，檢索時間複雜度分别是O(n)、O(log n)、O(1)。
布隆過濾器的原理是，當一個元素被加入集合時，通過 K 個散列函數将這個元素映射成一個位數組（Bit array）中的 K 個點，把它們置為 1 。檢索時，隻要看看這些點是不是都是1就知道元素是否在集合中；如果這些點有任何一個 0，則被檢元素一定不在；如果都是1，則被檢元素很可能在（之是以說“可能”是誤差的存在）。
BloomFilter 流程
首先需要 k 個 hash 函數，每個函數可以把 key 散列成為 1 個整數；
初始化時，需要一個長度為 n 比特的數組，每個比特位初始化為 0；
某個 key 加入集合時，用 k 個 hash 函數計算出 k 個散列值，并把數組中對應的比特位置為 1；
判斷某個 key 是否在集合時，用 k 個 hash 函數計算出 k 個散列值，并查詢數組中對應的比特位，如果所有的比特位都是1，認為在集合中。
1 <dependency>
2 <groupId>com.google.guava</groupId>
3 <artifactId>guava</artifactId>
4 <version>28.1-jre</version>
5 </dependenc