一如叼、問題引入
先來思考這樣一個問題：假如給你20億個數(shù)字，范圍大小是 1- 20億妻熊，需要你把這些數(shù)字存儲起來，然后再隨機給定一個數(shù)字仑最，判斷其是否存在這20億個數(shù)字中扔役， 你怎么解決。
首先如果不考慮其個數(shù)多少的話警医，我們首先想到的可能就是使用一個set集合亿胸，用來存儲數(shù)字集合，然后直接判斷數(shù)字是否存在预皇，因為其底層使用了hash的數(shù)據(jù)結構侈玄，判斷給定數(shù)字是否存在也是O(1) 的時間復雜度。但是當這個數(shù)字來到10億吟温，乃至更大的時候序仙，如果還是用set集合，可能會極大得浪費我們的存儲空間鲁豪，并且可能會引發(fā)OOM（我們可以大概估算一下潘悼，java中，一個int類型的數(shù)字是4個字節(jié)爬橡，取值范圍：-2147483648~+2147483647治唤。那么這20億個數(shù)據(jù)如果我們用int類型表示，那么占用內(nèi)存就是 4 * 20億 = 80億字節(jié)糙申，約等于8個G）宾添。這個時候，我們需要怎么解決這個問題呢柜裸？
我們主要解決的是占用內(nèi)存過大的這個問題缕陕，那我們想，有沒有比字節(jié)更小的單位呢粘室，沒錯了榄檬，就是bit 位。 我們知道衔统，計算機中鹿榜，最原始都是使用二進制表示，int類型有32bit位锦爵，如果我們用每個bit位表示一個數(shù)字舱殿，那么一個int類型就能夠存儲32個數(shù)字，而且題干中剛好只要求我們能夠判斷目標數(shù)字是否存在险掀，那我們只需要對應的bit位上存儲 1 或者 0沪袭，用來表示存在或者不存在。這么算下來樟氢，原本 約8個G的存儲 / 32,也就是200多M冈绊，就可以解決這個問題侠鳄。
二、思路歸納
為了方便計算死宣，我們暫且將 數(shù)字縮小化便于理解伟恶。
比如給定的數(shù)字集合，最大是130∫愀茫現(xiàn)在我們向集合中添加128博秫，129這兩個數(shù)字，具體應該怎么添加呢眶掌？
1挡育、首先要確定這個集合怎么表示，我們可以使用int類型的數(shù)組（當然你也可以使用Long類型的朴爬，這里只是舉例）即寒，因為int類型占用4個字節(jié)，32位召噩，所以一個int可以表示32個數(shù)字蒿叠，也就是int[0] 可以表示0-31，int[1]表示32-63蚣常，依次類推。
2痊银、有了數(shù)組抵蚊，那么我們就要確定給定的數(shù)字位于數(shù)組的下標位置。我們可以用 （130 / 32 ）+1 = 5 來表示下標位置溯革。為什么數(shù)組長度需要+1呢贞绳，因為4個長度的int數(shù)組只能表示0-127，所以多出來的幾個數(shù)字致稀，只能數(shù)組長度再加一冈闭。
3、有了下標抖单，還需要找到數(shù)組下標中的bit位置萎攒。128 % 32 = 0 來表示在第幾個bit位。
向int數(shù)組中添加128矛绘，
向int數(shù)組中添加129耍休，
有了如上添加數(shù)字將對應bit位置置為1的邏輯，接下來給定一個數(shù)字货矮，判斷這個數(shù)字是否存在于集合內(nèi)羊精，就只要判斷該數(shù)字對應的big位上 的值是否等于1 即可。
比如給定100囚玫，首先找到數(shù)組下標 index = 100 / 32 = 3, num = 100 % 32 = 4, 即只要判斷bigmap[2]的第四個bit位上是否等于1喧锦，等于1读规，說明存在，不等于1燃少，則不存在束亏。
三：布隆過濾器
所謂位圖，就是使用位這個最小的存儲單元來儲存供汛，針對于Integer4個字節(jié)枪汪，根據(jù)位的高低來存儲不同大小的數(shù)字。正常來說怔昨，20億個正整型數(shù)字雀久，數(shù)組來存，需要20億的長度趁舀，但是如果用位來存赖捌，一個Integer占32位，也就是數(shù)組中的一個Integer可以表示32個數(shù)字矮烹，那么就整整縮小了32倍的數(shù)組長度越庇。
問題一：
我們想，現(xiàn)在只是針對數(shù)字奉狈，如果我們把范圍擴大到其他類型卤唉，如果是字符串呢，那么我們就需要先對目標進行哈希運算仁期，然后再計算其數(shù)組下標桑驱。
問題二:
同時我們的哈希表（數(shù)組）長度總是有限的，如果產(chǎn)生哈希沖突跛蛋，那么最后判斷哈希表中的值熬的，就會不準確。那么怎么解決呢赊级？通過設置多個哈希函數(shù)押框，同時將多個位上的值置為1。當判斷一個key所對應的值存不存在時理逊，通過多個哈希函數(shù)得到的數(shù)組下標所對應的值都為1時橡伞，才能確定這個key是存在的，否則不存在挡鞍。這樣當然也可能會存在誤判骑歹，不過我們可以根據(jù)業(yè)務場景的容忍度，通過設置哈希表的大小和哈希函數(shù)的個數(shù)來調(diào)整誤判的概率墨微。redis中的布隆過濾器也就是這么做的道媚。
java的位圖實現(xiàn)：
/**
* @author zhangxiaohu
* @descript int整數(shù)位圖
* @date 2022-10-12
*/
public class BitMap {
private int[] bitMap;
/**
* java中int 占用4個字節(jié)，共32位
* 如果最大數(shù)值是 128，那么bigMap 數(shù)組的長度就是 4（占用128位）最域，如果用普通的方式存儲谴分，最大值是128，那么我們的 數(shù)組長度就是128,相比之下镀脂，內(nèi)存空間減少了32倍
* @param range
*/
public BitMap(int range) {
/**
* range >> 5 = range / 32
* 這里為什么要 + 1呢牺蹄，這是因為，比如最大值是128薄翅，數(shù)組長度是4沙兰，最多只能存儲到 0 - 127，所以存儲128數(shù)組長度要再+1
* 數(shù)組長度+1之后翘魄，所以range = 128鼎天，但是我們可以表示的最大值應該是 128 + 31 = 159
*/
bitMap = new int[(range >> 5) + 1];
}
public void set(Integer number) {
/**
* number >> 5 = number / 32
* 假如number = 128
* index = 4 表示在數(shù)據(jù)的最后一個位置，也就是bitMap[3]
* num = 0 表示在bitMap[3]上的第0位（bitMap[3] 上有32位）暑竟，也就是： 00000000 00000000 00000000 00000001
*/
int index = number >> 5;
int num = number % 32;
/**
* 1 << num = 1 * 2的num次冪,保證相應位置上的值無論為0還是1斋射，都變成1
* 這里為什么要用 | 運算呢 , | 或運算：有一個為1，值就為1
* 是因為多次給每個bitMap位置上的32個元素賦值為1時但荤，這32個值不相互影響
* 比如罗岖，第一次number=128，bitMap[3] = 00000000 00000000 00000000 00000001
* 第二次number = 130, bitMap[3] 不應該 = 00000000 00000000 00000000 00000100腹躁，而是應該 = 00000000 00000000 00000000 00000101
* 所以需要每次賦值時進行或運算
*/
bitMap[index] = bitMap[index] | 1 << num;
}
public boolean exist(Integer number) {
int index = number / 32;
int num = number % 32;
/**
* & 與運算：全部為1桑包，才為1
* 與運算后的結果為 0或者2的num次冪,只要 != 0,就說明這個元素存在
*/
return true == ((bitMap[index] & 1 << num ) != 0) ;
}
}
