Algorithms_算法专项_Bitmap原理及应用
文章目錄
- 引導(dǎo)案例
- 基礎(chǔ)知識(shí)回顧
- Bitmap
- 計(jì)算不同存儲(chǔ)類型需要開辟的內(nèi)存空間
- 原理
- 計(jì)算需要開辟多大長度的數(shù)組
- 找到目標(biāo)數(shù)字在數(shù)組中的下標(biāo)
- 找到目標(biāo)數(shù)字在對(duì)應(yīng)數(shù)組下標(biāo)中的位置
- 總結(jié)下3個(gè)步驟
- 存
- 判斷是否存在
- 刪除
- 代碼
- 測(cè)試
- bitmap優(yōu)缺點(diǎn)總結(jié)
- 優(yōu)點(diǎn)
- 缺點(diǎn)
- 小試牛刀
引導(dǎo)案例
Q: 如何在3億個(gè)整數(shù)， 每個(gè)整數(shù)的范圍是 0到2億，判斷一個(gè)數(shù)是否存在于3億個(gè)整數(shù)中。 要求內(nèi)存使用在100M以內(nèi)，一臺(tái)主機(jī)。
…
思考下…
數(shù)組？ hash ? 分治？ bitmap ? 布隆過濾器 ？
用數(shù)組的話 ， 開辟個(gè)data[2億]長度的數(shù)組， data[1]=1 表示存在，data[2]=0表示不存在。 理論上可行，但是內(nèi)存肯定超過了500M， 不可行
用hash的話，開3億個(gè)空間， 舉個(gè)例子 使用HashMap --> put(1,true) , get(1)為true，則存在， 聽起來也可行哈，但是3億個(gè)int類型 內(nèi)存也是絕對(duì)會(huì)超過500M的。
分治： 內(nèi)存要求也不滿足
bitmap ? 布隆過濾器？ 這兩個(gè)是可以的
我們這里先用bitmap來解決這個(gè)問題
基礎(chǔ)知識(shí)回顧
Algorithms_數(shù)據(jù)結(jié)構(gòu)與算法_位運(yùn)算符的巧技一二事
Bitmap
計(jì)算不同存儲(chǔ)類型需要開辟的內(nèi)存空間
在計(jì)算機(jī)科學(xué)中，bit通常用于表示信息的最小單位，也可以被稱作是二進(jìn)制位。
在計(jì)算機(jī)學(xué)科中，bit一般用0和1表示。
Byte也就是人們常說的字節(jié)，通常由8個(gè)位（8bit）組成一個(gè)字節(jié)(1Byte)
比如我們常見的基本類型的取值范圍
bit與Byte之間可以進(jìn)行換算，具體的換算關(guān)系為：1Byte=8bit
計(jì)算下3億數(shù)據(jù)需要開辟的內(nèi)存空間：
-
如果使用 int數(shù)組來存儲(chǔ)， 那就需要3億個(gè)int , 1個(gè)int占用4個(gè)Byte字節(jié) ， 故3億個(gè)int 占用的內(nèi)存空間為 3億 * 4 （總共占用的Byte） / 1024 (轉(zhuǎn)為KB) / 1024 (轉(zhuǎn)為MB) = 1144 MB
-
如果使用 bit數(shù)組來存儲(chǔ)，那么同樣也需要3億個(gè)bit, 8個(gè)bit才等于 1個(gè)Byte字節(jié)， 故3億個(gè)bit 占用內(nèi)存空間為 3億/8 (總共占用的Byte) / 1024 (轉(zhuǎn)為KB) / 1024 (轉(zhuǎn)為MB) = 35.7 MB
-
當(dāng)然了 你也可以用long 或者 short來存儲(chǔ)，無非就是計(jì)算的時(shí)候的轉(zhuǎn)換關(guān)系調(diào)整下 。 如果使用 long 數(shù)組來存儲(chǔ)， 那就需要3億個(gè)long , 1個(gè)long 占用8個(gè)Byte字節(jié) ， 故3億個(gè)long占用的內(nèi)存空間為 3億 * 8 （總共占用的Byte） / 1024 (轉(zhuǎn)為KB) / 1024 (轉(zhuǎn)為MB) = 2288 MB 。
-
如果使用 short數(shù)組來存儲(chǔ)， 那就需要3億個(gè)short, 1個(gè)short占用2個(gè)Byte字節(jié) ， 故3億個(gè)short占用的內(nèi)存空間為 3億 * 2（總共占用的Byte） / 1024 (轉(zhuǎn)為KB) / 1024 (轉(zhuǎn)為MB) = 572MB 。
-
其他類型也可以，主要是需要開辟的內(nèi)存大小，當(dāng)然是越小越好了…
結(jié)論顯而易見，使用二進(jìn)制bit來存儲(chǔ) 3億個(gè)數(shù)，比使用int來存儲(chǔ)3億個(gè)數(shù) 需要開辟的內(nèi)存空間從1個(gè)G 降低為 36M， 少了30倍 ,你說它不香嗎？？？
原理
bitmap就是利用一個(gè) bit 二進(jìn)制位（0,1）來存儲(chǔ)。由于采用bit為單位來存儲(chǔ)數(shù)據(jù)，可以大大的節(jié)省存儲(chǔ)空間。
OK , 計(jì)算完了需要開辟的內(nèi)存空間，如果使用bit來存儲(chǔ)這些數(shù)據(jù)，該如何表示呢？
我們知道bit 二進(jìn)制位，在計(jì)算機(jī)學(xué)科中，bit一般用0和1表示。
每一個(gè)bit位表示一個(gè)數(shù)，0表示不存在，1表示存在，這正符合bit二進(jìn)制。 舉個(gè)例子我們要存儲(chǔ) {1,2,4,6}
我們需要用bit來 存儲(chǔ)，java.util包中有個(gè)專門存儲(chǔ)bit的類 BitSet
當(dāng)然了，我們也可以用其他類型來表示bit . 接下來我們以int為例 （當(dāng)然了 你用byte , short ,long 都可以…）
計(jì)算需要開辟多大長度的數(shù)組
比如我們使用int來表示bit , 1個(gè)int = 4 個(gè)Byte = 4 * 8 bit . 因此一個(gè)int可以存儲(chǔ)32個(gè)int
假設(shè)有 65個(gè)數(shù)字(0~64)，最大數(shù)字為64 。 用bit表示，肯定需要64bit ,如果用int來表示，需要幾個(gè)int呢 ？
我們來計(jì)算下
-----> 需要3個(gè)int，才能把這65個(gè)bit 存下來。
-----> 65個(gè)數(shù)字 需要3個(gè)int (64/32 +1) , 97個(gè)數(shù)字 需要4個(gè)int (96/32+1) … 【從0開始計(jì)算，最大值 64 ，96】
-----> 推到出來一個(gè)公式來根據(jù)存儲(chǔ)的bit數(shù)量計(jì)算(取數(shù)據(jù)的最大值）需要幾個(gè)int
故需要開辟的int數(shù)組的容量為 (MAX/32 + 1) , 一定要注意的是 一定要取MAX來計(jì)算。 至于為啥子除以32 ， 1 int = 4 Byte = 4 * 8 bit ,通過轉(zhuǎn)換計(jì)算來的。 看到MAX/32 這種 ，應(yīng)該馬上想到 右移 2^5次方 這種高效的計(jì)算方式。 即 （MAX >> 5 + 1 ）
找到目標(biāo)數(shù)字在數(shù)組中的下標(biāo)
確定了需要開辟幾個(gè)int數(shù)組，假設(shè)我們要把64這個(gè)值存儲(chǔ)到bit中（當(dāng)然了，存到bit里肯定不是64 ,bit二進(jìn)制位 存0 1。 1 表示存在，0 表示不存在）
是不是得找到這個(gè)具體的位置 ？
----> 是不是需要先定位到數(shù)組中的哪個(gè)int ， 比如 64 在 int[2],先找到 int[2]
----> 64~95 在 int[2] , 32~63 在int[1] , 96-127 在int[4]
—> 推到出來一個(gè)公式來 找到目標(biāo)數(shù)字在數(shù)組中的下標(biāo) n / 32 ，同樣的 ，通過位移的方式更高效 n/32 —> n/2^5 --> n >> 5
找到目標(biāo)數(shù)字在對(duì)應(yīng)數(shù)組下標(biāo)中的位置
----> 然后再看下 這個(gè)int存儲(chǔ)了32位，那我這個(gè)目標(biāo)值應(yīng)該在第幾個(gè)位置 ，顯而易見，我們的64在第一個(gè)位置。
----> 64 在 int[2] 的 第1位，即下標(biāo)為0的位置， 65呢 下標(biāo)為1的位置 ，70 呢 下標(biāo)為6
—> 推到出來一個(gè)公式來 找到目標(biāo)數(shù)字在在對(duì)應(yīng)數(shù)組下標(biāo)中的位置 ，取余即可 n %32 ，（因?yàn)槌龜?shù)32位2^5）所以 ，通過位移的方式更高效 n%32 —> n%2^5 --> n &（2^5-1） —> n & 31
除數(shù)為2的n次方時(shí)，使用位操作（&運(yùn)算）代替求余操作
總結(jié)下3個(gè)步驟
1. 計(jì)算需要開辟多大長度的數(shù)組 ：（MAX >> 5 + 1 ）
2. 找到目標(biāo)數(shù)字在數(shù)組中的下標(biāo) ： n >> 5
3. 找到目標(biāo)數(shù)字在對(duì)應(yīng)數(shù)組下標(biāo)中的位置 ： n & 31
注意： 計(jì)算需要開辟多大長度的數(shù)組，一定要取最大值計(jì)算，假設(shè)你要存3億個(gè)數(shù)據(jù)
—> 根據(jù)公式 需要開辟的數(shù)組長度為： 3億/32 + 1 = 9375001（9百30多萬） 。
(1個(gè)int 占4個(gè)字節(jié)，9375001 * 4 （總字節(jié)大小） /1024 /1024 = 35.76MB)
存
存的本質(zhì)就是將下標(biāo)為pos的位由0變?yōu)?---->那就把1左移pos位，然后使用或運(yùn)算符運(yùn)算即可 （按位或運(yùn)算【|】有一個(gè)為1時(shí)，結(jié)果位就為1）
舉個(gè)例子 pos = 2 , pos 2原本的bit值是 0 （其實(shí)不管是0 ，還是1）
–> 0 | 1 --> 1
–> 1 | 1 --> 1
判斷是否存在
public boolean find(int n) {// bitMap構(gòu)建的時(shí)候，根據(jù)max來構(gòu)建的，如果入?yún)>max，直接返回不存在if (n > max) return false;return (bitsArray[index(n)] &= 1<<position(n)) != 0;}假設(shè)黃色的二進(jìn)制位1存儲(chǔ)的是數(shù)字n,要想判斷n是否存在
第一步： 找到n所在的數(shù)組下標(biāo)
第二步： 在第一步確定的那個(gè)數(shù)組下標(biāo)對(duì)應(yīng)的int里（假設(shè)我們是用int來存儲(chǔ)bit,32個(gè)bit), 確定這個(gè)n具體在哪個(gè)position，
第三步：把1 左移 position個(gè)位置，然后和目標(biāo)的二進(jìn)制bit位，進(jìn)行 與運(yùn)算. 只有都為1，才說明存在。 如果目標(biāo)的二進(jìn)制bit位是0，0&1=0 ，說明這個(gè)位置沒有被add過，也就不存在。
注： add的時(shí)候，用的是bitsArray[index(n)] |= 1 << position(n) ，所以add完成以后bitsArray[index(n)]就有值了，所以這里繼續(xù)使用bitsArray[index(n)]進(jìn)行 &運(yùn)算
刪除
刪除無非就是把 1置為 0 。
將1左移position后，因?yàn)榇嬖?#xff0c;那個(gè)位置自然就是1，然后取反就是0，再與當(dāng)前值做&，即可清除當(dāng)前的位置了
/*** * @param n* @return*/public boolean del(int n) {// 不存在 返回刪除失敗if (!find(n)) return false;// 將1左移position后，因?yàn)榇嬖?#xff0c;那個(gè)位置自然就是1，然后取反就是0，// 再與當(dāng)前值做&，即可清除當(dāng)前的位置了.return (bitsArray[index(n)] &= ~(1<<position(n))) == 0 ;}代碼
/*** @author 小工匠* @version v1.0* @create 2019-12-20 6:47* @motto show me the code ,change the word* @blog https://artisan.blog.csdn.net/* @description**/public class ArtisanBitMap {// 這批數(shù)據(jù)的最大值，用于確定需要開辟的數(shù)組長度private int max;// 數(shù)據(jù)映射到bit位上，這里用int表示的bit ，1個(gè)int占4個(gè)字節(jié)即4*1Byte = 4*8bit = 32bitprivate int[] bitsArray;/*** 構(gòu)造函數(shù)** @param max*/public ArtisanBitMap(int max) {this.max = max;// 構(gòu)建int數(shù)組，用于存儲(chǔ)bit// (max >> 5) 一定要加括號(hào)，因?yàn)?+號(hào)的優(yōu)先級(jí)比>>高bitsArray = new int[(max >> 5) + 1];}/*** 初始化數(shù)據(jù)** 其實(shí)用啥和1進(jìn)行或運(yùn)算都行，這里使用bitsArray[index(n)]* @return*/public boolean add(int n) {// 或運(yùn)算return (bitsArray[index(n)] |= 1 << position(n)) != 0;}public boolean find(int n) {// bitMap構(gòu)建的時(shí)候，根據(jù)max來構(gòu)建的，如果入?yún)>max，直接返回不存在if (n > max) return false;return (bitsArray[index(n)] &= 1<<position(n)) != 0;}/**** @param n* @return*/public boolean del(int n) {// 不存在 返回刪除失敗if (!find(n)) return false;// 將1左移position后，因?yàn)榇嬖?#xff0c;那個(gè)位置自然就是1，然后取反就是0，// 再與當(dāng)前值做&，即可清除當(dāng)前的位置了.return (bitsArray[index(n)] &= ~(1<<position(n))) == 0 ;}/*** 根據(jù)n 判斷n所在的數(shù)組下標(biāo)** @param n* @return*/public int index(int n) {// n/32 --> n 除以 32 （2^5） ，可以表示為 n向右移5位return n >> 5;}/*** 根據(jù)n 判斷n所在數(shù)組下標(biāo)對(duì)應(yīng)的存儲(chǔ)位置* 即：數(shù)組中的一個(gè)int可以存儲(chǔ)32位，判斷這個(gè)n需要存儲(chǔ)在哪一位** @param n* @return*/public int position(int n) {// n%32 --> n 取余32 （2^5） ，可以表示為 n &(2^5 -1)return n & 31;}public static void main(String[] args) {// 最大是65ArtisanBitMap bitMap = new ArtisanBitMap(300000000);bitMap.add(2);bitMap.add(300000000);// 判斷是否存在boolean a = bitMap.find(2);System.out.println("2是否存在: " + a);boolean b = bitMap.find(300000000);System.out.println("300000000是否存在: " + b);// 刪除操作boolean delete = bitMap.del(2);System.out.println("2是否刪除成功: " + delete);System.out.println("2是否存在: " + bitMap.find(2));}}測(cè)試
bitmap優(yōu)缺點(diǎn)總結(jié)
優(yōu)點(diǎn)
缺點(diǎn)
所以針對(duì)存在的缺點(diǎn)，就要布隆過濾器這個(gè)神器了，下篇我們探討下布隆過濾器的原理及使用。
小試牛刀
Q: 某個(gè)超大的文件中包含一些手機(jī)號(hào)碼，每個(gè)號(hào)碼為11位數(shù)字，求不同號(hào)碼的個(gè)數(shù)。
有了上面的處理思路，是不是這個(gè)問題也有思路了呢？
每個(gè)號(hào)碼11位， 最大值也就是 11個(gè)9唄…so , 懂了吧
總結(jié)
以上是生活随笔為你收集整理的Algorithms_算法专项_Bitmap原理及应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Algorithms_算法专项_Hash
- 下一篇： Algorithms_基础数据结构(01