前言

相信大家肯定也都遇到過，在很多的面試中，尤其是5年以下java工作經驗的面試中，經常會看到如下的面試題：

在2.5億個整數中找出不重複的整數，記憶體不足以容納這2.5億個整數。
給40億個不重複的int型整數(32位)，亂序，然後再給一個數，如何快速判斷這個數是否在那40億個數當中？

筆者也曾經遇到過，而且很長一段時間内都不知道這種題到底考點是什麼，但是那時候年少無知，過了也就過了也沒去仔細研究，直到後來開始研究大資料，接觸到了今天文章的主角BitMap以及BitMap的衍生技術BloomFilter，才恍然大悟，原來當初的面試題的考點竟然就是位圖（BitMap）。

由于現在已經進入了大資料時代，資料量越來越大，是以BitMap以及BitMap的衍生技術BloomFilter的适用場景越來越廣闊，是以在目前的技術場景下，BitMap還是值得好好學一下的，是以接下來的兩篇文章會分别來介紹下BitMap以及BloomFilter的原理以及應用。

正文

什麼是位圖

BitMap的基本思想就是用一個bit位來标記某個元素對應的Value。而此Bit位即是對應的元素，value可以使用位的值（0或者1）來進行表示。由于采用了Bit為機關來存儲資料，是以在存儲空間方面，可以大大節省。

回到前文的面試題，在40億個随機整數中找出某個數m是否存在其中，4G記憶體限制

在Java中，int占4位元組，1位元組=8位（1 byte = 8 bit）

如果每個數字用int存儲，那就是40億個int，因而占用的空間約為 (4000000000*4/1024/1024/1024)≈14.9G

如果按位存儲就不一樣了，40億個數就是40億位，占用空間約為 (4000000000/8/1024/1024/1024)≈0.466G

32位元組的int被存為1個Bit,記憶體消耗變為之前的1/32，簡直爽的一比啊。

位圖的實作

回顧下上面的兩個面試題，這也就代表了位圖的兩個最主要的适用場景：正整數的快速排序以及判斷是否存在；正整數的去重以及計數。

下面就從這兩個方面來說明下位圖的實作，最後再貼上我自己實作的Demo代碼，輔助大家了解位圖的實作過程。由于筆者水準有限，僅僅提供Java相關的實作，感興趣的小夥伴可以使用其他語言實作，邏輯是一樣的。

快速排序以及判斷元素是否存在

在這種場景下，使用一個bit位來表示數值是否存在，這也是位圖效率最高的一種場景，可以達到原始資料1/32的記憶體消耗。

詳細的流程如下：該bit位是0表示不存在，1表示存在；周遊一遍所有的資料，每個數字的值對應bit位相應的順序，周遊到了一個值，就将該bit位設定為1即可，那麼最後所有為1的Bit位的順序即是所有排序完畢的整數，一次周遊就搞定，時間複雜度O（n）。判斷正整數是否存在直接去正整數位置上的Bit位，1就是存在；0就是不存在，時間複雜度O（1），是不是很快很完美？

下面舉個栗子，如果我們想快速排序{6,8,2,5,4},根據位圖該怎麼做呢？根據上面詳細見下圖：

是不是很簡單易懂？完美！看到這裡有的小夥伴可能會提出問題，按順序取資料沒問題，如果資料量太大，Bit位豈不是要很長，這時候去固定位置取資料的效率也會受到影響，能不能優化？必須能！方案如下：

1個int占32位，那麼我們隻需要申請一個int數組長度為 int tmp[1+N/32] 即可存儲，其中N表示要存儲的這些數中的最大值，于是乎：

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

tmp[1]：可以表示33~64

tmp[2]：可以表示65~96

這樣在查詢資料時，先用該資料除了32得到資料的下标，然後使用資料除32取餘，得到bit位的下标。

存儲的問題解決後，剩下就是讀寫資料的問題了，在這個場景下，主要是增加資料，删除資料以及查詢資料，實作流程如下：

根據上文得到的數組下标（array_index）以及bit位下标（bit_index）來進行位運算：例如數字5，則array_index=5/32 = 0;bit_index=(5%32)-1 = 4;下面開始操作：

新增資料：tmp[0] = tmp[0] | 1 << (31 - 5)。計算過程如下：

根據array_index找到數組中對應的數值，将1右移到bit_index的位置後與數組中對應的值按位取或
任何數值和1取或結果都是1，目前位數變成1；其他位數和0取或，結果都不受影響。計算公式：

00001000....0000

————————

00001000....0000

删除資料：tmp[0] = tmp[0] & ~(1 << (31 - 5))。計算過程如下：

根據array_index找到數組中對應的數值，将1右移到bit_index的位置後取反，與按數組中對應的值按位取與
任何數值和0取與結果都是0，目前位數變成0，而其他位數和1取與結果為1，結果不受影響。計算公式：

00001000....0000

11110111....1111

————————

00000000....0000

查找資料：(tmp[0] & (1 << (31 - 5))) != 0 ? true : false

根據array_index找到數組中對應的數值，将1右移到bit_index的位置後與數組中對應的值按位取與
判斷上面的結果，如果不等于0，說明該資料存在；反之如果為0，則該資料不存在。計算公式：

00000000....0000

00001000....0000

————————

00000000....0000

最後留下一段筆者實作的Demo幫助大家了解：

public class BitMapTest {

  /**
   * 位圖的存儲數組
   */
  private static int[] bitArray;
  /**
   * 位圖的數組下标
   */
  private int arrayIndex;
  /**
   * 位圖的bit位下标
   */
  private int bitIndex;

  /**
   * 根據數值範圍執行個體化類
   *
   * @param size
   */
  public BitMapTest(int size) {
    bitArray = new int[(size >> 5) + 1];
  }

  /**
   * 根據實際資料給位圖的資料下标以及bit位下标指派
   *
   * @param index
   */
  private void setIndex(int index) {
    arrayIndex = index % 32 == 0 ? (index >> 5) - 1 : (index >> 5);
    bitIndex = index % 32 == 0 ? 31 : index % 32 - 1;
  }

  /**
   * 設定指定數值存在（插入）
   *
   * @param index
   */
  public void set1(int index) {
    setIndex(index);
    bitArray[arrayIndex] |= 1 << (31 - bitIndex);
  }

  /**
   * 設定指定數值不存在（删除）
   *
   * @param index
   */
  public void set0(int index) {
    setIndex(index);
    bitArray[arrayIndex] &= ~(1 << (31 - bitIndex));
  }

  /**
   * 指定數值是否存在（查詢）
   *
   * @param index
   * @return
   */
  public boolean exists(int index) {
    setIndex(index);
    return (bitArray[arrayIndex] & (1 << (31 - bitIndex))) != 0 ? true : false;
  }

  public static void main(String[] args) {
    BitMapTest test = new BitMapTest(1000);
    test.set1(288);
    test.set1(64);
    test.set1(63);
    test.set0(128);
    System.out.println(test.exists(64));
    System.out.println(test.exists(63));
    System.out.println(test.exists(128));
  }
}

正整數的去重以及計數

在這種場景下，使用兩個bit位來表示數值是否存在，可以達到原始資料1/16的記憶體消耗，效率也是很高的

詳細的流程如下：順序仍對應的是我們的key，value分下面幾種情況：00,01,10,11，分别代表0次，1次，2次和多次。資料錄入仍舊是一次周遊就搞定，時間複雜度O（n）。如果數字重複，則将對應的兩位bit加1即可，如果超過2次即兩位bit變成11後不再增加。可以看出周遊完成後去重即完成。判斷正整數出現的次數直接去正整數位置上的兩個Bit位，根據上面value的集中情況就可以直接得到統計的次數，時間複雜度O（1），是不是很快很完美？

下面舉個栗子，如果我們想去重以及計數{3,5,2,3,5,7,3,3},根據位圖該怎麼做呢？根據上面詳細見下圖：

數組優化和擴充的方式和上面的一樣，這裡就不再贅述了。

存儲的問題解決後，剩下就是讀寫資料的問題了，在這個場景下，主要是計數以及取數了，實作流程如下：

根據上文得到的數組下标（array_index）以及bit位下标（bit_index）來進行位運算：例如數字5，則array_index=5/16 = 0;bit_index=(5%16)-1 = 4;下面開始操作：

統計資料：由于流程有分支，此處不寫明代碼，後續通過Demo中的代碼幫助大家了解。計算過程如下：

根據array_index以及bit_index找到數組中對應的數值，然後在找到對應的2個Bit。
如果兩位Bit為'11'，則直接傳回說明已經超過2次；否則将兩位Bit加1得到新的結果。計算公式：

000000000100....

000010000100....

————————

000010001000....（結果是數字5從1次變成了2次）

取得資料：由于流程有分支，此處不寫明代碼，後續通過Demo中的代碼幫助大家了解。計算過程如下：

根據array_index以及bit_index找到數組中對應的數值，然後在找到對應的2個Bit。
如果這兩位Bit是'11'，則表明該正整數出現多次；其餘的三種可能性為：'10'出現兩次，'01'出現1次，'00'未出現。計算公式：

000000001000....對應的就是5出現兩次

最後留下一段筆者實作的Demo幫助大家了解：

public class BitMap4CntTest {

  /**
   * 位圖的存儲數組
   */
  private static int[] bitArray;
  /**
   * 位圖的數組下标
   */
  private int arrayIndex;
  /**
   * 位圖的bit位下标
   */
  private int bitIndex;

  /**
   * 根據數值範圍執行個體化類
   *
   * @param size
   */
  public BitMap4CntTest(int size) {
    bitArray = new int[(size >> 4) + 1];
  }

  /**
   * 根據實際資料給位圖的資料下标以及bit位下标指派
   *
   * @param index
   */
  private void setIndex(int index) {
    arrayIndex = index % 16 == 0 ? (index >> 4) - 1 : index >> 4;
    bitIndex = index % 16 == 0 ? 15 : index % 16 - 1;
  }

  /**
   * 位圖計數加1
   *
   * @param index
   */
  public void add1(int index) {
    int cnt = getCnt(index);
    switch (cnt) {
      case 0:
        bitArray[arrayIndex] |= 1 << (31 - bitIndex * 2 - 1);
        break;
      case 1:
        bitArray[arrayIndex] &= ~(1 << (31 - bitIndex * 2 - 1));
        bitArray[arrayIndex] |= 1 << (31 - bitIndex * 2);
        break;
      case 2:
        bitArray[arrayIndex] |= 1 << (31 - bitIndex * 2 - 1);
        break;
      default:
        break;
    }
  }

  /**
   * 擷取元素數量，數量的取值範圍是：0個，1個，2個以及多個
   *
   * @param index
   * @return
   */
  public int getCnt(int index) {
    int result = 0;
    setIndex(index);
    String str = toFullBinaryString(bitArray[arrayIndex]);
    String substring = str.substring(bitIndex * 2, bitIndex * 2 + 2);
    switch (substring) {
      case "00":
        result = 0;
        break;
      case "01":
        result = 1;
        break;
      case "10":
        result = 2;
        break;
      case "11":
        result = 3;
        break;
      default:
        break;
    }
    return result;
  }

  /**
   * 将整數num轉化為32位的二進制字元串
   *
   * @param num
   * @return
   */
  public String toFullBinaryString(int num) {
    char[] chs = new char[Integer.SIZE];
    for (int i = 0; i < Integer.SIZE; i++) {
      chs[Integer.SIZE - 1 - i] = (char) (((num >> i) & 1) + '0');
    }
    return new String(chs);
  }

  public static void main(String[] args) {
    BitMap4CntTest test = new BitMap4CntTest(1000);
    test.add1(111);
    test.add1(111);
    test.add1(111);
    test.add1(111);
    test.add1(112);
    test.add1(113);
    test.add1(113);
    test.add1(113);
    test.add1(114);
    test.add1(114);
    System.out.println(test.getCnt(111));
    System.out.println(test.getCnt(112));
    System.out.println(test.getCnt(113));
    System.out.println(test.getCnt(114));
  }
}

總結

如今的位圖除了在高性能的服務端程式設計中被廣泛利用，也在很多大資料元件中被反複實踐。如redis提供了類似的指令，最大可以存放2的32次方，即21億多的數字，主要有以下幾個：SETBIT， GETBIT， BITCOUNT， BITOP， BITPOS，BITFIELD等指令，主要用來做活躍使用者線上狀态、活躍使用者統計、使用者簽到等場景。

另外位圖的變種BloomFilter則在位圖的基礎上發揚光大，在很多NOSQL資料庫中起到了索引判空以及加速查詢的作用，後續文章會詳細介紹。

通過本文的學習，能夠幫助大家在後續解決類似問題的時候有一個思路，面試的時候遇到這類題時也能做到了然于胸，那這篇文章就發揮出自己的價值了。

最後，筆者長期關注大資料通用技術，通用原理以及NOSQL資料庫的技術架構以及使用。如果大家感覺筆者寫的還不錯，麻煩大家多多點贊和分享轉發，也許你的朋友也喜歡。

面試以及大資料進行中的常客BItMap到底是個什麼樣子的存在？

前言

正文

什麼是位圖

位圖的實作

快速排序以及判斷元素是否存在

正整數的去重以及計數

總結

繼續閱讀

Excel資料清洗大師-Power Query，我整理資料2小時，同僚2分鐘搞定了

TDMS資料讀取/轉換/儲存為MATLAB/Python 可讀取的通用資料格式的的方法

python 矢量轉栅格

Subaru/HiCIAO觀測RYTau近紅外散射光：蝴蝶狀分布展現引言再RYTau（一顆原恒星）上進行了近紅外冕狀成像

C語言實作的滑動平均濾波算法

算法和算法分析

快速排序算法的優勢

從算法入手講解如何在資料庫中實作最優最簡

pytorch nn.Linear(x)中x的資料次元

Java工具類之Apache的Commons-lang

Pandas将inf， nan轉化成特定的值

大資料清洗、轉換工具——ETL工具概述ETL的實作架構ETL工具的特點ETL産品分類ETL轉換過程資料品質中繼資料

企業架構13——資料處理

IBM Power程式設計馬拉松——以“碼”會友，把手言歡！

【資料處理】 python 基于Basemap地理資訊可視化資料可視化方法——Basemap效果

【python】【資料處理】畫多元資料分布圖