ビットマップの基本原理
ビットマップ（BitMap）は、データの存在状態をビット単位で管理するデータ構造です。各ビットが特定の要素の有無を示すフラグとして機能するため、膨大な量のデータを扱う際にもメモリ消費を極限まで抑えることができます。主に、データに重複がない場合や、存在確認のみが必要な場景において効果的です。
ビットマップのカスタム実装
標準ライブラリの機能に依存せず、独自のビット集合クラスを構築することで、内部動作の理解を深めることができます。ここでは、テンプレートを用いて固定サイズのビット配列を管理する BitArray クラスを定義します。
クラス設計とメンバー変数
このクラスはテンプレート引数 Size を受け取り、必要なビット数を確保します。内部では uint32_t の配列を使用し、1 つの整数で 32 ビットを管理します。
template<size_t Size>
class BitArray {
public:
BitArray() {
// 32 ビット単位のチャンク数を計算し、0 で初期化
_chunks.resize((Size >> 5) + 1, 0);
}
// 指定ビットを 1 に設定
void mark(size_t idx) {
size_t chunk = idx >> 5; // 配列インデックス（idx / 32）
size_t offset = idx & 0x1F; // ビットオフセット（idx % 32）
_chunks[chunk] |= (1u << offset);
}
// 指定ビットを 0 にリセット
void clear(size_t idx) {
size_t chunk = idx >> 5;
size_t offset = idx & 0x1F;
_chunks[chunk] &= ~(1u << offset);
}
// 指定ビットの状態を確認
bool check(size_t idx) const {
size_t chunk = idx >> 5;
size_t offset = idx & 0x1F;
return (_chunks[chunk] & (1u << offset)) != 0;
}
private:
std::vector<uint32_t> _chunks;
};上記の実装では、除算や剰余演算の代わりにビットシフトとビットマスクを使用することで、パフォーマンスを最適化しています。これにより、任意のビット位置へのアクセスが定数時間 O(1) で完了します。
ビットマップの活用事例
- 大規模データセットにおける存在確認の高速化
- 重複排除を伴うソート処理
- 集合演算（和集合、積集合）の効率化
- オペレーティングシステムにおけるディスクブロックの管理
ブルームフィルタの概要
ブルームフィルタは、1970 年に Burton Howard Bloom によって提案された確率論的データ構造です。複数のハッシュ関数を用いて要素をビットマップ上の複数の位置にマップします。この手法により、メモリ使用量を大幅に削減しつつ、高速な挿入と查询が可能になります。ただし、「存在しない場合は確実に存在しない」と判断できる一方、「存在する場合は存在する可能性がある（偽陽性あり）」という特性を持ちます。
ブルームフィルタの実装詳細
ブルームフィルタを機能させるためには、独立性の高い複数のハッシュ関数が必要です。ここでは、文字列キーに対して異なるハッシュ値を生成する 3 つの関数を用意し、それらを組み合わせてフィルタを構築します。
ハッシュ関数の定義
異なるアルゴリズムを用いることで、ビット位置の衝突リスクを分散させます。
struct HashStrategyA {
size_t operator()(const std::string& key) const {
size_t val = 0;
for (char c : key) {
val = val * 131 + c;
}
return val;
}
};
struct HashStrategyB {
size_t operator()(const std::string& key) const {
size_t val = 0;
for (size_t i = 0; i < key.size(); ++i) {
if (i & 1) {
val ^= ((val << 7) ^ key[i] ^ (val >> 3));
} else {
val ^= (~((val << 11) ^ key[i] ^ (val >> 5)));
}
}
return val;
}
};
struct HashStrategyC {
size_t operator()(const std::string& key) const {
size_t val = 5381;
for (char c : key) {
val = val + (val << 5) + c;
}
return val;
}
};ブルームフィルタクラスの構築
前述の BitArray を内部ストレージとして利用し、3 つのハッシュ戦略をテンプレート引数として受け取るクラスです。
template<size_t Capacity,
class KeyType = std::string,
class Hash1 = HashStrategyA,
class Hash2 = HashStrategyB,
class Hash3 = HashStrategyC>
class BloomSet {
public:
void Add(const KeyType& key) {
size_t h1 = Hash1()(key) % Capacity;
size_t h2 = Hash2()(key) % Capacity;
size_t h3 = Hash3()(key) % Capacity;
_bitmap.mark(h1);
_bitmap.mark(h2);
_bitmap.mark(h3);
}
bool Contains(const KeyType& key) const {
size_t h1 = Hash1()(key) % Capacity;
if (!_bitmap.check(h1)) return false;
size_t h2 = Hash2()(key) % Capacity;
if (!_bitmap.check(h2)) return false;
size_t h3 = Hash3()(key) % Capacity;
if (!_bitmap.check(h3)) return false;
return true; // 偽陽性の可能性あり
}
private:
BitArray<Capacity> _bitmap;
};実装上の注意点
ブルームフィルタは空間効率を追求する代わりに、完全な正確性を犠牲にしています。そのため、厳密な一致判定が必要なシステムには不向きです。また、標準的な実装では要素の削除をサポートしていません。特定のビットを 0 に戻すと、他の要素の存在確認にも影響を及ぼす可能性があるためです。
検索の仕組み
要素の存在確認は、複数のハッシュ値が指すビット位置がすべて 1 になっているかどうかで判定されます。いずれか一つでも 0 であれば、その要素は確実に集合に含まれていません。すべて 1 の場合、含まれている可能性がありますが、他の要素によるハッシュ衝突によって偶然 1 になっているケースも考えられます。
削除機能の拡張
削除機能を実装するには、各ビットを単なるフラグではなくカウンタとして扱います。挿入時に該当するカウンタをインクリメントし、削除時にデクリメントします。これにより、他の要素との共有ビットを誤ってクリアすることを防げますが、メモリ使用量が増加し、カウンタのオーバーフロー対策も必要になります。
ブルームフィルタの利点と欠点
利点：
- 挿入と查询の時間計算量がハッシュ関数の数に依存し、データ総量に依存しない。
- ハッシュ関数は独立しているため、並列処理との親和性が高い。
- 要素そのものを保存しないため、プライバシー保護が必要な場景で有用。
- 大規模データセットにおいて、他の構造と比較して圧倒的にメモリ効率が良い。
- 同じハッシュ関数群を使用するフィルタ同士で、集合演算が可能。
欠点：
- 偽陽性（False Positive）が発生する可能性があり、完全な正確性は保証されない。
- 要素そのものを復元することはできない。
- 標準的な実装では削除操作をサポートしない。
- カウンタ方式で削除を実現した場合、オーバーフローのリスクが生じる。