perfect-hash - 最小限の完全なハッシュ関数

Question

[0;の範囲に多くの整数があります。2^63-1]。ただし、整数は10^8しかありません。重複はありません。完全なリストはコンパイル時に知られていますが、それは単なる一意の乱数です。これらの数値は変更されません。
1つの整数を明示的に格納するには、8バイトが必要であり、1バイトの値が関連付けられているため、明示的に格納するには約860MBが必要です。
したがって、[0; 2^63-1]から[0;10^8-1]までの10^8個の整数のそれぞれをマップするための最小限の完全なハッシュ関数を見つけたいと思います。この関数は一度だけ見つける必要があり、データが変更されることはなく、関数が複雑になる可能性があります。しかし、それは最小限で完璧でなければならず、計算は高速でなければなりません。どうすればこれをより良くすることができますか？たぶん、それらが発生した場合、いくつかのサブシーケンスを見つけて使用することは可能ですか？
ありがとう。

Answer 1

あなたのコンピュータにあなたのために仕事をさせてください：

http://www.gnu.org/software/gperf/

引用：「GNUgperfは完璧なハッシュ関数ジェネレーターです。指定された文字列リストに対して、入力文字列に応じて値を検索するためのハッシュ関数とハッシュテーブルをCまたはC++コードの形式で生成します。ハッシュ関数は完璧です。つまり、ハッシュテーブルには衝突がなく、ハッシュテーブルのルックアップには単一の文字列比較のみが必要です。」

Answer 2

キーあたり1.6ビット未満を必要とするアルゴリズムとJavaの実装に取り​​組んでいます。

以前、キーごとに2.0ビット未満を必要とする最小限の完全なハッシュ関数ツールをJavaに実装しました。

他のアルゴリズムはCMPHに実装されています。たとえば、CHDはデフォルトでキーごとに約2.06ビットを必要とします。より少ないスペースを使用するように構成できますが、生成は遅くなります。