Bitmap算法中文又叫做位圖算法。那么什么是Bitmap算法呢？

位圖算法中的位圖是內存中連續的二進制位(bit)，用于對大量整形數據做去重和查詢。

舉個例子，給定一塊長度是10bit的內存空間，想要依次插入整形數據4，2，1，3。我們需要怎么做呢？

1. 給定長度是10的bitmap，每一個bit位分別對應著從0到9的10個整型數。此時bitmap的所有位都是0。

2. 把整型數4存入bitmap，對應存儲的位置就是下標為4的位置，將此bit置為1。

3. 把整型數2存入bitmap，對應存儲的位置就是下標為2的位置，將此bit置為1。

4. 把整型數1存入bitmap，對應存儲的位置就是下標為1的位置，將此bit置為1。

5. 把整型數3存入bitmap，對應存儲的位置就是下標為3的位置，將此bit置為1。

要問此時bitmap里存儲了哪些元素？顯然是4、3、2、1，一目了然。

Bitmap不僅方便查詢，還可以去除掉重復的整型數。

雖然HashSet和HashMap也同樣能實現用戶的去重和統計，但是如果使用HashSet和HashMap存儲的話，每一個數據比如用戶ID都要存成int，占4字節即32bit。而一個用戶ID在Bitmap中只占一個bit，內存節省了32倍。

不僅如此，Bitmap在做交集和并集運算的時候也有極大的便利。我們來看看下面的例子：

1. 如何查找使用蘋果手機的程序員用戶？

 2. 如何查找所有男性或者00后的用戶？

這就是Bitmap算法的另一個優勢：位運算的高性能。

那么Bitmap這種解決方案這么方便，它有什么缺點沒？

缺點也是存在的，Bitmap不支持[非運算]。比如想要查找不使用蘋果手機的用戶，Bitmap就無能為力了。

現在也有一些開源的Bitmap的實現：

Bitmap和BitSet的關系：JDK中的BitSet集合是對Bitmap相對簡單的實現。

而谷歌開發的EWAHCompressedBitmap則是一種更為優化的實現。

EWAH的意思是Enhanced Word-Aligned Hybrid，在WAH基礎上優化而來。

Bitmap的一個缺點無法進行[非運算]，為什么不能進行非運算呢？

在統計用戶標簽這樣的特定場景下，Bitmap無法[直接]做非運算。為什么呢？看看下面的例子：

我們以下面的用戶數據為例，用戶基本信息如下。按照年齡標簽，可以劃分成90后、00后兩個Bitmap：

用更加形象的表示，90后用戶的Bitmap如下：

這時候可以直接求得非90后的用戶嗎？直接進行非運算？ 

顯然，非90后用戶實際上只有1個，而不是圖中得到的8個結果，所以不能直接進行非運算。

那如果我們一定要求出不屬于某個標簽的用戶數量，該怎么做呢？

這個時候就需要借助一個全量的Bitmap。

同樣是剛才的例子，我們給定90后用戶的Bitmap，再給定一個全量用戶的Bitmap。最終要求出的是存在于全量用戶，但又不存在于90后用戶的部分。

如何求出呢？我們可以使用異或操作，即相同位為0，不同位為1。

Bitmap雖然使用方便，但是如果在一個很長的Bitmap里只存有一兩個用戶，就會很浪費空間。

針對這個問題，在谷歌所實現的EWAHCompressedBitmap中，對Bitmap存儲空間做了一定的優化。

EWAH把Bitmap存儲于long數組當中。long數組的每一個元素都可以當做是64位的二進制數，也是整個Bitmap的子集。谷歌把這些子集叫做[Word]。

當創建一個空的Bitmap時，初始只有4個Word，也即long數組的長度是4。隨著數據的不斷插入，Word數量會隨之擴充。

初始情況由于還未插入任何數據，此時所有的Word值都是0。

EWAH有些Word存儲實際數據，有些Word存儲數據和數據之間的間隔個數，當節點之間跨度很大時，Bitmap不會傻傻把長度擴充到Bitmap的最高位那么多，他會由一個節點專門存儲兩個節點之間的跨度信息，以此達到節省空間的目的。在插入新的數據的時候，如果數據不存放在已有的Word當中，EWAH還會進行動態擴充或對存儲跨度的節點進行分裂。

關于EWAH實現原理的更多信息，可以參考EWAH的算法論文：《Sorting improves word-aligned bitmap indexes》。

EWAHCompressedBitmap對應的maven依賴如下：

<dependency>
  <groupId>com.googlecode.javaewah</groupId>
  <artifactId>JavaEWAH</artifactId>
  <version>1.1.0</version>
</dependency>

關于Bitmap的基礎知識就簡單介紹到這里啦。

參考：程序員小灰—《Bitmap算法 整合版》