如何巧用二進制讓性能提升100倍，讓存儲空間減少100倍

本篇內(nèi)容介紹了“如何巧用二進制讓性能提升100倍，讓存儲空間減少100倍”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

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

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

如果用int存儲，那就是200億個int，因而占用的空間約為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

。。。

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

那么，怎么把一個數(shù)放進Bitmap呢？比如想把5這個數(shù)字放進去

插入一個數(shù)

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

二進制就是:

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

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

刪除一個數(shù)

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

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

公式如下：

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

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

查找一個數(shù)

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

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

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

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

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

怎么將用戶映射到BitMap里邊的某個位置？

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

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

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

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

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

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

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

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

Bloom filter（布隆過濾器）

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

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

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

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

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

BloomFilter 流程：

1. 首先需要 k 個 hash 函數(shù)，每個函數(shù)可以把 key 散列成為 1 個整數(shù)；

2. 初始化時，需要一個長度為 n 比特的數(shù)組，每個比特位初始化為 0；

3. 某個 key 加入集合時，用 k 個 hash 函數(shù)計算出 k 個散列值，并把數(shù)組中所有對應(yīng)的比特位置為 1；

4. 判斷某個 key 是否在集合時，用 k 個 hash 函數(shù)計算出 k 個散列值，并查詢數(shù)組中對應(yīng)的比特位，如果所有的比特位都是1，則key很可能在集合中。如果其中任意一個比特位為0，則確定key不在集合中。

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

“如何巧用二進制讓性能提升100倍，讓存儲空間減少100倍”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！