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

10年積累的網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有臨潁免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

假設(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位來(lái)標(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，也是說(shuō)它應(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)。也就是說(shuō)，要想插入一個(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表示不存在。通過(guò)把該位置為1或者0來(lái)達(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)用的用戶訪問(wèn)日志，每天生成一個(gè)BitMap；每個(gè)用戶對(duì)應(yīng)BitMap里的一個(gè)位置，如果當(dāng)天訪問(wèn)了，該位置就置為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)用，昨天使用過(guò)的用戶中，有多少今天也使用了？可以在例子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ī)則采用自增量的方式來(lái)產(chǎn)生；這樣比如有100個(gè)用戶，則其用戶ID為1，2，3，…，98，99，100；用戶ID為1的用戶映射到BitMap里的第1個(gè)位置，用戶ID為2的用戶映射到BitMap里的第2個(gè)位置…（問(wèn)題：如果自增量的初始值不是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ī)則來(lái)計(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有沖突的問(wèn)題（即有可能用戶C和用戶D計(jì)算出來(lái)的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)常用于文本分析中來(lái)記錄某個(gè)詞是否已經(jīng)出現(xiàn)；或者垃圾郵件過(guò)濾中來(lái)檢查郵件地址是否在已知的垃圾郵件地址列表里。

Bloom filter（布隆過(guò)濾器）

---

來(lái)了解一下Bloom filter， Bloom filter是一個(gè)數(shù)據(jù)結(jié)構(gòu)，它可以用來(lái)判斷某個(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ù)下不需要精確過(guò)濾的場(chǎng)景，如檢查垃圾郵件地址，爬蟲URL地址去重，解決緩存穿透問(wèn)題等

如果想判斷一個(gè)元素是否在集合里，一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表、樹、散列表等數(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è)散列（hash）函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組（Bit array）中的 K 個(gè)點(diǎn)，把它們置為 1 。檢索時(shí)，只要看看這些點(diǎn)是不是都是1就知道元素是否在集合中；如果這些點(diǎn)有任何一個(gè) 0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。之所以說(shuō)“可能”，是因?yàn)榭赡苡衕ash沖突的問(wèn)題。

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不在集合中。

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

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

分享文章：如何巧用二進(jìn)制讓性能提升100倍，讓存儲(chǔ)空間減少100倍
當(dāng)前網(wǎng)址：http://aaarwkj.com/article38/gdgcsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、網(wǎng)站排名、定制網(wǎng)站、全網(wǎng)營(yíng)銷推廣、商城網(wǎng)站、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)