場(chǎng)景題：假設(shè)有40億QQ號(hào)，但只有1G內(nèi)存，如何實(shí)現(xiàn)判重？
當(dāng)數(shù)據(jù)量比較大時(shí)，使用常規(guī)的方式來(lái)判重就不行了。例如，使用 MySQL 數(shù)據(jù)庫(kù)判重，或使用 List.contains() 或 Set.contains() 判重就不行了，因?yàn)閿?shù)據(jù)量太大會(huì)導(dǎo)致內(nèi)存放不下，或查詢速度太慢等問(wèn)題。
1.空間占用量預(yù)測(cè)
正常情況下，如果將 40 億 QQ 號(hào)存儲(chǔ)在 Java 中的 int 類型的話，一個(gè) int 占 4 字節(jié)（byte）那么 40 億占用空間大小為：
4000000000*4/1024/1024/1024=14.9 GB
1GB=1024MB，1MB=1024KB，1KB=1024B（byte）
所以，我們無(wú)法使用正常的手段進(jìn)行 40 億 QQ 號(hào)的存儲(chǔ)和去重判斷，那怎么實(shí)現(xiàn)呢？
2.解決方案
此問(wèn)題的常見(jiàn)解決方案有兩種：
- 使用位數(shù)組 BitMap 實(shí)現(xiàn)判重。
- 使用布隆過(guò)濾器實(shí)現(xiàn)判重。
具體來(lái)說(shuō)。
（1）位數(shù)組實(shí)現(xiàn)判重
位數(shù)組是指使用位（bit）組成的數(shù)組，每個(gè) QQ 號(hào)使用 1 位（bit）來(lái)存儲(chǔ)，如下圖所示：
其中下標(biāo)用來(lái)標(biāo)識(shí)具體的數(shù)字，例如以上圖片標(biāo)識(shí) 1、3 數(shù)字存在，如果值為 0 表示不存在，這樣的話 40 億占用的位數(shù)組空間位 40 億 bit，也就是 4000000000/1024/1024/1024/8=0.465 GB，不到 1G 的內(nèi)存就可以存儲(chǔ) 40 億 QQ 號(hào)了，查詢某個(gè) QQ 號(hào)是否在線，只需要看這個(gè) QQ 下標(biāo)對(duì)應(yīng)的位置是否為 1，1 表示存在，0 表示不存在。
位數(shù)組代碼實(shí)現(xiàn)
位數(shù)組可以使用 Java 自帶的 BitSet 來(lái)實(shí)現(xiàn)，它位于 java.util 包中，具體實(shí)現(xiàn)代碼如下：
import java.util.BitSet;
public class BitmapExample {
public static void main(String[] args) {
// 創(chuàng)建一個(gè)BitSet實(shí)例
BitSet bitmap = new BitSet();
// 設(shè)置第5個(gè)位置為1，表示第5個(gè)元素存在
bitmap.set(5);
// 檢查第5個(gè)位置是否已設(shè)置
boolean exists = bitmap.get(5);
System.out.println("Element exists: " + exists); // 輸出: Element exists: true
// 設(shè)置從索引10到20的所有位置為1
bitmap.set(10, 21); // 參數(shù)是包含起始點(diǎn)和不包含終點(diǎn)的區(qū)間
// 計(jì)算bitset中所有值為1的位的數(shù)量，相當(dāng)于計(jì)算設(shè)置了的元素個(gè)數(shù)
int count = bitmap.cardinality();
System.out.println("Number of set bits: " + count);
// 清除第5個(gè)位置
bitmap.clear(5);
// 判斷位圖是否為空
boolean isEmpty = bitmap.isEmpty();
System.out.println("Is the bitset empty? " + isEmpty);
}
}（2）布隆過(guò)器實(shí)現(xiàn)
布隆過(guò)濾器是基于位數(shù)組實(shí)現(xiàn)的，它是一種高效的數(shù)據(jù)結(jié)構(gòu)，由布隆在 1970 年提出。它主要用于判斷一個(gè)元素可能是否存在于集合中，其核心特性包括高效的插入和查詢操作，但存在一定的假陽(yáng)性（False Positives）可能性。
布隆過(guò)濾器實(shí)現(xiàn)如下圖所示：
根據(jù) key 值計(jì)算出它的存儲(chǔ)位置，然后將此位置標(biāo)識(shí)全部標(biāo)識(shí)為 1（未存放數(shù)據(jù)的位置全部為 0），查詢時(shí)也是查詢對(duì)應(yīng)的位置是否全部為 1，如果全部為 1，則說(shuō)明數(shù)據(jù)是可能存在的，否則一定不存在。
布隆過(guò)器特性：如果布隆過(guò)濾器說(shuō)一個(gè)元素不在集合中，那么它一定不在這個(gè)集合中；但如果它說(shuō)一個(gè)元素在集合中，則有可能是不存在的（存在誤差，假陽(yáng)性）。
布隆過(guò)器代碼實(shí)現(xiàn)
布隆過(guò)濾器的常見(jiàn)實(shí)現(xiàn)有以下幾種方式：
使用 Google Guava BloomFilter 實(shí)現(xiàn)布隆過(guò)濾器，具體實(shí)現(xiàn)代碼如下：
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample {
public static void main(String[] args) {
// 創(chuàng)建一個(gè)布隆過(guò)濾器，設(shè)置期望插入的數(shù)據(jù)量為10000，期望的誤判率為0.01
BloomFilter<String> bloomFilter =
BloomFilter.create(Funnels.unencodedCharsFunnel(), 10000, 0.01);
// 向布隆過(guò)濾器中插入數(shù)據(jù)
bloomFilter.put("data1");
bloomFilter.put("data2");
bloomFilter.put("data3");
// 查詢?cè)厥欠翊嬖谟诓悸∵^(guò)濾器中
System.out.println(bloomFilter.mightContain("data1")); // true
System.out.println(bloomFilter.mightContain("data4")); // false
}
}使用 Hutool 框架 BitMapBloomFilter 實(shí)現(xiàn)布隆過(guò)濾器，如下代碼所示：
// 初始化
BitMapBloomFilter filter = new BitMapBloomFilter(10);
// 存放數(shù)據(jù)
filter.add("123");
filter.add("abc");
filter.add("ddd");
// 查找
filter.contains("abc");使用 Redisson 框架中的 RBloomFilter 實(shí)現(xiàn)布隆過(guò)濾器，如下代碼所示：
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redissonClient = Redisson.create(config);
// 創(chuàng)建布隆過(guò)濾器，設(shè)置名稱和期望容量與誤報(bào)率
RBloomFilter<String> bloomFilter =
redissonClient.getBloomFilter("myBloomFilter");
bloomFilter.tryInit(10000, 0.03); // 期望容量 10000，誤報(bào)率 3%
// 添加元素到布隆過(guò)濾器
String element1 = "element1";
bloomFilter.add(element1);
// 判斷元素是否存在
boolean mightExist = bloomFilter.contains(element1);
System.out.println("元素 " + element1 + " 可能存在: " + mightExist);
String element2 = "element2";
boolean mightExist2 = bloomFilter.contains(element2);
System.out.println("元素 " + element2 + " 可能存在: " + mightExist2);其中 Google Guava BloomFilter 和 Hutool 框架 BitMapBloomFilter 為單機(jī)版的布隆過(guò)濾器實(shí)現(xiàn)，不適用分布式環(huán)境。分布式環(huán)境要使用 Redisson 框架中的 RBloomFilter 來(lái)實(shí)現(xiàn)布隆過(guò)濾器，因?yàn)樗臄?shù)據(jù)是保存在 Redis 中間件的，而中間件天生支持分布式系統(tǒng)。
小結(jié)
位數(shù)組和布隆過(guò)濾器的區(qū)別如下：
- 位數(shù)組：沒(méi)有誤判，但空間利用率低。
- 布隆過(guò)濾器：空間利用率高，但存在對(duì)已經(jīng)存在的數(shù)據(jù)的誤判（不存在的數(shù)據(jù)沒(méi)有誤判）。
因此，如果對(duì)精準(zhǔn)度要求高可以使用位數(shù)組；如果對(duì)空間要求苛刻，可以考慮布隆過(guò)濾器。
