轉(zhuǎn)自：https://www.seoxiehui.cn/article-45186-1.html

需求：

　　為滿足用戶標(biāo)簽的統(tǒng)計需求，小灰利用Mysql設(shè)計了如下的表結(jié)構(gòu)，每一個維度的標(biāo)簽都對應(yīng)著Mysql表的一列：要想統(tǒng)計所有90后的程序員該怎么做呢?

兩個月之前——

為滿足用戶標(biāo)簽的統(tǒng)計需求，小灰利用Mysql設(shè)計了如下的表結(jié)構(gòu)，每一個維度的標(biāo)簽都對應(yīng)著Mysql表的一列：

要想統(tǒng)計所有90后的程序員該怎么做呢？

用一條求交集的SQL語句即可：

Select count（distinct Name） as 用戶數(shù) from table whare age = '90后' and Occupation = '程序員' ;

要想統(tǒng)計所有使用蘋果手機(jī)或者00后的用戶總合該怎么做？

用一條求并集的SQL語句即可：

Select count（distinct Name） as 用戶數(shù) from table whare Phone = '蘋果' or age = '00后' ;

兩個月之后——

———————————————

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

2. 把整型數(shù)4存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為4的位置，將此bit置為1。

3. 把整型數(shù)2存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為2的位置，將此bit置為1。

4. 把整型數(shù)1存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為1的位置，將此bit置為1。

5. 把整型數(shù)3存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為3的位置，將此bit置為1。

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

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

1. 建立用戶名和用戶ID的映射：

2. 讓每一個標(biāo)簽存儲包含此標(biāo)簽的所有用戶ID，每一個標(biāo)簽都是一個獨(dú)立的Bitmap。

3. 這樣，實(shí)現(xiàn)用戶的去重和查詢統(tǒng)計，就變得一目了然：

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

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

一周之后......

我們以上一期的用戶數(shù)據(jù)為例，用戶基本信息如下。按照年齡標(biāo)簽，可以劃分成90后、00后兩個Bitmap：

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

這時候可以直接求得非90后的用戶嗎？直接進(jìn)行非運(yùn)算？

顯然，非90后用戶實(shí)際上只有1個，而不是圖中得到的8個結(jié)果，所以不能直接進(jìn)行非運(yùn)算。

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

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

25769803776L = 11000000000000000000000000000000000B

8589947086L = 1000000000000000000011000011001110B

1.解析Word0，得知當(dāng)前RLW橫跨的空Word數(shù)量為0，后面有連續(xù)3個普通Word。

2.計算出當(dāng)前RLW后方連續(xù)普通Word的最大ID是 64 X (0 + 3) -1 = 191。

3. 由于 191 < 400003，所以新ID必然在下一個RLW（Word4）之后。

4.解析Word4，得知當(dāng)前RLW橫跨的空Word數(shù)量為6247，后面有連續(xù)1個普通Word。

5.計算出當(dāng)前RLW（Word4）后方連續(xù)普通Word的最大ID是191 + （6247 + 1）X64 = 400063。

6.由于400003 < 400063，因此新ID 400003的正確位置就在當(dāng)前RLW（Word4）的后方普通Word，也就是Word5當(dāng)中。

最終插入結(jié)果如下：

官方說明如下：

* Though you can set the bits in any order (e.g., set(100), set(10), set(1),* you will typically get better performance if you set the bits in increasing order (e.g., set(1), set(10), set(100)).* * Setting a bit that is larger than any of the current set bit* is a constant time operation. Setting a bit that is smaller than an * already set bit can require time proportional to the compressed* size of the bitmap, as the bitmap may need to be rewritten.

幾點(diǎn)說明：

1. 該項目最初的技術(shù)選型并非Mysql，而是內(nèi)存數(shù)據(jù)庫hana。本文為了便于理解，把最初的存儲方案寫成了Mysq數(shù)據(jù)庫。

1.文中介紹的Bitmap優(yōu)化方法在一定程度上做了簡化，源碼中的邏輯要復(fù)雜得多。比如對于插入數(shù)據(jù)400003的定位，和實(shí)際步驟是有出入的。

2.如果同學(xué)們有興趣，可以親自去閱讀源碼，甚至是嘗試實(shí)現(xiàn)自己的Bitmap算法。雖然要花不少時間，但這確實(shí)是一種很好的學(xué)習(xí)方法。

EWAHCompressedBitmap對應(yīng)的maven依賴如下： <dependency><groupId>com.googlecode.javaewah</groupId><artifactId>JavaEWAH</artifactId><version>1.1.0</version> </dependency>

?

轉(zhuǎn)載于:https://www.cnblogs.com/itplay/p/11089233.html

總結(jié)

以上是生活随笔為你收集整理的【算法】BitMap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。