1 .問(wèn)題引入

? ? ?在給定的一臺(tái)4G的PC機(jī)器上實(shí)現(xiàn)，一個(gè)包含40億個(gè)不重復(fù)并且沒(méi)有排過(guò)序的無(wú)符號(hào)的int整數(shù)，給出一個(gè)整數(shù)，找出給定的某個(gè)數(shù) m,是否在文件40億個(gè)數(shù)據(jù)當(dāng)中的需求。

? 需求分析:Int類型在Java中的存儲(chǔ)占用4個(gè)Byte,32Bit,如果在內(nèi)存中定義40億個(gè)int類型數(shù)組來(lái)讀取文件，占用大小:(40*100000000*4/1024/1024/1024)G=14.901G。這已經(jīng)遠(yuǎn)遠(yuǎn)超出了機(jī)器的內(nèi)存限制，這時(shí)候常規(guī)思路是，將數(shù)據(jù)存在磁盤，分批讀取數(shù)據(jù)到內(nèi)存中，但這樣就會(huì)產(chǎn)生磁盤IO，對(duì)于追求速率的我們來(lái)講，這種情況我們不考慮。

?對(duì)于數(shù)據(jù)來(lái)說(shuō)，某個(gè)數(shù)據(jù)有還是沒(méi)有，我們可以用0和1來(lái)表示，這正好符合二進(jìn)制的0 1屬性，我們知道Java中1 Int = 4 Byte = 32 Bit，這種情況下，我們需要的內(nèi)存空間是，（40*100000000/8/1024/1024）M = 476.8！竟然滿足了我們的要求。

具體思路：

? ?1個(gè)int占4字節(jié)即4*8=32位，那么我們只需要申請(qǐng)一個(gè)int數(shù)組長(zhǎng)度為 int tmp[1+N/32]即可存儲(chǔ)完這些數(shù)據(jù)，其中N代表要進(jìn)行查找的總數(shù)，tmp中的每個(gè)元素在內(nèi)存在占32位可以對(duì)應(yīng)表示十進(jìn)制數(shù)0~31,所以可得到BitMap表:

tmp[0]:可表示0~31

tmp[1]:可表示32~63

tmp[2]可表示64~95

.......

那么接下來(lái)就看看十進(jìn)制數(shù)如何轉(zhuǎn)換為對(duì)應(yīng)的bit位：

假設(shè)這40億int數(shù)據(jù)為：6,3,8,32,36,......，那么具體的BitMap表示為：

如何判斷int數(shù)字在tmp數(shù)組的哪個(gè)下標(biāo)，這個(gè)其實(shí)可以通過(guò)直接除以32取整數(shù)部分，例如：整數(shù)8除以32取整等于0，那么8就在tmp[0]上。另外，我們?nèi)绾沃懒?在tmp[0]中的32個(gè)位中的哪個(gè)位，這種情況直接mod上32就ok，又如整數(shù)8，在tmp[0]中的第8 mod上32等于8，那么整數(shù)8就在tmp[0]中的第八個(gè)bit位（從右邊數(shù)起）。

2.原理

　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ù)的排序、查詢以及去重。

　　Bitmap在用戶群做交集和并集運(yùn)算的時(shí)候也有極大的便利。

3.典型場(chǎng)景

? ?3.1 快速排序

　　假設(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)位設(shè)置為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)行排序和查找。

3.2 快速去重

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

　　首先，根據(jù)“內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)”我們可以快速的聯(lián)想到Bit-map。下邊關(guān)鍵的問(wèn)題就是怎么設(shè)計(jì)我們的Bit-map來(lái)表示這2.5億個(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ǔ)空間幾十兆左右。

　　接下來(lái)的任務(wù)就是遍歷一次這2.5億個(gè)數(shù)字，如果對(duì)應(yīng)的狀態(tài)位為00，則將其變?yōu)?1；如果對(duì)應(yīng)的狀態(tài)位為01，則將其變?yōu)?1；如果為11，,對(duì)應(yīng)的轉(zhuǎn)態(tài)位保持不變。

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

?3.3 快速查詢

? ?　同樣，我們利用Bit-map也可以進(jìn)行快速查詢，這種情況下對(duì)于一個(gè)數(shù)字只需要一個(gè)bit位就可以了，0表示不存在，1表示存在。假設(shè)上述的題目改為，如何快速判斷一個(gè)數(shù)字是夠存在于上述的2.5億個(gè)數(shù)字集合中。

　　同之前一樣，首先我們先對(duì)所有的數(shù)字進(jìn)行一次遍歷，然后將相應(yīng)的轉(zhuǎn)態(tài)位改為1。遍歷完以后就是查詢，由于我們的Bit-map采取的是連續(xù)存儲(chǔ)（整型數(shù)組形式，一個(gè)數(shù)組元素對(duì)應(yīng)32bits），我們實(shí)際上是采用了一種分桶的思想。一個(gè)數(shù)組元素可以存儲(chǔ)32個(gè)狀態(tài)位，那將待查詢的數(shù)字除以32，定位到對(duì)應(yīng)的數(shù)組元素（桶），然后再求余（%32），就可以定位到相應(yīng)的狀態(tài)位。如果為1，則代表改數(shù)字存在；否則，該數(shù)字不存在。

? 3.4?Bit-map擴(kuò)展——Bloom Filter(布隆過(guò)濾器)

當(dāng)一個(gè)元素被加入集合中時(shí),通過(guò)k各散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的k個(gè)點(diǎn),并將這k個(gè)點(diǎn)全部置為1.

　　有一定的誤判率--在判斷一個(gè)元素是否屬于某個(gè)集合時(shí),有可能會(huì)把不屬于這個(gè)集合的元素誤判為屬于這個(gè)集合.因此,它不適合那些"零誤判"的應(yīng)用場(chǎng)合.在能容忍低誤判的應(yīng)用場(chǎng)景下,布隆過(guò)濾器通過(guò)極少的誤判換區(qū)了存儲(chǔ)空間的極大節(jié)省.

Bloom Filter使用k個(gè)相互獨(dú)立的哈希函數(shù)（Hash Function），它們分別將集合中的每個(gè)元素映射到{1,…,m}的范圍中。對(duì)任意一個(gè)元素x，第i個(gè)哈希函數(shù)映射的位置hi(x)就會(huì)被置為1（1≤i≤k）。注：如果一個(gè)位置多次被置為1，那么只有第一次會(huì)起作用，后面幾次將沒(méi)有任何效果。

在判斷y是否屬于這個(gè)集合時(shí)，對(duì)y應(yīng)用k次哈希函數(shù)，若所有hi(y)的位置都是1（1≤i≤k），就認(rèn)為y是集合中的元素，否則就認(rèn)為y不是集合中的元素。

4.Bitmap實(shí)戰(zhàn)

? ? ? java 已經(jīng)對(duì)Bitmap思想進(jìn)行了封裝，我們只需要進(jìn)行相應(yīng)的類引用就行，Bitset 底層采用的是lang類型,如下我們對(duì)：【1,2,3,22,0,3,5,63】數(shù)據(jù)進(jìn)行存儲(chǔ)，最大數(shù)為63，所以我們只需要一位lang類型進(jìn)行存儲(chǔ)，最終的輸出bitSet.size()為64，如果我們的int數(shù)組為【1,2,3,22,0,3,5,65】那么bitSet.size()為128 我們獲取的是bitSet.get(3),就是數(shù)字存儲(chǔ)的數(shù)據(jù) 3。

public class myTest {

public static void main(String[] args) {

int [] array = new int [] {1,2,3,22,0,3,5,63};

BitSet bitSet = new BitSet(); //將數(shù)組內(nèi)容組bitmap for(int i=0;i<array.length;i++) {

bitSet.set(array[i], true);

}

System.out.println(bitSet.size());

System.out.println(bitSet.get(3)); } }

5. 總結(jié)

　　使用Bit-map的思想，我們可以將存儲(chǔ)空間進(jìn)行壓縮，而且可以對(duì)數(shù)字進(jìn)行快速排序、去重和查詢的操作。Bloom Filter是Bit-map思想的一種擴(kuò)展，它可以在允許低錯(cuò)誤率的場(chǎng)景下，大大地進(jìn)行空間壓縮，是一種拿錯(cuò)誤率換取空間的數(shù)據(jù)結(jié)構(gòu)。

6. 應(yīng)用

　　適用范圍：可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來(lái)說(shuō)數(shù)據(jù)范圍是int的10倍以下

　　基本原理及要點(diǎn)：使用bit數(shù)組來(lái)表示某些元素是否存在，比如8位電話號(hào)碼

　　擴(kuò)展：bloom filter可以看做是對(duì)bit-map的擴(kuò)展

問(wèn)題實(shí)例：

1、已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。

8位最多99 999 999，大概需要99m個(gè)bit，大概10幾M字節(jié)的內(nèi)存即可。

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

方案1：采用2-Bitmap（每個(gè)數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無(wú)意義）進(jìn)行，共需內(nèi)存232*2bit=1GB內(nèi)存，還可以接受。然后掃描這2.5億個(gè)整數(shù)，查看Bitmap中相對(duì)應(yīng)位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對(duì)應(yīng)位是01的整數(shù)輸出即可。

原文地址：https://blog.csdn.net/forward__/article/details/80942345