hash - OpenCLの完璧なハッシュ

Question

私は約200万の値、それぞれ20バイトのセット（静的、コンパイル時に知られています）を持っています。私が必要としているのは、与えられた値がこのセットにあるかどうかをチェックするための高速なO（1）方法です。これにはビット配列を使用した完全なハッシュ関数が理想的であるように思われますが、それを作成する簡単な方法を見つけることができません。gperfなどのユーティリティがいくつかありますが、それらは複雑すぎます。また、私の場合、100％に近い負荷率である必要はなく、10％でも十分ですが、衝突がないことが保証されています。この関数のもう1つの要件は、多くの条件がない単純さです。GPUで実行されます。この場合、あなたは何をアドバイスしますか？

Answer 1

ここで私の答えを見てください。問題は少し異なりますが、ソリューションはニーズに合わせて調整できます。オリジナルは 100% の負荷率を使用していますが、これは簡単に変更できます。これは、起動時に配列をその場でシャッフルすることによって機能します (これはコンパイル時に行うことができますが、生成されたコードをコンパイルすることを意味します)。

ハッシュ関数の WRT: 20 バイト オブジェクトの内容について何も知らない場合は、適切なハッシュ関数 (FNV、Jenkins、または私のもの) で十分です。

Answer 2

完全ハッシュに関する詳細を読んだ後、私はそれを実装しようとしないことに決め、代わりに cuckoo hashtable を使用しました。それははるかに単純で、完全なハッシュのために 1 回ではなく、テーブルへの最大 2 回のアクセス (または 1 より大きいその他の数。最もよく使用されるのは 2..5) です。