位圖—BitMap和BitSet，布隆過濾器，Roaring Bitmap

位圖

簡單來說就是為了壓縮節省空間，才出現的。
           

舉個例子：

你要是存儲三個數字 2,5,10。這三個數字用java中的short類型來存儲，也要6個Byte（short類型的記憶體空間是2Byte）。一個Byte是8bit，一共占用是64bit。我們知道bit的取值非0即1.

如果我用bit來表示這三個數字呢？

0010010000100000

從0開始，對應的位置上放1，這樣16個bit就能表示這三個數字了，一共占用記憶體2byte。
           

比起上面的6Byte,用bit這樣表示2byte可節省了不少空間。

BitMap

為什麼叫BitMap呢？

我們知道Map類型的資料結構是key-value類型的，這裡的BitMap也是這樣的，比如我們在BitMap裡面
	
	存儲一個2，這個2就是key，value就是對應的bit位上的0或者1，這就是BitMap。	
           

BitSet

為什麼叫BitSet呢？

我們知道Set在我們眼裡是去重的類似于list的結構，沒錯這裡也是這個意思，比如一組數字2，3，2，5，7
	
	存儲第一個2的時候，對應的bit位已經置為1了，再去存儲第二個2的時候對應的bit位已經是1了，
	
	這樣就去重了。而且java中BitSet就是BitMap的實作。為什麼不是兩個類呢？我想了一下，因為一個BitSet
	
	就已經具備這兩個的功能了。你想想是不是。
           

拓展

其實基于BitMap的變型有很多，比如布隆過濾器，

布隆過濾器

主要目的是去重。主要思想是根據多個Hash函數,根據Hash出來的結果(hash函數結果一般是Integer)将對應位置的bit置為1，舉個例子：

比如重複過濾字元串“中國人牛逼”，幾個Hash函數的結果分别是67829，23424，,575675，就将對應的
		
		位置bit置為1，然後再過濾到“中國人牛逼”的時候，發現67829，23424，,575675對應的位置的bit
		
		已經是1了，就認為已經存在了，這樣就去重了，
           

從上面的原理我們可以知道，這個會存在誤判重，布隆過濾器的效果好不好，

主要取決于選的Hash函數的散列效果，不然如果hash函數的散列效果比較差，主要集中在某一段取值上，這樣很快就會把這一段位置的bit置為1，然後後面來的都會被認為重複，即是bit數組再大也沒效果。

還有就是bit數組的大小，不然Hash函數散列效果再好，數組太小，也會出現上面的問題。

Roaring Bitmap

Roaring Bitmap算是對BitMap的優化，怎麼優化呢？舉個例子：

我現在隻要存儲兩個數字0, 8388607這要是按照上面的BitMap去存儲的話，這就需要一個

8388608個bit大的數組，也就是1M，我日，存儲兩個數字要用1M的記憶體，可見

BitMap有時候效率并不高，于是乎就出現了各種版本的優化，這裡就出現了Roaring Bitmap。
           

Roaring Bitmap下文簡稱RBM，不是RMB

原理也很簡單，RBM将一個Integer類型的數字分類高16位和低16位，我們知道16位的最大值是2^16，
	
	然後建立一個2^16的數組，數組的類型是Container，Container又分為不同的類型，
	
	先說為什麼分為2^16個數組長度，一個Integer類型的數字，除以2^16得到的商和餘數分别對應這個
	
	Integer高16位和低16位對應的值。是以當一個數存儲到RMB的時候，就會那這個數除以2^16，
	
	然後根據商找到數組中對應下标的Container，然後在将餘數放到Container中，這樣就完成了

	一個Integer的存儲。
           

上面大緻介紹了RBM的原理，但是一直沒有介紹他的Container，相比于BitMap，Container也是新增的概念，可見優化的點就在這個Container上，下面我們詳細介紹一下這個Container。

Container 主要有兩種：
	
	一種是ArrayContainer主要存放稀疏資料，它的資料結構是Short類型的數組，可以動态擴容，

	最大容量為4096，當超過4096則轉換成BitContainer，而且數組是有序的可以通過二分法快速定位到。
	
	另一種是BitContainer主要存放稠密資料，資料結構是Long型的數組，切容量恒定為1024，存儲方式

	像上面的BitMap一樣，查找定位可以直接定位，如果對應的bit是1，就是存在。
           

為什麼ArrayContainer的資料類型是Short？

因為Container裡面存儲的是餘數，餘數最大就是2^16,剛好在short範圍内。

為什麼BitContainer是恒定的Long型1024長度的數組？

因為是按照BitMap的形式操作的，Long型是64bit，1024長度的Long型數組，剛好有2^16個bit，

餘數最大剛好是2^16。能容下所有的數。

為什麼大于ArrayContainer容量大于4096轉換成BitContainer？

因為BitContainer是Long型1024長度的恒容數組，也就是記憶體占用是8Byte*1024 = 8KB，ArrayContainer short類型4096容量時，占用的記憶體 2Byte * 4096 =8KB，是以當ArrayContainer 容量超過4096占用的記憶體就會大于8KB，就不劃算了，是以就會轉換成永遠不會變的BitContainer的8KB