c〹実現ビットマップアルゴリズム(BitMap)

アルゴリズムの原理
BitMapの基本的な考え方は、ある要素に対応するValueをビットで表記することであり、Keyはその要素である。Bit単位でデータを格納するため、記憶空間を大幅に節約することができます。
BitMapはデータ構造と見なすことができる。
このような需要があると仮定すると、20億個のランダム整数の中からある数mが存在するかどうかを探し出し、32ビットのオペレーティングシステム、4 Gメモリを仮定する。
Javaでは、intは4バイト、1バイト=8ビット（1 byte=8 bit）を占めています。
各数字をintとして保存すると20億個のintとなり、占有する空間は約（2000000*4/1024/1024）≒7.45 Gとなる。
位置によって保存すると違って、20億個の数は20億位で、占有空間は約2000000/8/1024/1024/1024)≒0.333 Gです。
長所と短所
利点：Bitを単位としてデータを保存し、マッピング関係を確立して位置を検索するために採用されているので、記憶空間を大幅に減らすことができ、大量のデータでの検索時間を速めることができます。ちょっとハッシュ表の意味がありますが、ハッシュのvalue値データの種類は多様であり、BitMapが最終的に調べたvalueは簡単ないくつかの状態しか表しません。）
短所：BitMapでの検索結果（value）の表現可能な状態は限られていますが、すべてのデータは重複できません。つまり、重複したデータを並べ替えて検索してはいけません。
アルゴリズムの実現
NETでは既にBitMapのデータ構造を実現しています。BitArayは、BitMapアルゴリズムを使って問題を解決する際に、直接公式のBitArayを使用することを提案しています。
NETのソースコードを参照してください。簡単版のBitMapを実現しました。int配列の保存ビット値（最大21億ビットの値を保存します。）は下記の通りです。

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

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

    //        
    public bool this[int index]
    {
      get
      {        
        return Get(index);
      }
      set
      {
        Set(index,value); 
      }
    }

    //           ,             defaultValue。
    public BitMap(int length, bool defaultValue)
    {
      if (length < 0) {
        throw new ArgumentOutOfRangeException("length", "       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;
    }
  
    //            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));
      }
    }
  }

アルゴリズムの適用
問題1：
40億個の重複しないunsigned intの整数を並べたことがなくて、更に一つの数をあげて、この数がその40億個の数の中にあるかどうかを素早く判断すればいいです。海量データのクエリ問題を解決する）
問題1の解法：
ビットセットを作成し、すべて0に初期化します。40億個の重複しない整数を巡回して、上記で提供された1つのマッピング（各重複しない整数が所与のビットにマッピングされる）によってそのビットの位置を見つけ、1としてマークします。この数は大きな整数のセットにあるかどうか、すなわちマッピング関係でこの整数のビット位置を計算し、1であるかどうかを確認し、1であれば存在し、0であれば存在しない。
問題2：
データベースには多くの800の電話番号が保存されています。数がとても大きいので、中に保存できません。どのように並べ替えたらいいですか？時間は空間より重要です。電話番号は800-810-5555と似ています。効率的な並べ替え）
問題2の解法：
実は重複しない任意の7桁とその内のソート問題です。私たちは電話があるかどうかを1つのビットで表します。電話番号のシーケンスを巡回して、ビットマップの収集ビットが設定された番号を巡回すればいいです。上記の実装コードを確認します。
以上はczhiビットマップアルゴリズム（BitMap）の詳細を実現しました。czhiビットマップアルゴリズムに関する資料は他の関連記事に注目してください。