Bit-map的基本思想就是用一個bit位來標記某個元素對應(yīng)的Value，而Key即是該元素上鞠。由于采用了Bit為單位來存儲數(shù)據(jù)际邻，因此在存儲空間方面，可以大大節(jié)省旗国。（PS：劃重點 節(jié)省存儲空間 ）

假設(shè)有這樣一個需求：在20億個隨機整數(shù)中找出某個數(shù)m是否存在其中枯怖，并假設(shè)32位操作系統(tǒng)，4G內(nèi)存

在Java中能曾，int占4字節(jié)度硝，1字節(jié)=8位（1 byte = 8 bit）

如果每個數(shù)字用int存儲，那就是20億個int寿冕，因而占用的空間約為 (20000000004/1024/1024/1024)≈7.45* G

如果按位存儲就不一樣了蕊程，20億個數(shù)就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.23 G

高下立判驼唱，無需多言

那么藻茂，問題來了，如何表示一個數(shù)呢？

剛才說了辨赐，每一位表示一個數(shù)优俘，0表示不存在，1表示存在掀序，這正符合二進制

這樣我們可以很容易表示{1,2,4,6}這幾個數(shù)：

image.png

計算機內(nèi)存分配的最小單位是字節(jié)帆焕，也就是8位，那如果要表示{12,13,15}怎么辦呢不恭？

當然是在另一個8位上表示了：

image.png

這樣的話叶雹，好像變成一個二維數(shù)組了

1個int占32位，那么我們只需要申請一個int數(shù)組長度為 int tmp[1+N/32] 即可存儲换吧，其中N表示要存儲的這些數(shù)中的最大值折晦，于是乎：

tmp[0]：可以表示0~31

tmp[1]：可以表示32~63

tmp[2]：可以表示64~95

。沾瓦。满着。

如此一來姻氨，給定任意整數(shù)M执俩，那么M/32就得到下標绿鸣，M%32就知道它在此下標的哪個位置

添加

這里有個問題嚼贡，我們怎么把一個數(shù)放進去呢涯塔？例如伤锚，想把5這個數(shù)字放進去琼梆，怎么做呢捶码？

首先撕蔼，5/32=0豁鲤，5%32=5，也是說它應(yīng)該在tmp[0]的第5個位置鲸沮，那我們把1向左移動5位琳骡，然后按位或

image.png

換成二進制就是

image.png

這就相當于 86 | 32 = 118

86 | (1<<5) = 118

b[0] = b[0] | (1<<5)

也就是說，要想插入一個數(shù)讼溺，將1左移帶代表該數(shù)字的那一位楣号，然后與原數(shù)進行按位或操作

化簡一下，就是 86 + (5/8) | (1<<(5%8))

因此怒坯，公式可以概括為：p + (i/8)|(1<<(i%8)) 其中炫狱，p表示現(xiàn)在的值，i表示待插入的數(shù)

清除

以上是添加剔猿，那如果要清除該怎么做呢视译？

還是上面的例子，假設(shè)我們要6移除归敬，該怎么做呢酷含？

image.png

從圖上看鄙早，只需將該數(shù)所在的位置為0即可

1左移6位，就到達6這個數(shù)字所代表的位椅亚，然后按位取反限番，最后與原數(shù)按位與，這樣就把該位置為0了

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

查找

前面我們也說了呀舔，每一位代表一個數(shù)字扳缕，1表示有（或者說存在），0表示無（或者說不存在）别威。通過把該為置為1或者0來達到添加和清除的小伙，那么判斷一個數(shù)存不存在就是判斷該數(shù)所在的位是0還是1

假設(shè)驴剔，我們想知道3在不在省古，那么只需判斷 b[0] & (1<<3) 如果這個值是0，則不存在丧失，如果是1豺妓，就表示存在

Bitmap有什么用

大量數(shù)據(jù)的快速排序、查找布讹、去重

快速排序

假設(shè)我們要對0-7內(nèi)的5個元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）,我們就可以采用Bit-map的方法來達到排序的目的琳拭。

要表示8個數(shù)，我們就只需要8個Bit（1Bytes）描验，首先我們開辟1Byte的空間白嘁，將這些空間的所有Bit位都置為0，然后將對應(yīng)位置為1膘流。

最后絮缅，遍歷一遍Bit區(qū)域，將該位是一的位的編號輸出（2呼股，3耕魄，4，5彭谁，7）吸奴，這樣就達到了排序的目的，時間復(fù)雜度O(n)缠局。

優(yōu)點:

• 運算效率高则奥，不需要進行比較和移位；
• 占用內(nèi)存少甩鳄，比如N=10000000逞度；只需占用內(nèi)存為N/8=1250000Byte=1.25M

缺點:

• 所有的數(shù)據(jù)不能重復(fù)。即不可對重復(fù)的數(shù)據(jù)進行排序和查找妙啃。
• 只有當數(shù)據(jù)比較密集時才有優(yōu)勢

快速去重

20億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)档泽，內(nèi)存不足以容納這20億個整數(shù)俊戳。

首先，根據(jù)“內(nèi)存空間不足以容納這05億個整數(shù)”我們可以快速的聯(lián)想到Bit-map馆匿。下邊關(guān)鍵的問題就是怎么設(shè)計我們的Bit-map來表示這20億個數(shù)字的狀態(tài)了抑胎。其實這個問題很簡單，一個數(shù)字的狀態(tài)只有三種渐北，分別為不存在阿逃，只有一個，有重復(fù)赃蛛。因此恃锉，我們只需要2bits就可以對一個數(shù)字的狀態(tài)進行存儲了，假設(shè)我們設(shè)定一個數(shù)字不存在為00呕臂，存在一次01破托，存在兩次及其以上為11。那我們大概需要存儲空間2G左右歧蒋。

接下來的任務(wù)就是把這20億個數(shù)字放進去（存儲）土砂，如果對應(yīng)的狀態(tài)位為00，則將其變?yōu)?1谜洽，表示存在一次萝映；如果對應(yīng)的狀態(tài)位為01，則將其變?yōu)?1阐虚，表示已經(jīng)有一個了序臂，即出現(xiàn)多次；如果為11实束，則對應(yīng)的狀態(tài)位保持不變贸宏，仍表示出現(xiàn)多次。

最后磕洪，統(tǒng)計狀態(tài)位為01的個數(shù)吭练，就得到了不重復(fù)的數(shù)字個數(shù)，時間復(fù)雜度為O(n)析显。

快速查找

這就是我們前面所說的了鲫咽，int數(shù)組中的一個元素是4字節(jié)占32位，那么除以32就知道元素的下標谷异，對32求余數(shù)（%32）就知道它在哪一位分尸，如果該位是1，則表示存在歹嘹。

小結(jié)&回顧

Bitmap主要用于快速檢索關(guān)鍵字狀態(tài)箩绍，通常要求關(guān)鍵字是一個連續(xù)的序列（或者關(guān)鍵字是一個連續(xù)序列中的大部分）， 最基本的情況尺上，使用1bit表示一個關(guān)鍵字的狀態(tài)（可標示兩種狀態(tài)）材蛛，但根據(jù)需要也可以使用2bit（表示4種狀態(tài)）圆到，3bit（表示8種狀態(tài)）。

Bitmap的主要應(yīng)用場合：表示連續(xù)（或接近連續(xù)卑吭，即大部分會出現(xiàn)）的關(guān)鍵字序列的狀態(tài)（狀態(tài)數(shù)/關(guān)鍵字個數(shù) 越小越好）芽淡。

32位機器上，對于一個整型數(shù)豆赏，比如int a=1 在內(nèi)存中占32bit位挣菲，這是為了方便計算機的運算。但是對于某些應(yīng)用場景而言掷邦，這屬于一種巨大的浪費白胀，因為我們可以用對應(yīng)的32bit位對應(yīng)存儲十進制的0-31個數(shù)，而這就是Bit-map的基本思想抚岗。Bit-map算法利用這種思想處理大量數(shù)據(jù)的排序纹笼、查詢以及去重。

補充1

在數(shù)字沒有溢出的前提下苟跪，對于正數(shù)和負數(shù)，左移一位都相當于乘以2的1次方蔓涧，左移n位就相當于乘以2的n次方件已，右移一位相當于除2，右移n位相當于除以2的n次方元暴。

<< 左移篷扩，相當于乘以2的n次方，例如：1<<6 相當于1×64=64茉盏，3<<4 相當于3×16=48

右移鉴未，相當于除以2的n次方，例如：64>>3 相當于64÷8=8

^ 異或鸠姨，相當于求余數(shù)铜秆，例如：48^32 相當于 48%32=16

補充2

不使用第三方變量，交換兩個變量的值

// 方式一
a = a + b;
b = a - b;
a = a - b;

// 方式二
a = a ^ b;
b = a ^ b;
a = a ^ b;

BitSet

BitSet實現(xiàn)了一個位向量讶迁，它可以根據(jù)需要增長连茧。每一位都有一個布爾值。一個BitSet的位可以被非負整數(shù)索引（PS：意思就是每一位都可以表示一個非負整數(shù)）巍糯⌒パ保可以查找、設(shè)置祟峦、清除某一位罚斗。通過邏輯運算符可以修改另一個BitSet的內(nèi)容。默認情況下宅楞，所有的位都有一個默認值false针姿。

image

image

image

image

image

可以看到袱吆，跟我們前面想的差不多

用一個long數(shù)組來存儲，初始長度64搓幌，set值的時候首先右移6位（相當于除以64）計算在數(shù)組的什么位置杆故，然后更改狀態(tài)位

別的看不懂不要緊，看懂這兩句就夠了：

int wordIndex = wordIndex(bitIndex);
words[wordIndex] |= (1L << bitIndex);

Bloom Filters

image.png

Bloom filter 是一個數(shù)據(jù)結(jié)構(gòu)溉愁，它可以用來判斷某個元素是否在集合內(nèi)处铛，具有運行快速，內(nèi)存占用小的特點拐揭。

而高效插入和查詢的代價就是撤蟆，Bloom Filter 是一個基于概率的數(shù)據(jù)結(jié)構(gòu)：它只能告訴我們一個元素絕對不在集合內(nèi)或可能在集合內(nèi)。

Bloom filter 的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是一個 比特向量（可理解為數(shù)組）堂污。

主要應(yīng)用于大規(guī)模數(shù)據(jù)下不需要精確過濾的場景家肯，如檢查垃圾郵件地址，爬蟲URL地址去重盟猖，解決緩存穿透問題等

如果想判斷一個元素是不是在一個集合里讨衣，一般想到的是將集合中所有元素保存起來，然后通過比較確定式镐。鏈表反镇、樹、散列表（哈希表）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路娘汞，但是隨著集合中元素的增加歹茶，需要的存儲空間越來越大；同時檢索速度也越來越慢你弦，檢索時間復(fù)雜度分別是O(n)惊豺、O(log n)、O(1)禽作。

布隆過濾器的原理是尸昧，當一個元素被加入集合時，通過 K 個散列函數(shù)將這個元素映射成一個位數(shù)組（Bit array）中的 K 個點旷偿，把它們置為 1 彻磁。檢索時，只要看看這些點是不是都是1就知道元素是否在集合中狸捅；如果這些點有任何一個 0衷蜓，則被檢元素一定不在；如果都是1尘喝，則被檢元素很可能在（之所以說“可能”是誤差的存在）磁浇。

BloomFilter 流程

1、 首先需要 k 個 hash 函數(shù)朽褪，每個函數(shù)可以把 key 散列成為 1 個整數(shù)置吓；

2无虚、初始化時，需要一個長度為 n 比特的數(shù)組衍锚，每個比特位初始化為 0友题；

3、某個 key 加入集合時戴质，用 k 個 hash 函數(shù)計算出 k 個散列值度宦，并把數(shù)組中對應(yīng)的比特位置為 1；

4告匠、判斷某個 key 是否在集合時戈抄，用 k 個 hash 函數(shù)計算出 k 個散列值，并查詢數(shù)組中對應(yīng)的比特位后专，如果所有的比特位都是1划鸽，認為在集合中。

image.png

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.1-jre</version>
</dependency>