算法原理

BitMap的基本思想就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value，而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此可以大大節(jié)省存儲(chǔ)空間。
BitMap可以看成一種數(shù)據(jù)結(jié)構(gòu)。

假設(shè)有這樣一個(gè)需求：在20億個(gè)隨機(jī)整數(shù)中找出某個(gè)數(shù)m是否存在其中，并假設(shè)32位操作系統(tǒng)，4G內(nèi)存。
在Java中，int占4字節(jié)，1字節(jié)=8位（1 byte = 8 bit）。
如果每個(gè)數(shù)字用int存儲(chǔ)，那就是20億個(gè)int，因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45G
如果按位存儲(chǔ)就不一樣了，20億個(gè)數(shù)就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.233G

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)并建立映射關(guān)系來(lái)查找位置，因此可以大大減少存儲(chǔ)空間，加快在大量數(shù)據(jù)中查詢的時(shí)間。（有點(diǎn)哈希表的意思，但哈希中的value值數(shù)據(jù)類型可以豐富多樣，而BitMap最終查到的value只能表示簡(jiǎn)單的幾種狀態(tài)。）

缺點(diǎn)：BitMap中的查詢結(jié)果（value）能表達(dá)的狀態(tài)有限，且所有的數(shù)據(jù)不能重復(fù)。即不可對(duì)重復(fù)的數(shù)據(jù)進(jìn)行排序和查找。

算法實(shí)現(xiàn)（C#）

.NET中已經(jīng)實(shí)現(xiàn)了BitMap的數(shù)據(jù)結(jié)構(gòu)——BitArray，建議使用BitMap算法解決問(wèn)題時(shí)直接使用官方的BitArray。
我參照.NET源碼實(shí)現(xiàn)了一個(gè)簡(jiǎn)化版的BitMap，以int數(shù)組存儲(chǔ)位值（最多存21億個(gè)位值），代碼如下：

  class BitMap
  {
    public int Length{ get{ return m_length;}
    }
    private int[] m_array;
    private int m_length;

    public BitMap(int length): this(length, false) { }

    //索引根據(jù)需求添加
    public bool this[int index]
    {
      get
      {        
        return Get(index);
      }
      set
      {
        Set(index,value); 
      }
    }

    //分配空間以容納長(zhǎng)度位值, 位數(shù)組中的所有值都設(shè)置為defaultValue。
    public BitMap(int length, bool defaultValue)
    {
      if (length < 0) {
        throw new ArgumentOutOfRangeException("length", "長(zhǎng)度值不能小于0");
      }

      int arrayLength = length > 0 ? (((length - 1) / 32) + 1) : 0;
      m_array = new int[arrayLength];
      m_length = length;
  
      int fillValue = defaultValue ? unchecked(((int)0xffffffff)) : 0;
      for (int i = 0; i < m_array.Length; i++) {
        m_array[i] = fillValue;
      }
    }

    //返回位置索引處的位值。
    public bool Get(int index) {
      if (index < 0 || index >= Length) {
        throw new ArgumentOutOfRangeException("index", "索引值超出范圍");
      }
      return (m_array[index / 32] & (1 << (index % 32))) != 0;
    }
  
    //將位置索引處的位值設(shè)置為value。
    public void Set(int index, bool value) {
      if (index < 0 || index >= Length) {
        throw new ArgumentOutOfRangeException("index", "索引值超出范圍");
      }
  
      if (value) {
        m_array[index / 32] |= (1 << (index % 32));
      } else {
        m_array[index / 32] &= ~(1 << (index % 32));
      }
    }
  }

算法應(yīng)用

問(wèn)題1：

給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒(méi)有排過(guò)序，然后再給一個(gè)數(shù)，如果快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中。（解決海量數(shù)據(jù)中的查詢問(wèn)題）

問(wèn)題1解法：

建立一個(gè)位集合，全部初始化為0。遍歷40億個(gè)不重復(fù)的整數(shù)，通過(guò)上述提供的一種映射（每個(gè)不重復(fù)的整數(shù)映射到給定的位）找到其位的位置，標(biāo)記為1。判斷這個(gè)數(shù)是否在大整數(shù)集合中，即通過(guò)映射關(guān)系計(jì)算此整數(shù)的位位置，檢查是否為1，若為1，則存在，若為0，則不存在

問(wèn)題2：

數(shù)據(jù)庫(kù)里存了很多800電話號(hào)碼，數(shù)量特別大，以至于內(nèi)存放不下，如何排序，時(shí)間比空間更重要？電話號(hào)碼類似于800-810-5555。（高效排序）

問(wèn)題2解法：

其實(shí)就是不重復(fù)的任意7位數(shù)及其之內(nèi)的排序問(wèn)題。我們用1位來(lái)表示電話是否出現(xiàn)，遍歷整個(gè)電話號(hào)序列，設(shè)置相應(yīng)的位，遍歷位圖收集位被設(shè)置的號(hào)碼即可。查看上述的實(shí)現(xiàn)代碼

以上就是c# 實(shí)現(xiàn)位圖算法（BitMap）的詳細(xì)內(nèi)容，更多關(guān)于c# 位圖算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論