JAVA中BitSet

JAVAにおけるBitSetは「ビットマップ」データ構造であり、「ビットマップ」の意味によって、データの存在性はbitビット上の1または0で表すことができる.1 bitには2つの値:0と1があり、falseとtrueを表すのにちょうど使用できます.「データが存在するか否か」を判断するシーンについては、HashMapを用いて記憶するのが一般的であるが、hashmapというデータ構造KEYとValueの保存には多くのメモリを消費する必要があり、多くのデータ、すなわちビッグデータシーンを保存するのに適していない.例えば、10億件のURLの中で「www.baidu.com/a」が存在するかどうかを判定し、通常のhashmapを使用して保存するのは現実的ではありません.URL自体がメモリを多く占める必要があるため、直接操作することはできません.bitsetを使用して保存すると、1つのURLに対してhashcodeを求め、数字をbitsetにマッピングすることができます.実際には、bitset上の1つのbitビット、すなわち、1ビット空間で1つのURL文字列の存在性を表すことができます.
「存在性」とは、BitSetによって1つの数字が存在するか否かを検出することである.
bitset原理
JAVAでは、1つのlong型の数字が64ビットの空間を占有しており、上記の「ビットマップ」の概念によれば、1つのlong型の数字(4バイト)は64個の数字の「存在性」状態(衝突衝突がない場合、true、false状態)を保存することができる.例えば50個の数字{0,1,10,...63}が「15」が存在するかどうかを判定すると、私たちは通常、これらの数字を配列またはhashmapで保存してから、これらのデータを保存するには64*64ビットを占有する必要があります.ビットマップを使用する場合は、long型の数字でいいです.(50文字列に置き換えると、節約できるスペースが大きくなる可能性があります).

BitSetは、set(int a,boolean value)メソッドのような数字比較のみに向いており、bitSetでは、数字aをtrueまたはfalseに設定する.その後get(int a)法により結果を検出することができる.stringタイプのデータの場合、BitSetを使用するようにhashcode値をbitsetにマッピングできます.

まず、1,1<64,1<128,1<192...など、これらの数字の計算結果は等しい(ビット演算).これもlong数字であり、連続的(または衝突していない)64個の数字の状態しか表現できない.すなわち、数字1をlongでビットで表すと、数字64は同じlong数字の中位で表すことができない--衝突;BitSet内部はlong[]配列であり,配列の大きさはbitSetが受信した最大数によって決定され,この配列は数値セグメントを[0,63],[64127],[128,191]....すなわちlong[0]は[0,63]という範囲の数字の「存在性」を記憶するために用いる、long[1]は[64127]を記憶するために用いられ、順次繰り返すことでビット演算による衝突を回避することができる.|------------|----------|----------|----------|----------| | | [0,63] [64,127] [128,191] ... | |------------|----------|----------|----------|----------| | |long 0 1 2 ... | |------------|----------|----------|----------|----------|

bitSet内部のlong[]配列は、setの最大数に従って動的に拡張されるベクトルに基づいている.配列の最大長の計算:(maxValue - 1) >> 6 + 1

BitSetメソッド疑似コード:public void set(int number){ int index = number >> 6;// number index if(index + 1 > length){ ensureCapacity(index + 1);// long[] } long[index] |= (1L << number);// }