[[394848]]

假設(shè)有一個(gè)需求是這樣的：在200億個(gè)隨機(jī)整數(shù)中找出某個(gè)數(shù)是否存在其中?要求效率高，而且要節(jié)省內(nèi)存。

我們知道，在Java中，int占4字節(jié)，1字節(jié)=8 byte，1 byte = 8 bit(位)

如果用int存儲(chǔ)，那就是200億個(gè)int，因而占用的空間約為

(20000000000*4/1024/1024/1024)≈74.5G。

內(nèi)存消耗很大，一般的家用電腦是滿足不了需求的，所以將數(shù)據(jù)存儲(chǔ)在內(nèi)存中存儲(chǔ)是不合適的。

如果按位存儲(chǔ)就不一樣了，200億個(gè)數(shù)就是200億位，占用空間約為

(2000000000/8/1024/1024/1024)≈2.33G，節(jié)省了30倍的空間。

實(shí)際上這就是Bitmap的思想。Bitmap的基本思想是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value，而Key即是該元素本身。采用bit存儲(chǔ)數(shù)據(jù)，可以大大節(jié)省存儲(chǔ)空間。

Bitmap是什么?如何在bitmap中表示一個(gè)數(shù)呢?

我們知道計(jì)算機(jī)底層存儲(chǔ)的都是二進(jìn)制數(shù)據(jù)，二進(jìn)制數(shù)只有0和1。bitmap每一位的值也只能是0或1，0表示不存在，1表示存在。

這樣我們可以很容易表示{1,2,4,6}這幾個(gè)數(shù)：

計(jì)算機(jī)內(nèi)存分配的最小單位是字節(jié)，也就是8位，那如果要表示{12,13,15}怎么辦呢?

當(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

。。。

于是，對(duì)于任意整數(shù)M，M/32可以得到下標(biāo)，M%32就可以得到它在此下標(biāo)的哪個(gè)位置。

那么，怎么把一個(gè)數(shù)放進(jìn)Bitmap呢?比如想把5這個(gè)數(shù)字放進(jìn)去

插入一個(gè)數(shù)

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

二進(jìn)制就是:

這就相當(dāng)于 86 | 32 = 118，即 86 | (1<<5) = 118，也就是 b[0] = b

[0] | (1<<5)。也就是說，要想插入一個(gè)數(shù)，將1左移相應(yīng)的位數(shù)，然后與原數(shù)進(jìn)行按位或操作即可。

刪除一個(gè)數(shù)

還是上面的例子，假設(shè)刪除數(shù)字6，該怎么做呢?

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

公式如下：

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

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

查找一個(gè)數(shù)

前面已經(jīng)提到，1表示存在，0表示不存在。通過把該位置為1或者0來達(dá)到添加和清除的效果，那么判斷一個(gè)數(shù)存不存在就是判斷該數(shù)所在的位是0還是1。比如，我們想知道6在不在，那么只需要判斷 b[0] & (1<<6)， 如果這個(gè)值是0，則不存在，如果是1，就表示存在。

BitMap在統(tǒng)計(jì)系統(tǒng)里邊能做什么?

例子 1：針對(duì)獨(dú)立用戶的統(tǒng)計(jì)。比如想知道某個(gè)應(yīng)用，每天有多少個(gè)獨(dú)立用戶使用了該應(yīng)用?可以根據(jù)該應(yīng)用的用戶訪問日志，每天生成一個(gè)BitMap;每個(gè)用戶對(duì)應(yīng)BitMap里的一個(gè)位置，如果當(dāng)天訪問了，該位置就置為1，否則為0。這樣要知道當(dāng)天這個(gè)應(yīng)用的總獨(dú)立用戶數(shù)，只需要看看那天的BitMap里邊有多少個(gè)1。

對(duì)于10M(1000萬(wàn))用戶的應(yīng)用，每天需要的BitMap大小為10M/8=1.25MB，即只需要1.25兆字節(jié)。在采用一些壓縮技術(shù)的基礎(chǔ)上，可以進(jìn)一步縮減需要的存儲(chǔ)量，一般情況下可能只需要大約100-200KB的存儲(chǔ)即可。

例子2：用戶回訪的統(tǒng)計(jì)。比如想知道某個(gè)應(yīng)用，昨天使用過的用戶中，有多少今天也使用了?可以在例子1(每天保存一個(gè)獨(dú)立活躍用戶的BitMap)的基礎(chǔ)上，將昨天的BitMap和今天的BitMap進(jìn)行AND操作，然后數(shù)一下生成的BitMap里有多少個(gè)1即可。

怎么將用戶映射到BitMap里邊的某個(gè)位置?

使用BitMap的時(shí)候，都需要將原始數(shù)據(jù)(比如用戶)映射到BitMap里的位置;這種映射一般可以采用外部數(shù)據(jù)(比如在數(shù)據(jù)庫(kù)里保存用戶到BitMap位置的映射)，或者采用固定的規(guī)則(比如計(jì)算用戶名的hash code)。

采用第一種方法時(shí)，通常是在數(shù)據(jù)庫(kù)里邊給用戶分配一個(gè)數(shù)值型的用戶ID，而用戶ID的生成規(guī)則采用自增量的方式來產(chǎn)生;這樣比如有100個(gè)用戶，則其用戶ID為1，2，3，…，98，99，100;用戶ID為1的用戶映射到BitMap里的第1個(gè)位置，用戶ID為2的用戶映射到BitMap里的第2個(gè)位置…(問題：如果自增量的初始值不是0，而是比如10000，會(huì)產(chǎn)生什么影響?)

采用自增量的另外一個(gè)好處是，系統(tǒng)用戶數(shù)少的時(shí)候，BitMap需要的位數(shù)也少;當(dāng)用戶量增長(zhǎng)時(shí)，BitMap的位數(shù)跟著增長(zhǎng)即可;而且如果記住每天的總用戶數(shù)，BitMap里邊還可以直接表明每天的新增用戶是哪些(注意：此處對(duì)于我們的分析系統(tǒng)不一定適用)

采用第二種方法時(shí)，最常使用的規(guī)則是計(jì)算用戶的hash(比如Object.hashCode,或者M(jìn)D5);但由于hash生成的數(shù)字分布很寬(比如java里邊Object的hashCode會(huì)返回一個(gè)int，所以其分布是-231 – 231-1)，但需要的BitMap的位數(shù)往往不用那么大，這樣就需要再做一個(gè)hashcode到BitMap里位置的映射(一般是取余數(shù))，這就要求必須預(yù)先知道BitMap的大小，且這個(gè)大小一般要求保持不變。

比如要求將用戶映射到一個(gè)1024位的BitMap：用戶A的hashcode是101，101除1024取余數(shù)是101，所以用戶A就對(duì)應(yīng)BitMap的第101位;而用戶B的hashcode是1234567，1234567除1024取余數(shù)是647，用戶B就對(duì)應(yīng)BitMap的第647位。

第二種方法由于采用固定的規(guī)則來計(jì)算映射，而不需要去做外部數(shù)據(jù)查詢，因此映射這部分的開銷會(huì)較第一種方法低很多。但第二種方法也有兩個(gè)缺點(diǎn)，其一是如果預(yù)期總用戶量會(huì)增長(zhǎng)到1百萬(wàn)，即使目前系統(tǒng)只有1000個(gè)用戶，也需要一個(gè)1百萬(wàn)位的BitMap，這樣會(huì)造成很大的存儲(chǔ)和計(jì)算資源的浪費(fèi);其二是hashcode有沖突的問題(即有可能用戶C和用戶D計(jì)算出來的hashcode是一樣的);

而hashcode到BitMap里位置的映射也會(huì)造成更多的沖突(比如用戶E和用戶F的hashcode分別是12345678和12377422，但除1024取余后都是334)。這些沖突的存在，導(dǎo)致了數(shù)據(jù)可信度的下降，比如BitMap里的第334位為0，則可以知道用戶E和F都不在;但如果第334位為1，則并不知道用戶E或者用戶F是不是在。

采用第二種方法的BitMap，有一個(gè)更廣為人知的名字，即Bloom Filter (http://en.wikipedia.org/wiki/Bloom_filter)。Bloom Filter經(jīng)常用于文本分析中來記錄某個(gè)詞是否已經(jīng)出現(xiàn);或者垃圾郵件過濾中來檢查郵件地址是否在已知的垃圾郵件地址列表里。

Bloom filter(布隆過濾器)

來了解一下Bloom filter， Bloom filter是一個(gè)數(shù)據(jù)結(jié)構(gòu)，它可以用來判斷某個(gè)元素是否在集合內(nèi)，具有運(yùn)行快速，內(nèi)存占用小的特點(diǎn)。插入和查詢效率都很高。Bloom Filter 是一個(gè)基于概率的數(shù)據(jù)結(jié)構(gòu)：它只能確定一個(gè)元素不在集合內(nèi)，不能確定一定在集合內(nèi)。

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

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

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

布隆過濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過 K 個(gè)散列(hash)函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組(Bit array)中的 K 個(gè)點(diǎn)，把它們置為 1 。檢索時(shí)，只要看看這些點(diǎn)是不是都是1就知道元素是否在集合中;如果這些點(diǎn)有任何一個(gè) 0，則被檢元素一定不在;如果都是1，則被檢元素很可能在。之所以說“可能”，是因?yàn)榭赡苡衕ash沖突的問題。

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，則key很可能在集合中。如果其中任意一個(gè)比特位為0，則確定key不在集合中。

由此可見，如果我們能靈活運(yùn)行二進(jìn)制，確實(shí)能給系統(tǒng)帶來不少好處。所有的程序和指令在執(zhí)行前都會(huì)被轉(zhuǎn)化成0和1，所以我們用二進(jìn)制的0和1直接和計(jì)算機(jī)交互效率是最高的，而且能大幅節(jié)省空間。所以大家一定要關(guān)心計(jì)算機(jī)基礎(chǔ)啊，基礎(chǔ)扎實(shí)了，我們的技術(shù)能力才能上新的臺(tái)階。

號(hào)主簡(jiǎn)介：馮濤，曾任職于阿里巴巴，每日優(yōu)鮮等互聯(lián)網(wǎng)公司，任技術(shù)總監(jiān)，15年電商互聯(lián)網(wǎng)經(jīng)歷。