Bloomフィルタとは？仕組みと使い方をわかりやすく解説

2025年10月28日

その他

大量のデータから「その要素が含まれていそうか」を素早く確かめたいとき、Bloomフィルタはとても便利です。

メモリをほとんど使わず、高速に「含まれていない」を確実に判定できます。

ここでは、初心者でも段階的に理解できるように、仕組みと使い方、応用例までわかりやすく解説します。

Bloomフィルタとは

何をするデータ構造か

Bloomフィルタは、要素が集合に含まれているかどうかを高速に調べるための確率的なデータ構造です。

内部ではビット配列と複数のハッシュ関数を使います。

「含まれていない」は確実に言えますが、「含まれている」はたまに間違える可能性があります。

この「たまに間違える」を小さく保つのが設計の要です。

直感的なイメージ

ひとつの要素に対して何個かのハッシュ関数をかけ、その結果の位置のビットを1にします。

照合時は、同じ位置がすべて1なら「含まれているかもしれない」、どれかが0なら「含まれていない」と判断します。

原始的に見えますが、うまく設計すると非常に効率的です。

できること/できないこと

できること

含有判定を高速かつ省メモリで行えます。
データそのものを保存しないため取り扱いが軽量です。
誤判定率の目標に合わせた設計が可能です。

できないこと

要素の列挙はできません(中身を取り出す用途には向きません)。
典型的な実装では削除ができません(後述)。
偽陽性は起きますが、偽陰性は起きません(含まれているのに「ない」とは言いません)。

用語

初心者がつまずきやすい用語を表でまとめます。

用語	意味
ビット配列(bit array)	0と1だけを並べた配列です。位置で管理します。
ハッシュ関数	入力を一定範囲の数値に変換する関数です。Bloomフィルタでは同じ入力に対して常に同じ結果になります。
k	使うハッシュ関数の個数です。
m	ビット配列の長さです。メモリ使用量に直結します。
n	登録予定の要素数です。設計時の見積もり値です。
偽陽性(false positive)	実際は含まれていないのに「含まれているかも」と出ることです。
偽陰性(false negative)	実際は含まれているのに「含まれていない」と出ることです。標準的なBloomフィルタでは発生しません。

Bloomフィルタは「偽陽性は起こり得るが、偽陰性は起こらない」という性質が核です。

どんなときに使うか

キャッシュの前段で「問い合わせる価値があるか」を素早くふるいにかけたいとき。
大量のURLやIDの重複チェックを高速にしたいとき。
データベースの存在確認をディスクI/Oなしで予測したいとき。
スパムやボットの疑い判定を本格チェック前に軽く行いたいとき。共通点は、誤判定が少しあっても困らないが、速度とメモリが重要な場面です。

Bloomフィルタの仕組み

追加の流れ

要素を追加するときは、次の考え方で進みます。

複数のハッシュ関数で位置を求め、その位置のビットを1にするだけです。

要素xに対してk個のハッシュを計算し、それぞれmの範囲に写像します。
得られたk個の位置のビットを全て1にします。 : この処理は同じ要素に対して何度行っても結果は同じで、他の要素とも自然に重なります。

照合(含まれるか)の流れ

照合では、該当するk個のビットが全て1になっていれば「含まれているかもしれない」、1つでも0なら「含まれていない」と判定します。

これにより「含まれていない」の判定は確実です。

誤判定(偽陽性)の意味

複数の別の要素がビットを1にしていくと、ある未登録要素のk個の位置も偶然すべて1になる場合があります。

これが偽陽性です。

偽陽性は設計時のパラメータで確率を小さく調整できます。

逆に偽陰性は発生しません。

ここが利用者にとっての安心材料です。

削除が難しい理由

ビット配列の1は複数の要素によって共有されています。

ある要素を消すためにビットを0に戻すと、他の要素が使っていた1まで消してしまい、偽陰性が発生します。

改善策としてカウンティングBloomフィルタ(各位置をビットではなく小さなカウンタにする方式)がありますが、メモリが増えるため初心者向けの基本的なBloomフィルタからは外れます。

パラメータ(ビット数/ハッシュ数)の目安

数学的な式は省き、実務で使いやすい目安を示します。

ターゲットの偽陽性率を決めると、1要素あたりの必要ビット数とkの目安が決まります。

目標偽陽性率	1要素あたりのビット数の目安	ハッシュ関数の数の目安	100万要素のメモリ目安
5%	約6.2ビット	約4〜5個	約0.78MB
1%	約9.6ビット	約7個	約1.25MB
0.1%	約14.4ビット	約10個	約1.80MB

現場では、kは「ビット数/要素数の約0.69倍」あたりが良い目安になります。

まずは1%前後から試し、必要に応じて下げると扱いやすいです。

メリット/デメリット

メリット: 圧倒的に省メモリで高速、構造が簡単、スケールしやすい。
デメリット: 偽陽性がある、標準形では削除不可、nの見積もりを誤ると性能が落ちる。

セット/ハッシュテーブルとの違い

ふだんのsetやdictと何が違うかを整理します。

観点	Bloomフィルタ	set(ハッシュセット)
判定	含まれていないは確実、含まれているはたまに誤判定	正確
追加/削除	追加は可能、削除は基本不可	追加/削除とも可能
メモリ	とても少ない	要素数に比例して増える
値の取得	できない	要素をそのまま保持
主な用途	ふるい分けの前段	最終的な正確な集合管理

Bloomフィルタは「一次フィルタ」、setは「最終確認」と覚えると使い分けが明確になります。

Bloomフィルタの使い方

Python実装のイメージ

ここでは標準ライブラリだけで動く最小イメージを示します。

本番では最適化や既存ライブラリの利用を検討してください。

Python

import hashlib

class BloomFilter:
    def __init__(self, m, k):
        self.m = int(m)  # ビット数
        self.k = int(k)  # ハッシュの数
        self.bits = bytearray((self.m + 7) // 8)

    def _indices(self, data: bytes):
        # ダブルハッシング: 2つのハッシュからk個の位置を作る
        h1 = int.from_bytes(hashlib.sha256(data + b'#1').digest(), 'big')
        h2 = int.from_bytes(hashlib.sha256(data + b'#2').digest(), 'big')
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        b = item.encode('utf-8') if isinstance(item, str) else bytes(item)
        for idx in self._indices(b):
            self.bits[idx >> 3] |= 1 << (idx & 7)

    def __contains__(self, item) -> bool:
        b = item.encode('utf-8') if isinstance(item, str) else bytes(item)
        for idx in self._indices(b):
            if ((self.bits[idx >> 3] >> (idx & 7)) & 1) == 0:
                return False
        return True

# 例: 目標1%程度、100万件想定なら m=10_000_000, k=7 が目安
bf = BloomFilter(m=10_000_000, k=7)
bf.add('apple')
print('apple' in bf)   # True (追加済み)
print('orange' in bf)  # たまにTrueになることがある(偽陽性)

Pythonの組み込みhash関数は実行ごとに結果が変わることがあるため避け、hashlibのような安定した関数を使います。

ハッシュ関数の選び方

初心者はまず、hashlib.sha256のような安定ハッシュで十分です。

速度が重要なら、mmh3(MurmurHash3)やxxhashのような高速非暗号ハッシュを検討します。

複数の独立なハッシュ関数を用意する代わりに、ダブルハッシングで2つのハッシュからk個の位置を作ると実装が簡単で高速です。

パラメータの決め方

まず、登録予定の最大要素数nを見積もります。
許容できる偽陽性率を決めます(例: 1%)。
上の目安表から、1要素あたりのビット数とkを選び、mを計算します。例えばn=1,000,000、1%ならm=約9,600,000ビット(簡単に10,000,000ビットに丸める)、k=7が使いやすいです。
迷ったら1%・10ビット/要素・k=7を起点にし、実測で調整すると安全です。

ライブラリ/ツール

言語や環境ごとに成熟した実装があります。

本番環境では実績のあるライブラリを使うのが安心です。

Python: bloom-filter2、pybloom-live、bitarrayとの組み合わせ
Java: GuavaのBloomFilter
C/C++: folly、libbloom
ストレージ・サーバ: RedisBloom(Redisモジュール)、RocksDBのBloomフィルタ、Apache HBase/BigtableのBlock Bloom