試圖散列字符串統一的哈希表？

Question

我目前在學期末附近的數據結構課程中，並且已經分配了一個項目，我們正在實施鏈接哈希表來存儲和檢索密鑰。我們已經被賦予了相當大的自由度，我們將如何設計我們的哈希表實現，但是對於獎勵要點，我們被告知要嘗試找到一個散列函數，它將我們的密鑰（唯一字符串）一致且隨機地桌子。

我已經選擇了使用ELF散，看到這裏http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

我的問題是：有了這個哈希函數返回一個整數，但我無法看到這是如何用於幫助指定將我的密鑰放入散列表中。我可以簡單地這樣做：index = ELFhash（String key）％tableSize，但是這是否會破壞首先使用ELF哈希的目的？

此外，我選擇了我的衝突解決策略爲雙重哈希。有沒有一種很好的方法來確定一個合適的二次哈希函數來查找跳轉？我的哈希表不會是一個常量大小（字符串集將被添加並從我哈希的數據集中刪除，我將在每次添加和刪除迭代之後重新哈希它們以使負載因子爲.75 ），所以我很難做出像k％n這樣的事情，其中​​n是一個與我的表格大小相對的數字。

感謝您花時間閱讀我的問題，並讓我知道您的想法！

Answer 1

你想想「包裝偏見」是正確的，但對於大多數實際目的來說，這不會是一個問題。

如果散列表的大小爲N，並且散列值在[0..M）的範圍內，則讓k = floor(M/N)。在[0..k*N)範圍內的任何散列值都是「好」的，因爲使用mod N作爲映射，每個散列桶映射的確實是k散列值。 [k*N..M)中的散列值是「壞」的，因爲如果使用它們，則相應的M-K*n最低散列桶將從一個附加散列值映射。即使哈希函數是完美的，這些桶具有更高的接收給定值的概率。

但問題是「多高？這取決於M和N.如果哈希值是unsigned int,[0..2^32)，並且 - 讀過Knuth和其他人 - 你決定選擇大約一千個桶的素數，比如說1009，會發生什麼？

floor(2^32/1009) = 4256657 

的「壞」值數爲

2^32 - 4256657 * 1009 = 383 

因此，所有的桶從4256657「好」值映射，以及383獲得一個額外的不利的「壞」的價值4256658.因此， 「偏見」爲1/4,256,657。

這是非常不可能的，你會發現一個散列函數，其中桶之間的概率差異是百分之四十是明顯的。

現在，如果您重新計算數百萬個桶而不是一千個，那麼情況會有所不同。在這種情況下，如果你有點OC，你可能想切換到64位散列。

另外還有一件事：精靈哈希不太可能給出絕對可怕的結果，而且速度相當快，但是哈希函數有更好的表現。一個相當受人重視的人，你可能想嘗試一下是Murmur 32。（這篇Wiki文章提到原始alg有一些弱點可以用於DoS攻擊，但是對於你的應用程序來說它沒問題。）我確定你的教授不希望你複製代碼，但Wikipedia頁面有它完成。自己實施Elf並嘗試對付Murmur來看看他們的比較會很有趣。