牛逼哄哄的 BitMap，到底牛逼在哪？

作者：廢物大師兄
來(lái)源：www.cnblogs.com/cjsblog/p/11613708.html

1、BitMap

Bit-map的基本思想就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value，而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。（PS：劃重點(diǎn) 節(jié)省存儲(chǔ)空間）

假設(shè)有這樣一個(gè)需求：在20億個(gè)隨機(jī)整數(shù)中找出某個(gè)數(shù)m是否存在其中，并假設(shè)32位操作系統(tǒng)，4G內(nèi)存

在Java中，int占4字節(jié)，1字節(jié)=8位（1 byte = 8 bit）

如果每個(gè)數(shù)字用int存儲(chǔ)，那就是20億個(gè)int，因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45G

如果按位存儲(chǔ)就不一樣了，20億個(gè)數(shù)就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.2****33G

高下立判，無(wú)需多言！

那么，問(wèn)題來(lái)了，如何表示一個(gè)數(shù)呢？

剛才說(shuō)了，每一位表示一個(gè)數(shù)，0表示不存在，1表示存在，這正符合二進(jìn)制

當(dāng)然是在另一個(gè)8位上表示了：

這樣的話，好像變成一個(gè)二維數(shù)組了

1個(gè)int占32位，那么我們只需要申請(qǐng)一個(gè)int數(shù)組長(zhǎng)度為 int tmp[1+N/32] 即可存儲(chǔ)，其中N表示要存儲(chǔ)的這些數(shù)中的最大值，于是乎：

tmp[0]：可以表示0~31

tmp[1]：可以表示32~63

tmp[2]：可以表示64~95

。。。

如此一來(lái)，給定任意整數(shù)M，那么M/32就得到下標(biāo)，M%32就知道它在此下標(biāo)的哪個(gè)位置。

添加

這里有個(gè)問(wèn)題，我們?cè)趺窗岩粋€(gè)數(shù)放進(jìn)去呢？例如，想把5這個(gè)數(shù)字放進(jìn)去，怎么做呢？

首先，5/32=0，5%32=5，也是說(shuō)它應(yīng)該在tmp[0]的第5個(gè)位置，那我們把1向左移動(dòng)5位，然后按位或

86 | (1<<5) = 118

b[0] = b[0] | (1<<5)

也就是說(shuō)，要想插入一個(gè)數(shù)，將1左移帶代表該數(shù)字的那一位，然后與原數(shù)進(jìn)行按位或操作

化簡(jiǎn)一下，就是 86 + (5/8) | (1<<(5%8))

因此，公式可以概括為：p + (i/8)|(1<<(i%8)) 其中，p表示現(xiàn)在的值，i表示待插入的數(shù)。

清除

以上是添加，那如果要清除該怎么做呢？

1左移6位，就到達(dá)6這個(gè)數(shù)字所代表的位，然后按位取反，最后與原數(shù)按位與，這樣就把該位置為0了

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

查找

前面我們也說(shuō)了，每一位代表一個(gè)數(shù)字，1表示有（或者說(shuō)存在），0表示無(wú)（或者說(shuō)不存在）。通過(guò)把該為置為1或者0來(lái)達(dá)到添加和清除的小伙，那么判斷一個(gè)數(shù)存不存在就是判斷該數(shù)所在的位是0還是1。

假設(shè)，我們想知道3在不在，那么只需判斷 b[0] & (1<<3) 如果這個(gè)值是0，則不存在，如果是1，就表示存在。

2、Bitmap有什么用

大量數(shù)據(jù)的快速排序、查找、去重。

快速排序

假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒(méi)有重復(fù)）,我們就可以采用Bit-map的方法來(lái)達(dá)到排序的目的。

要表示8個(gè)數(shù)，我們就只需要8個(gè)Bit（1Bytes），首先我們開(kāi)辟1Byte的空間，將這些空間的所有Bit位都置為0，然后將對(duì)應(yīng)位置為1。

最后，遍歷一遍Bit區(qū)域，將該位是一的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的，時(shí)間復(fù)雜度O(n)。

優(yōu)點(diǎn)：

• 運(yùn)算效率高，不需要進(jìn)行比較和移位；
• 占用內(nèi)存少，比如N=10000000；只需占用內(nèi)存為N/8=1250000Byte=1.25M

缺點(diǎn)：

• 所有的數(shù)據(jù)不能重復(fù)。即不可對(duì)重復(fù)的數(shù)據(jù)進(jìn)行排序和查找。
• 只有當(dāng)數(shù)據(jù)比較密集時(shí)才有優(yōu)勢(shì)

快速去重

20億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存不足以容納這20億個(gè)整數(shù)。

首先，根據(jù)“內(nèi)存空間不足以容納這05億個(gè)整數(shù)”我們可以快速的聯(lián)想到Bit-map。下邊關(guān)鍵的問(wèn)題就是怎么設(shè)計(jì)我們的Bit-map來(lái)表示這20億個(gè)數(shù)字的狀態(tài)了。

其實(shí)這個(gè)問(wèn)題很簡(jiǎn)單，一個(gè)數(shù)字的狀態(tài)只有三種，分別為不存在，只有一個(gè)，有重復(fù)。因此，我們只需要2bits就可以對(duì)一個(gè)數(shù)字的狀態(tài)進(jìn)行存儲(chǔ)了，假設(shè)我們?cè)O(shè)定一個(gè)數(shù)字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲(chǔ)空間2G左右。

接下來(lái)的任務(wù)就是把這20億個(gè)數(shù)字放進(jìn)去（存儲(chǔ)），如果對(duì)應(yīng)的狀態(tài)位為00，則將其變?yōu)?1，表示存在一次；如果對(duì)應(yīng)的狀態(tài)位為01，則將其變?yōu)?1，表示已經(jīng)有一個(gè)了，即出現(xiàn)多次；如果為11，則對(duì)應(yīng)的狀態(tài)位保持不變，仍表示出現(xiàn)多次。

最后，統(tǒng)計(jì)狀態(tài)位為01的個(gè)數(shù)，就得到了不重復(fù)的數(shù)字個(gè)數(shù)，時(shí)間復(fù)雜度為O(n)。

快速查找

這就是我們前面所說(shuō)的了，int數(shù)組中的一個(gè)元素是4字節(jié)占32位，那么除以32就知道元素的下標(biāo)，對(duì)32求余數(shù)（%32）就知道它在哪一位，如果該位是1，則表示存在。

小結(jié)&回顧

Bitmap主要用于快速檢索關(guān)鍵字狀態(tài)，通常要求關(guān)鍵字是一個(gè)連續(xù)的序列（或者關(guān)鍵字是一個(gè)連續(xù)序列中的大部分）， 最基本的情況，使用1bit表示一個(gè)關(guān)鍵字的狀態(tài)（可標(biāo)示兩種狀態(tài)），但根據(jù)需要也可以使用2bit（表示4種狀態(tài)），3bit（表示8種狀態(tài)）。

Bitmap的主要應(yīng)用場(chǎng)合：表示連續(xù)（或接近連續(xù)，即大部分會(huì)出現(xiàn)）的關(guān)鍵字序列的狀態(tài)（狀態(tài)數(shù)/關(guān)鍵字個(gè)數(shù) 越小越好）。

32位機(jī)器上，對(duì)于一個(gè)整型數(shù)，比如int a=1 在內(nèi)存中占32bit位，這是為了方便計(jì)算機(jī)的運(yùn)算。但是對(duì)于某些應(yīng)用場(chǎng)景而言，這屬于一種巨大的浪費(fèi)，因?yàn)槲覀兛梢杂脤?duì)應(yīng)的32bit位對(duì)應(yīng)存儲(chǔ)十進(jìn)制的0-31個(gè)數(shù)，而這就是Bit-map的基本思想。Bit-map算法利用這種思想處理大量數(shù)據(jù)的排序、查詢以及去重。

補(bǔ)充1

在數(shù)字沒(méi)有溢出的前提下，對(duì)于正數(shù)和負(fù)數(shù)，左移一位都相當(dāng)于乘以2的1次方，左移n位就相當(dāng)于乘以2的n次方，右移一位相當(dāng)于除2，右移n位相當(dāng)于除以2的n次方。

<< 左移，相當(dāng)于乘以2的n次方，例如：1<<6  相當(dāng)于1×64=64，3<<4 相當(dāng)于3×16=48

>> 右移，相當(dāng)于除以2的n次方，例如：64>>3 相當(dāng)于64÷8=8

^ 異或，相當(dāng)于求余數(shù)，例如：48^32 相當(dāng)于 48%32=16

補(bǔ)充2

不使用第三方變量，交換兩個(gè)變量的值

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實(shí)現(xiàn)了一個(gè)位向量，它可以根據(jù)需要增長(zhǎng)。每一位都有一個(gè)布爾值。一個(gè)BitSet的位可以被非負(fù)整數(shù)索引（PS：意思就是每一位都可以表示一個(gè)非負(fù)整數(shù)）。可以查找、設(shè)置、清除某一位。通過(guò)邏輯運(yùn)算符可以修改另一個(gè)BitSet的內(nèi)容。默認(rèn)情況下，所有的位都有一個(gè)默認(rèn)值false。

可以看到，跟我們前面想的差不多。

用一個(gè)long數(shù)組來(lái)存儲(chǔ)，初始長(zhǎng)度64，set值的時(shí)候首先右移6位（相當(dāng)于除以64）計(jì)算在數(shù)組的什么位置，然后更改狀態(tài)位

別的看不懂不要緊，看懂這兩句就夠了：

1 int wordIndex = wordIndex(bitIndex);
2 words[wordIndex] |= (1L << bitIndex);

4、Bloom Filters

Bloom filter 是一個(gè)數(shù)據(jù)結(jié)構(gòu)，它可以用來(lái)判斷某個(gè)元素是否在集合內(nèi)，具有運(yùn)行快速，內(nèi)存占用小的特點(diǎn)。

而高效插入和查詢的代價(jià)就是，Bloom Filter 是一個(gè)基于概率的數(shù)據(jù)結(jié)構(gòu)：它只能告訴我們一個(gè)元素絕對(duì)不在集合內(nèi)或可能在集合內(nèi)。

Bloom filter 的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是一個(gè) 比特向量（可理解為數(shù)組）。

主要應(yīng)用于大規(guī)模數(shù)據(jù)下不需要精確過(guò)濾的場(chǎng)景，如檢查垃圾郵件地址，爬蟲(chóng)URL地址去重，解決緩存穿透問(wèn)題等。

如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表、樹(shù)、散列表（哈希表）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路，但是隨著集合中元素的增加，需要的存儲(chǔ)空間越來(lái)越大；同時(shí)檢索速度也越來(lái)越慢，檢索時(shí)間復(fù)雜度分別是O(n)、O(log n)、O(1)。

布隆過(guò)濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過(guò) K 個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組（Bit array）中的 K 個(gè)點(diǎn)，把它們置為 1 。檢索時(shí)，只要看看這些點(diǎn)是不是都是1就知道元素是否在集合中；如果這些點(diǎn)有任何一個(gè) 0，則被檢元素一定不在；如果都是1，則被檢元素很可能在（之所以說(shuō)“可能”是誤差的存在）。

BloomFilter 流程

1. 首先需要 k 個(gè) hash 函數(shù)，每個(gè)函數(shù)可以把 key 散列成為 1 個(gè)整數(shù)；
2. 初始化時(shí)，需要一個(gè)長(zhǎng)度為 n 比特的數(shù)組，每個(gè)比特位初始化為 0；
3. 某個(gè) key 加入集合時(shí)，用 k 個(gè) hash 函數(shù)計(jì)算出 k 個(gè)散列值，并把數(shù)組中對(duì)應(yīng)的比特位置為 1；
4. 判斷某個(gè) key 是否在集合時(shí)，用 k 個(gè) hash 函數(shù)計(jì)算出 k 個(gè)散列值，并查詢數(shù)組中對(duì)應(yīng)的比特位，如果所有的比特位都是1，認(rèn)為在集合中。

1 <dependency>
2     <groupId>com.google.guava</groupId>
3     <artifactId>guava</artifactId>
4     <version>28.1-jre</version>
5 </dependency>

com.google.common.hash.BloomFilter

參考文檔：

http://llimllib.github.io/bloomfilter-tutorial/zh_CN/
https://www.cnblogs.com/geaozhang/p/11373241.html
https://www.cnblogs.com/huangxincheng/archive/2012/12/06/2804756.html
https://www.cnblogs.com/DarrenChan/p/9549435.html