最近小林在求職面試中被詢問了這么一個有趣的面試題：
假設當我們需要在一千萬個整數（整數的范圍在1-1億之間）里面快速查找某個整數是否存在于其中的話，如何快速查找進行判斷會比較方便呢？
ps: int 型別的資料存盤的時候是會占用四個位元組空間，假設存盤的資料范圍在1-1億之間，那么資料存盤的時候大概占用空間為：100 * 100 * 1000 * 4 byte 大概存盤空間大小消耗為 ：40000 kb 40mb左右，
1.散串列結構方案
通過散串列來實作該功能當然是可以的，但是散串列里面除了需要存盤對應的數字以外，還需要存盤對應的鏈表指標，每個數字都采用int型別來進行存盤的話，光是數字占用的記憶體大小大概是40mb左右，如果是加上了指標的存盤空間的話，那么存盤的記憶體大小大概是80mb左右了，
2.布爾陣列結構方案
通過使用布爾型別的陣列來進行存盤，首先創建一個一千萬長度的布爾型別陣列，然后根據整數，定位到相應的下標賦值true，那么以后在遍歷的時候，根據相應的下標查找到指定的變數，如果該變數的值是true的話，那么就證明該數字存在，
布爾型別變數在存盤的時候只有true和false存在，但是在陣列中存盤的時候實際上是占用了1個位元組，該型別的變數在被編譯之后實際上是以int型別的資料0000 0000和0000 0001存盤的，因此還是占用了較多的記憶體空間，
3.使用bitmap來進行存盤
例如說一個長度是10的bitmap，每一個bit位都存盤著對應的0到9的十個整形數字，此時每個bitmap所對應的位都是0，當我們存入的數字是3的時候，位于3的位置會變為1，
當我們存盤了多個數字的時候，例如說存盤了4,3,2,1的時候，那么位圖結構就會如下所示：
那么這個時候你可能就會疑惑了，到底在代碼上邊該如何通過計算來獲取一個數字的索引定位呢？
首先我們將核心思路的代碼先貼上來：
public void set(int number) { //相當于對一個數字進行右移動3位，相當于除以8 int index = number >> 3; //相當于 number % 8 獲取到byte[index]的位置 int position = number & 0x07; //進行|或運算 參加運算的兩個物件只要有一個為1，其值為1， bytes[index] |= 1 << position; }
為了方便理解核心思想，所以還是通過圖例來理解會比較好：
例如說往bitmap里面存盤一個數字11，那么首先需要通過向右移位（因為一個byte相當于8個bit），計算出所存盤的byte[]陣列的索引定位，這里計算出index是1，由于一個byte里面存盤了八個bit位，所以通過求余的運算來計算postion，算出來為3，
這里假設原有的bitmap里面存盤了4和12這2個數字，那么它的結構如下所示：
圖片
這個時候，我們需要存盤11進來，那么就需要進行或運算了：
圖片
同理，當我們判斷數字是否存在的時候，也需要進行相應的判斷，代碼如下：
public boolean contain(int number) { int index = number >> 3; int position = number & 0x07; return (bytes[index] & (1<<position)) !=0; }
圖片
整合一下，簡單版的一個bitmap代碼如下：
public class MyBitMap { private byte[] bytes; private int initSize; public MyBitMap(int size) { if (size <= 0) { return; } initSize = size / (8) + 1; bytes = new byte[initSize]; } public void set(int number) { //相當于對一個數字進行右移動3位，相當于除以8 int index = number >> 3; //相當于 number % 8 獲取到byte[index]的位置 int position = number & 0x07; //進行|或運算 參加運算的兩個物件只要有一個為1，其值為1， bytes[index] |= 1 << position; } public boolean contain(int number) { int index = number >> 3; int position = number & 0x07; return (bytes[index] & (1 << position)) != 0; } public static void main(String[] args) { MyBitMap myBitMap = new MyBitMap(32); myBitMap.set(30); myBitMap.set(13); myBitMap.set(24); System.out.println(myBitMap.contain(2)); } }
從剛剛位圖結構的講解中，你應該可以發現，位圖通過陣列下標來定位資料，所以，訪問效率非常高，而且，每個數字用一個二進制位來表示，在數字范圍不大的情況下，所需要的記憶體空間非常節省，
比如剛剛那個例子，如果用散串列存盤這 1 千萬的資料，資料是 32 位的整型數，也就是需要 4 個位元組的存盤空間，那總共至少需要 40MB 的存盤空間，如果我們通過位圖的話，數字范圍在 1 到 1 億之間，只需要 1 億個二進制位，也就是 12MB 左右的存盤空間就夠了，
但是實際應用中，卻并非如我們所想象的那么簡單，假設我們的實際場景進行改變一下：
還是剛剛的那個情況：
還是一千萬個數字，但是數字范圍不是 1 到 1 億，而是 1 到 10 億，那位圖的大小就是 10 億個二進制位，也就是 120MB 的大小，消耗的記憶體空間反而更加大了，而且在bitmap里面還會有部分空間浪費的情況存在，
假設我們對每一個數字都進行一次hash計算，然后通過hash將計算后的結果范圍限制在1千萬里面，那么就不需要再定義10億個二進制位了，
但是這樣子還是會有相應的弊端，例如說hash沖突，那么這個時候如果我們采用多個hash函式來進行處理的話，理論上是可以大大降低沖突的概率的，于是就有了下邊所說的布隆過濾器一說，
布隆過濾器
圖片
布隆過濾器通過使用多次的hash計算來進行數值是否存在的判斷，雖然大大降低了hash沖突的情況，但是還是存在一定的缺陷，那就是容易會有誤判的情況，例如說如下如所示：
圖片
布隆過濾器的誤判有一個特點，那就是，它只會對存在的情況有誤判，如果某個數字經過布隆過濾器判斷不存在，那說明這個數字真的不存在，不會發生誤判；如果某個數字經過布隆過濾器判斷存在，這個時候才會有可能誤判，有可能并不存在，
不過，只要我們調整哈希函式的個數、位圖大小跟要存盤數字的個數之間的比例，那就可以將這種誤判的概率降到非常低，
那么該怎么調整這個位圖大小和存盤數字之間的比例呢？
這里可能就需要用到一些數學公式來進行計算了，
在位陣列長度m的BF中插入一個元素，相應的位可能會被標志為1，所以說，在插入元素后，該位元仍然為0的概率是：
圖片
現有k個哈希函式，并插入n個元素，自然就可以得到該位元仍然為0的概率是：
圖片
反過來講，它已經被置為1的概率就是：
圖片
也就是說，如果在插入n個元素后，我們用一個不在集合中的元素來檢測，那么被誤報為存在于集合中的概率（也就是所有哈希函式對應的位元都為1的概率）為：
圖片
當n比較大時，在查詢了相關資料之后，可以近似得出誤判率的公式大致如下：（本人數學不是太好，這段公式是請教其他大佬得出的）
圖片
所以，在哈希函式的個數k一定的情況下：
- 位陣列長度m越大，誤判率越低；
- 已插入元素的個數n越大，誤判率越高，
盡管說布隆過濾器在使用的時候會有誤判的情況發生，但是在對于資料的準確性有一定容忍度的情況下，使用布隆過濾器還是會比較推薦的，
在實際的專案應用中，布隆過濾器經常會被用在一些大規模去重，但又允許有小概率誤差的場景中，例如說我們對一組爬蟲網頁地址的去重操作，或者統計某些大型網站每天的用戶訪問數量（需要對相同用戶的多次訪問進行去重），
實際上，關于bitmap和布隆過濾器這類工具在大型互聯網企業上已經受到了廣泛使用，例如說java里面提供了BitSet類，Redis也提供了相應的位圖類，Google里面的guava工具包中的BloomFilter也已經實作類布隆過濾器，所以在實際應用的時候只需要直接使用這些現有的組件即可，避免重復造輪子的情況發生，
4.Redis提供的BitMap
在redis里有一個叫做bitmap的資料結構，使用技巧如下：
setbit指令
語法：setbit key offset value 127.0.0.1:6379> setbit bitmap-01 999 0 (integer) 0 127.0.0.1:6379> setbit bitmap-01 999 1 (integer) 0 127.0.0.1:6379> setbit bitmap-01 1003 1 (integer) 0 127.0.0.1:6379> setbit bitmap-01 1003 0 (integer) 1 127.0.0.1:6379> setbit bitmap-01 1004 0 (integer) 0
注意：
1.offset 引數必須大于或等于 0 ，小于 2^32 (bit 映射被限制在 512 MB 之內)，
2.因為 Redis 字串的大小被限制在 512 兆(megabytes)以內， 所以用戶能夠使用的最大偏移量為 2^29-1(536870911) ， 如果你需要使用比這更大的空間， 請使用多個 key，
3.當生成一個很長的字串時， Redis 需要分配記憶體空間， 該操作有時候可能會造成服務器阻塞(block)，在2010年出產的Macbook Pro上， 設定偏移量為 536870911(512MB 記憶體分配)將耗費約 300 毫秒， 設定偏移量為 134217728(128MB 記憶體分配)將耗費約 80 毫秒， 設定偏移量 33554432(32MB 記憶體分配)將耗費約 30 毫秒， 設定偏移量為 8388608(8MB 記憶體分配)將耗費約 8 毫秒，
getbit指令
語法：getbit key offset
回傳值：
127.0.0.1:6379> setbit bm 0 1 (integer) 0 127.0.0.1:6379> getbit bm 0 (integer) 1
bitcount指令
語法：bitcount key [start] [end] ，這里的start和end值為可選項
回傳值：被設定為 1 的位的數量
127.0.0.1:6379> bitcount user18
(integer) 4
bitop指令
語法：bitop operation destkey key [key ...]
operation 可以是 AND 、 OR 、 NOT 、 XOR 這四種操作中的任意一種：
BITOP AND destkey key [key ...] ，對一個或多個 key 求邏輯并，并將結果保存到 destkey ，
BITOP OR destkey key [key ...] ，對一個或多個 key 求邏輯或，并將結果保存到 destkey ，
BITOP XOR destkey key [key ...] ，對一個或多個 key 求邏輯異或，并將結果保存到 destkey ，
BITOP NOT destkey key ，對給定 key 求邏輯非，并將結果保存到 destkey ，
實戰案例
統計某個用戶在xx論壇的簽到次數，這里假設用戶的id為u18
127.0.0.1:6379> setbit user18 1 1 (integer) 0 127.0.0.1:6379> setbit user18 2 1 (integer) 0 127.0.0.1:6379> setbit user18 5 1 (integer) 0 127.0.0.1:6379> setbit user18 15 1 (integer) 0 127.0.0.1:6379> bitcount user18 (integer) 4
通過使用bitcount指令可以快速從redis中計算出user18的簽到天數，
( ps:但是如果要計算出連續簽到的天數，或者記錄更多的簽到資訊，并且考慮上資料存盤的可靠穩定性，那么此時bitmap就不太適用了，這里我只是模擬了一個案例供大家學習這條指令的使用，)
按天統計網站活躍用戶
設計思路，用天來作為統計的key，然后以用戶ID作為Offset，一旦用戶登錄訪問網站，則根據其用戶id計算出對應的offset并且將其設定為1，
//2020年10月21日 用戶11034訪問網站 127.0.0.1:6379> setbit 20201021 11034 1 (integer) 0 //2020年10月21日 用戶11089訪問網站 127.0.0.1:6379> setbit 20201021 11089 1 (integer) 0 //2020年10月21日 用戶11034訪問網站 127.0.0.1:6379> setbit 20201022 11034 1 (integer) 0 //2020年10月21日 用戶11032訪問網站 127.0.0.1:6379> setbit 20201023 11032 1 (integer) 0 //通過使用bitop or 做多個集合的交集運算，計算出2020年10月21日 至2020年10月22日 //內連續登錄的用戶id，并且將其放入到名為active_user的bitmap中 127.0.0.1:6379> bitop or active_user 20201021 20201022 (integer) 1387 //提取活躍用戶資訊 127.0.0.1:6379> bitcount active_user (integer) 2 127.0.0.1:6379>
用戶在線狀態、在線人數統計
//模擬用戶98321訪問系統 127.0.0.1:6379> setbit online_member 98321 1 (integer) 0 127.0.0.1:6379> setbit online_member 13284 1 (integer) 0 127.0.0.1:6379> setbit online_member 834521 1 (integer) 0 127.0.0.1:6379> bitcount online_member (integer) 3 //模擬用戶13284離開系統，在線人數減1 127.0.0.1:6379> setbit online_member 13284 0 (integer) 1 127.0.0.1:6379> bitcount online_member (integer) 2 127.0.0.1:6379>
這段指令案例將會員id作為來offset位置，存入到來bitmap中，通過設定相應到bitmap，當有對應會員登錄訪問的時候，對應offset位置則置為1，最后通過bitcount來統計該bitmap中有多少個項為1，從而計算出用戶在線的人數，
Guava提供的布隆過濾器
對應的依賴：
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency>
引入相關的依賴之后，可以通過撰寫一個簡單的案例來理解guava里面提供的布隆過濾器組件：
packageorg.idea.guava.filter; import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; /** * @author idea * @date created in 11:05 上午 2020/10/25 */ public class GuavaBloomFilter { public static void main(String[] args) { //創建布隆過濾器時要傳入期望處理的元素數量，及最期望的誤報的概率， BloomFilter<Integer> bloomFilter = BloomFilter.create( Funnels.integerFunnel(), 100, //希望存盤的元素個數 0.01 //希望誤報的概率 ); bloomFilter.put(1); bloomFilter.put(2); bloomFilter.put(3); bloomFilter.put(4); bloomFilter.put(5); //判斷過濾器內部是否存在對應的元素 System.out.println(bloomFilter.mightContain(1)); System.out.println(bloomFilter.mightContain(2)); System.out.println(bloomFilter.mightContain(1000)); } }
這段代碼中你可能會疑惑，為什么是mightContain而不是contain呢？
這一點其實和布隆過濾器本身的誤判機制有關，
布隆過濾器常用的場景為：
對于一些快取穿透的場景可以用于做為預防手段，
本身的優點：
存盤空間消耗較少，
時間效率高，查詢和插入的時間復雜度均為O(h)，（h為hash函式的個數）
缺點：
查詢元素是否存在的概率不能保證100%準確，會有部分誤判的情況存在，
只能插入和查詢元素，不允許進行洗掉操作，
END
推薦好文
強大，10k+點贊的 SpringBoot 后臺管理系統竟然出了詳細教程！
為什么MySQL不推薦使用uuid或者雪花id作為主鍵？
為什么建議大家使用 Linux 開發？爽（外加七個感嘆號）
IntelliJ IDEA 15款 神級超級牛逼插件推薦（自用，真的超級牛逼）
炫酷，SpringBoot+Echarts實作用戶訪問地圖可視化（附原始碼）
記一次由Redis分布式鎖造成的重大事故，避免以后踩坑！
十分鐘學會使用 Elasticsearch 優雅搭建自己的搜索系統（附原始碼）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/191701.html
標籤：Java
上一篇：成為最差開發者的10條建議