前言
首先我們來看看如果要儲存40億QQ號需要多少記憶體？我們使用無符號整數儲存，一個整數需要4個位元組，那麼40億需要4*4000000000/1024/1024/1024≈15G，在業務中我們往往需要更多的空間。而且在Java中並不存在無符號整形，只有幾個操作無符號的靜態方法。
1GB = 1024MB，1MB = 1024KB，1KB = 1024B, 1B = 8b
很顯然這種儲存是不太優雅的，對於這種大資料量的去重，我們可以使用點陣圖Bitmap。
Bitmap
Bitmap，點陣圖，首先看它的名字，位元map，首先我們聽到map，一般都有去重的功能，bitmap聽名字就像使用bit儲存的map。確實，點陣圖是使用bit陣列表示的，它只儲存0或者1，因此我們可以把全部的QQ號放到點陣圖中，當index位置為1時表示已經存在。
假如我們要判斷2924357571是否存在，那麼我們只需要看index為2924357571的值是否為1，如果為1則表示已經存在。
點陣圖使用1個位元表示一個數是否存在，那麼使用無符號整數表示QQ號，4位元組2^32-1是4294967295，記憶體需要4294967295/8/1024/1024≈512MB。
使用Java程式設計時，我們使用點陣圖一般是透過的redis，在redis中點陣圖常用的是以下三個命令：
| 命令 | 功能 |
|---|---|
| SETBIT key offset value | 設定指定offset位置的值，value只能是0或1 |
| GETBIT key offset | 獲取指定offset位置的值 |
| BITCOUNT key start end | 獲取start到end之間value為1的數量 |
演示
其他作用
大資料量去重，Bitmap其極致的空間用在大資料量去重非常合適的，除了QQ號去重，我們還可以用在比如訂單號去重；爬取網站時URL去重，爬過的就不爬取了。
資料統計，比如線上人員統計，將線上人員id為偏移值，為1表示線上；影片統計，將全部影片的id為偏移儲存到Bitmap中。
布隆過濾器（BloomFilter），布隆過濾器的基礎就是使用的點陣圖，只不過布隆過濾器使用了多個雜湊函式處理，只有當全部的雜湊都為1，才表示這個值存在。
布隆過濾器
布隆過濾器一般會使用多個雜湊函式，計算出對應的hash對應多個位圖下標值，如果都為1，表示這個值存在。
例如hutool工具中布隆過濾器的實現類BitMapBloomFilter預設就提供了5個雜湊函式。
public BitMapBloomFilter(int m) {
int mNum =NumberUtil.div(String.valueOf(m), String.valueOf(5)).intValue();
long size = mNum * 1024 * 1024 * 8;
filters = new BloomFilter[]{
new DefaultFilter(size),
new ELFFilter(size),
new JSFilter(size),
new PJWFilter(size),
new SDBMFilter(size)
};
}
優點：相較點陣圖，布隆過濾器使用多個hash演算法，我們就可以給字串或物件存進去計算hash了，不像點陣圖一樣只能使用整形數字看偏移位置是否為1。
缺點：可能產生雜湊衝突，如果判斷某個位置值為1，那麼可能是產生了雜湊衝突，所以，布隆過濾器會有一定誤差。
