什麼是存儲大型隨機數的最佳散列函數？

Question

我想在數據結構中存儲大量數據，爲此，我想使用散列函數，以便插入，刪除或搜索可以很快。但我無法決定使用哪個哈希函數？

而且一般情況下，我想知道如何確定散列函數對任何特定問題都有好處？

編輯：我認爲一個讓人混淆的術語「隨機」。這裏隨機的，我的意思是，我沒有任何特定範圍的數字，我必須選擇[任何32位整數]，但我有總數不會存儲在數據結構中，例如5000個數字。因此，建議我爲這種情況提供最好的散列函數，爲什麼你認爲它是最好的？

Answer 1

如果這些數字是一致的隨機數，只需使用選擇低位的散列函數即可。

unsigned hash_number(long long x) 
{ 
    return (unsigned) x; 
} 

Answer 2

你的問題對我沒有意義。使用散列算法來存儲一些隨機數字是矯枉過正的。如果問題還有更多的話，那麼數據結構的選擇將取決於更多的東西（你不這麼說）。

如果這些數字確實是隨機數或僞隨機數，那麼您只需要一個堆棧或循環緩衝區 - 將新的隨機數添加（推送）到數據結構中的能力以及刪除（彈出）現有隨機數從結構。如果您想按順序檢索它們，請使用循環緩衝區。哈希函數在每個方面都比一個簡單的堆棧（或循環緩衝區）更糟，用於保存隨機數列表 - 它更復雜，運行速度更慢，並使用更多的內存。

大多數語言/環境都提供散列函數，可以使用（或提供）「字典」類，這些函數與效率有關。通常，您可以通過分配更多內存來加快字典類的速度 - 當散列鍵發生衝突時，它們會減慢速度。因此，所有可能的數字中實際數字的「密度」很重要。

所以，如果你不得不保存100個這樣的數字，你可以使用只查看最後12位的散列函數。這給出了2^12 = 4096個可能的哈希值，所以碰撞只會發生在100/2048的時間內，小於5％。另一方面，你使用的內存數量應該超過20倍。 （該函數與以2^12爲基數的數字的模數相同，並且與Epp建議的類似）。

基於散列函數編寫存儲類，該函數可正確處理散列衝突（因爲它必須），優雅地處理重複的數據，如果你挑選不好的數據（如每個數字相同），並且高效，不會變得怪異，這不是一件小事。

另一方面，實現堆棧或循環緩衝區非常簡單，非常有效，並且具有完全可預測的行爲。

你確定你沒有把它做得比它需要的更復雜嗎？

Answer 3

即使您的輸入數字是完全隨機的，使用h（x）= x仍可能會造成性能問題。從圖中可以看出，你的號碼是從0,2,4，...，2k隨機選出的，儘管是隨機的，但它們都不會被映射到哈希表的第一個桶（桶0），假設兩個桶大小的功率。因此，真正重要的是輸入數字的信息熵。

在你的情況下，一個很好的選擇是Thomas Wang的整數散列函數，它是可逆的並且保持良好的雪崩效應（http://en.wikipedia.org/wiki/Avalanche_effect）。有一篇文章描述了Thomas Wang的哈希函數及其逆函數：http://naml.us/blog/2012/03。