スパースキースペースから密キースペースへのマッピング

私は、ブラウザを識別するUUIDを持つイベントのリストを持っています。この疎なキースペースを考えると、密なキースペースにマップしたいと思います。スパースキースペースから密キースペースへのマッピング

ブルームフィルタの他に、他にどのようなオプションがありますか？

64ビットの値にマッピングされたものがあれば、特にルックアップテーブルではなくアルゴリズムであれば完璧です。

出典

2011-01-12 François Beausoleil

ブルームフィルタを使用してマッピングを行う方法はありません。 Bloom Filtersは 'メンバーである 'という質問に' no'または 'maybe'で答えるためのものです。 –

イベントのリストが定数で動的でない場合は、最小完全ハッシュ関数を使用できます。

出典

2011-01-12 14:31:22 Tim

UUIDは実際のUUIDなので、2 ** 128の可能性があります。それは多くのアイテムです。 –

しかし、あらかじめ知られているUUIDのセットはありますか？そうでなくても、セットが頻繁に変更されない場合、CMPHのようなライブラリを使用して、適度に短い時間で完璧なハッシュ関数を生成することができ、非常に迅速に評価することができます。 – mokus

新しいUUIDは常に生成されます。後で遭遇するものはわからない。私たちはある程度の衝突を許容することができますが、明らかにこれができるだけ低いことが望ましいでしょう。 –

ゼロ衝突を保証するには、標準の辞書/シンボルテーブルアルゴリズムを使用します。それが彼らの行いなのです。

衝突を最小限にするために、あらゆる種類のハッシュ関数が利用できます。 Bob Jenkinsのlookup3.cはかなり人気があります。あなたが悪意を持って選んだUUIDの対象になるかどうかを尋ねなければなりません。もしそうなら、より良いハッシュ関数と安全なランダムな塩が必要です。（スピードを許すことができれば、キー付きHMACがこれを行うための完全な方法です）

出典

2011-01-13 03:02:33 Anonymous

スパースキースペースから密キースペースへのマッピング

答えて

関連する問題