題目

給一臺(tái)普通PC，2G內(nèi)存，要求處理一個(gè)包含20億個(gè)不重復(fù)并且沒有排過序的Int整數(shù)，給出一個(gè)整數(shù)，問如果快速地判斷這個(gè)整數(shù)是否在文件20億個(gè)數(shù)據(jù)當(dāng)中？

分析

由于一個(gè)Int整數(shù)為4個(gè)字節(jié)（Byte），那所需要的內(nèi)存空間為 20億 * 4字節(jié) ≈ 7.45 GB。由于電腦內(nèi)存只有2GB，無法一次性加載整個(gè)數(shù)據(jù)集到內(nèi)存中進(jìn)行查找，所以我們得換個(gè)思路。

已知一個(gè)字節(jié)由八個(gè)二進(jìn)制位組成（如：10101001），因此我們可以用一個(gè)二進(jìn)制位（Bit）標(biāo)記一個(gè)整數(shù)是否存在，存在標(biāo)記為1，不存在標(biāo)記為0，具體如下：

表格標(biāo)記了0到7的數(shù)字，其中 0、3、5和7被標(biāo)記為1，即集合中存在0、3、5和7，可表示為：int[ ] a = { 0, 3, 5, 7 }，這種 位映射 的方式被稱為 bit-map（位圖） 。 因?yàn)?Int = 4Bytet = 32Bit，所以一個(gè)Int所占的二進(jìn)制位可以映射32個(gè)數(shù)字，相當(dāng)于壓縮了32倍，那么之前20億個(gè)整數(shù)所需要的7.45GB內(nèi)存可縮減至238.41MB，至此該數(shù)據(jù)集可以一次性加載到2G內(nèi)存的電腦上。

詳解

一個(gè)Int可以映射32個(gè)數(shù)，那我們最大可申請(qǐng)(n / 32) + 1個(gè)容量的數(shù)組，即：

int[] arr = new int[(n / 32) + 1];

其中：

arr[0]:可映射0~31的數(shù)
arr[1]:可映射32~63的數(shù)
arr[2]:可映射64~95的數(shù)
...

添加數(shù)字number到數(shù)組

1. 首先計(jì)算數(shù)字number在arr數(shù)組中的下標(biāo)index，解：

// 數(shù)字number除以int的位數(shù)32，得到arr數(shù)組中的下標(biāo)index，使用位運(yùn)算優(yōu)化可得:
int index = number >> 5;

2. 其次計(jì)算數(shù)字number在arr[index]中的二進(jìn)制位position，解：

// 數(shù)字number模以int的位數(shù)32，得到元素的二進(jìn)制位position，使用位運(yùn)算優(yōu)化可得:
int position = number & (32 - 1);

3. 最后取出 之前存放的元素 和 新的元素 進(jìn)行| 或運(yùn)算，相當(dāng)于取兩邊二進(jìn)制位的并集，然后再賦值給數(shù)組。

arr[index] = arr[index] | (1 << position);

最終的函數(shù)可為:

public void add(int number){ 
    int index = number >> 5;
    int position = number & 31;
    arr[index] |= 1 << position;
}

注: | 或運(yùn)算相當(dāng)于取并集，列：0101 | 0011 = 0111

從數(shù)組中移除數(shù)字number

標(biāo)記一個(gè)數(shù)是否存在，是將其二進(jìn)制位設(shè)為1，如果要移除就把該位置設(shè)為0，相當(dāng)于位運(yùn)算中的 ~ 取反。最后在和 之前存放的元素 進(jìn)行 & 與運(yùn)算，相當(dāng)于取兩邊二進(jìn)制位的交集，然后再賦值給數(shù)組。

arr[index] = arr[index] & ~(1 << position);

最終的函數(shù)可為:

public void remove(int number){ 
    int index = number >> 5;
    int position = number & 31;
    arr[index] &= ~(1 << position);
}

注: & 與運(yùn)算相當(dāng)于取交集，列：0101 & 0011 = 0001

判斷數(shù)字number是否存在

確認(rèn)該數(shù)字的位置，把這個(gè)數(shù)無符號(hào)右移到最低位，然后在和1進(jìn)行 & 與運(yùn)算，去除高位的數(shù)，最后判斷這個(gè)數(shù)是1還是0，即存在還是不存在。

public boolean contains(int number) {
    int index = number >> 5;
    int position = number & 31;
    return ((arr[index] >>> position) & 1) == 1;
}

應(yīng)用

位圖算法應(yīng)用場(chǎng)景，例如：

1. 布爾型集合操作：位圖還可以進(jìn)行位運(yùn)算，如 & 與（AND）、| 或（OR）、^ 異或（XOR）、~ 取反（NOT）等操作，以支持高效的集合運(yùn)算，比如并集、交集、差集等。
2. 數(shù)據(jù)壓縮：位圖算法可以用于數(shù)據(jù)的壓縮和壓縮索引，例如在索引大量文本數(shù)據(jù)時(shí)，可以將每個(gè)單詞使用位圖表示，從而減少索引的存儲(chǔ)空間。
3. 布隆過濾器（Bloom Filter）：布隆過濾器是一種概率型數(shù)據(jù)結(jié)構(gòu)，利用位圖算法和多個(gè)哈希函數(shù)，可以高效地判斷一個(gè)元素是否屬于一個(gè)集合。
4. 數(shù)據(jù)去重：通過位圖算法可以快速地判斷一個(gè)元素是否已經(jīng)存在于一個(gè)數(shù)據(jù)集合中，從而實(shí)現(xiàn)數(shù)據(jù)去重的功能。

場(chǎng)景

1.判斷用戶是否登錄

思路： 使用redis的bitmap結(jié)構(gòu)存儲(chǔ)，只需要一個(gè)key，然后用戶id為偏移量offset，如果在線就設(shè)置為1，不在線就設(shè)置為0。

2.統(tǒng)計(jì)用戶打卡情況

思路： 使用時(shí)間作為緩存的key，然后用戶id為偏移量offset，如果當(dāng)日打過卡就設(shè)置為1。之后通過bitOp進(jìn)行二進(jìn)制計(jì)算算出在某段時(shí)間內(nèi)用戶的活躍情況。

3.視頻屬性的擴(kuò)展

思路： 一個(gè)擁有億級(jí)數(shù)據(jù)量的短視頻app，視頻存在各種屬性(是否加鎖、是否特效等等)，需要做各種標(biāo)記。key由屬性的type組成。然后視頻id為偏移量offset。