私は範囲[0; 2^63-1]。しかし、10^8の整数しかありません。 は重複なしです。完全なリストはコンパイル時に知られていますが、というユニークな乱数です。これらの番号は決して変更されません。
1つの整数を明示的にに格納するには、8バイトが必要です。関連付けられた1バイトの値があるため、明示的な格納には約860 MBが必要です。
私は[0; 2^63-1]から[0; 10^8-1]までの10^8の整数のそれぞれをマップするために、最小完全ハッシュ関数を見つけたいと思っています。私はこの機能を一度だけ見つけて、データは決して変わらず、機能は複雑になるはずです。しかし、それは最小限で完璧で、計算は速くなければなりません。どのように私はこれをより良くすることができますか？もし起これば、いくつかのサブシーケンスを見つけて使うことは可能でしょうか？
ありがとうございます。最小完璧なハッシュ関数
お使いのコンピュータがあなたのために仕事をしてみましょう：
http://www.gnu.org/software/gperf/
引用：「GNUのgperfのある文字列の特定のリストについては、それはハッシュ関数とハッシュテーブルを生成し、完璧なハッシュ関数ジェネレータ、入力文字列に応じて値を参照するためのCまたはC++コード形式のハッシュ関数です。ハッシュ関数は完全です。つまり、ハッシュテーブルには衝突がなく、ハッシュテーブル参照には単一の文字列比較のみが必要です。 "
ですが、非常に大きなキーセットに対して最小限の完全なハッシュ関数を作成することが考えられているので、[CMPH]（http://cmph.sourceforge.net/）の方が優れています。 –
ありがとう、おそらく私は両方を試みます。 –
私はan algorithm and Java implementation that needs less than 1.6 bits per keyに取り組んでいます。
以前は、キーあたり2.0ビット未満を必要とするa minimal perfect hash function tool in Javaを実装しました。
その他のアルゴリズムはCMPHに実装されています。たとえば、CHDにはデフォルトで約2.06ビット/キーが必要です。スペースを少なくするように設定できますが、生成は遅くなります。
私は、1エントリあたり1.58ビット未満必要な改善されたアルゴリズムに取り組んでいます。 –
あなたのコードを書いてください。私は長いデータ型のために実装しようとしましたが、indexoutofboundsエラーが発生しました – sss999
@ sss999現在のところ多くのドキュメントはありません。あなたはテストケースを読むことができます。テストケースと例外を含む[問題]（https://github.com/thomasmueller/minperf/issues）を作成する可能性があります。 –
コンパイル時に全リストが分かりますか？私の助言は、あなた自身が数字を「手動で」割り当てることであり、あなたのプログラミング言語で地図の静的宣言を吐き出すためのスクリプトを書くことです。決して変わらない場合は、静的なデータ構造を使用して値を完全にマッピングすることが理想的なソリューションになります。私はあなたが明らかに手でそれをするつもりはないので、逆のカンマで「手動で」言う。他のコメントと回答を参照して、どのツールで割り当てを行うことができるかを確認してください。 – darvids0n