我有很多整數範圍[0; 2^63-1]。然而，只有10^8個整數。有沒有重複的。完整列表在編譯時已知，但它是只是唯一的隨機數。這些號碼絕不會改變。
要存儲一個整數明確，需要8個字節，並且有關聯的1個字節的值，所以顯式存儲需要大約860 MB。
所以我想找到最小的完美哈希函數來將10^8個整數從[0; 2^63-1]映射到[0; 10^8-1]。我只能找到這個函數一次，數據永遠不會改變，而且函數可能很複雜。但它應該是最小的，完美的，並且計算應該是快速的。我怎麼能做得更好？也許有可能找到並使用一些子序列，如果它們發生？
謝謝。最小完美哈希函數
讓你的電腦爲你做的工作：
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。
以前，我已經實現a minimal perfect hash function tool in Java，每個密鑰需要少於2.0位。
其他算法在CMPH中實現。例如，默認情況下，CHD每個密鑰需要大約2.06位。它可以配置爲使用較少的空間，但生成速度較慢。
我正在研究改進的算法，每個條目需要少於1.58位。 –
你有沒有爲你的代碼寫任何東西。我試圖實現它的長數據類型，但得到indexoutofbounds錯誤 – sss999
@ sss999目前沒有太多的文檔;你可以閱讀測試用例。也許創建一個[問題]（https://github.com/thomasmueller/minperf/issues）與一個測試用例和異常，所以我可以看看問題可能是 –
編譯時已知的完整列表嗎？那麼我的建議就是「自己手動」分配數字，然後編寫一個腳本來以所需的編程語言吐出靜態聲明。如果它永遠不會改變，那麼使用靜態數據結構來完美映射這些值將是您理想的解決方案。我用引號說'手動'，因爲你顯然不會手動完成。查看其他意見和答案，瞭解哪些工具可以爲您分配資源。 – darvids0n