面試被問，一千萬個整數裡面快速查找某個整數，你會怎麼去做？

2020 年 10 月 26 日
筆記
Java基礎

最近小林在求職面試中被詢問了這麼一個有趣的面試題：

假設當我們需要在一千萬個整數（整數的範圍在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%準確，會有部分誤判的情況存在。

只能插入和查詢元素，不允許進行刪除操作。