偽陽性を許容して空間効率良くキーの存在を確認するBloom filterとCuckoo filter - sambaiz-net
例えばデータストアへのアクセス抑制のためにキーの存在を確認する際、 全てのキーを保持して探索すれば100%正しく判定できるが、キーが長く数が膨大になるとメモリの使用量が問題になることがある。 もし偽陽性が許容できるなら、次のフィルタを使うことで空間効率良くキーの存在を確認できる。 Bloom filter 1970年に考案されたフィルタで、 LevelDBやCassandraで使われている。 GoogleのkvsライブラリLevelDBを使う - sambaiz-net 初期値0のビット配列と、そのいずれかのビットにデータをマッピングするk個のハッシュ関数を定義し、 含めるデータを各ハッシュ関数に通して、マッピングされたビットを1に更新していく。 これにより、いずれかのハッシュ関数によって0のビットにマッピングされるデータは、必ずフィルタに含まれないことが分かる。 また、ビット配列のAND
MD5のハッシュ値オールゼロに挑戦 - わさっきhb
いきなりですが問題です． MD5のハッシュ値（チェックサム，fingerprint，メッセージダイジェスト）がすべて0となるような，入力メッセージを答えなさい． さっそくですが解答…いや，答えは知りません．もし，そんな入力メッセージを得ていたら，弱衝突耐性を破ったってことになります．そんな入力があるかどうかも，分かっていません． そこで，もっと簡単な問題にします． MD5のハッシュ値の先頭32ビット（16進出力では最初の8桁）がすべて0となるような，入力メッセージを答えなさい． これくらいだと，計算機をぶん回せば，答えが出てきそうです．情報セキュリティの試験も終わったことですし，Rubyスクリプトを書いてみました． Find all-zero hash · GitHub 少し気をつかったことが2つ，あります．一つは，入力メッセージをどのように生成するかです．乱数を使うと，周期の問題がありま
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
