對未知輸入具有良好均勻性的散列函數

我正在尋找一個散列函數，它將一大組輸入數據以良好的均勻性分區到少數分區（比如說100或 256）。這意味着我期望有很多碰撞，我不關心碰撞。對未知輸入具有良好均勻性的散列函數

輸入數據未預先知道。我預計長度爲的字符串可能在6到100個字節之間。這些字符串可能分佈不均勻（例如大部分填充空格或僅包含數字）。

CRC算法是首先想到的想法之一。 CRC8已經提出，但沒有提供有關其統一性的信息;對於CRC32顯然是uniformity is not that good。

有一系列simple或general purpose散列函數，但沒有告訴它們的一致性。

Bob Jenkins在散列函數上有一個完整的article，該散列函數返回一個 32位值。我想對於均勻分佈的32位值也應該均勻分佈所有可能的8位子集，所以是很好的候選者。但是，如果8位的算法比較簡單，那麼將32位值減小爲8位值可能會矯枉過正？

來源

2011-12-20 pesche

伯恩斯坦的哈希至極是詹金斯的頁面上也一點也不壞，這是死的簡單。當需要「只是一些散列」時，我正在使用它。沒有任何問題。如果你擔心它不是「足夠隨機」的，你甚至可以將添加劑和異或變量合併成一個，這通常會流水到相同的循環次數。請注意，CRC的設計原理主要不是爲了產生散佈良好的散列，而是爲了檢測意外的位翻轉。 – Damon 2011-12-20 13:09:54

在使用本機寄存器大小（32位）進行計算時不會有任何懲罰，大多數操作都是在（符號）操作數擴展到本地int大小之後執行的。截斷（或取模）將是便宜的（但不是免費的）。並非所有散列函數在最右邊的位都有足夠的熵。 – wildplasser 2011-12-26 14:53:29

我發現SDBM算法表現出良好的均勻度，是相當簡單：

 h := 0. 
     forEach ch in str { 
      h := (h * 65599) + ch; 
     }

來源

2011-12-26 12:28:03 blabla999

對未知輸入具有良好均勻性的散列函數

回答

相關問題