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

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

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

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

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

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

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

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

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

實際上這就是Bitmap的思想。Bitmap的基本思想是用一個bit位來標記某個元素對應的Value，而Key即是該元素本身。采用bit存儲數據，可以大大節省存儲空間。

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

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

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

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

當然是在另一個8位上表示：

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

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

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

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

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

。。。

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

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

插入一個數

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

二進制就是:

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

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

刪除一個數

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

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

公式如下：

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

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

查找一個數

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

BitMap在統計系統里邊能做什么？

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

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

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

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

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

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

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

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

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

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

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

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

Bloom filter（布隆過濾器）

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

Bloom filter 的基礎數據結構是比特向量，可理解為數組。

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

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

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

BloomFilter 流程：

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

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

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

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

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

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