哈希函數的確定

我們如何找到這組字符串的最有效的哈希函數（碰撞的可能性最小）。哈希函數的確定

假設我們給了一些字符串..而字符串的長度也沒有定義。阿賈伊維傑拉祈彩 ....

我們知道的不計數。可用的字符串，所以我們可以設計一個大小的哈希表（可用的計數）。什麼可能是我們可以爲這樣的問題設計的完美散列函數？

以增量方式將每個字符的ascii值乘以31（主要編號）將導致散列值大於MAX_INT的值，然後模數將無法正常工作......所以請給出一些有效的散列函數構建up解決方案....

我有幾個字符串集，可以說count = 10 ....我需要實現一個哈希函數，使所有這10個字符串適合哈希表中的唯一...任何完美的散列函數O（1）都可用，對於這種問題??哈希表的大小將是10，這種情況下...

只有C語言編程...

請解釋邏輯在網站.... http://burtleburtle.net/bob/c/perfect.c 這看起來很複雜，但完美的我..！！這裏使用的算法是什麼......馬上閱讀代碼，非常困難！

謝謝....

2011-03-16 AGeek

哦，這些解決方案是沒有幫助親愛的....是否存在任何解決方案可以給出一組給定的字符串完美的哈希值..沒有字符串可能會非常大....完美的哈希解決方案！它是否存在..？ – AGeek 2011-03-16 19:05:34

@Necrolis推薦的gperf程序是一個實際工作的開源程序。您可以下載並查看源代碼，看看它是如何完成的。很難想象一個比這更好的例子。 – 2011-03-16 19:10:20

那麼這個網站上的代碼呢... – AGeek 2011-03-16 19:20:07

你可能要考慮perfect hashing.

2011-03-16 17:55:38

菲利普，你可以用一個例子來支持這個...如果我們有字符串...我們如何從這些字符串列表中得到一個整數（唯一）？ – AGeek 2011-03-16 18:42:45

@AGeek：如果你看一下Philipp鏈接的文章的「外部鏈接」部分，你會看到幾個完美的哈希生成器的免費實現。 – 2011-03-16 18:56:16

我需要一個代碼.... examplee ...在C程序中...並且需要一個完美的散列函數..它可以給出O（1）時間的結果.. – AGeek 2011-03-16 19:06:38

哈希表是爲了能夠處理動態輸入。如果你只能保證一組特定的輸入，並且你希望保證每個輸入的特定插槽，爲什麼散列呢？

只需爲每個已知的可用輸入建立一個數組索引。

2011-03-16 17:55:10

對於幾乎只讀訪問的大型數據集，使用類似完美哈希的東西可能是明智的。 – 2011-03-16 17:57:27

當你有一組已知的輸入並保證每個輸入有一個插槽時，爲什麼會有意義散列？您可以跳過散列函數的代價，並對每個「已知輸入」使用#defined索引進行數組查找。 – 2011-03-16 18:10:01

「已知輸入」是相對的。如果您知道您將隨機訪問在運行時提供的5GiB數據，則首先完全哈希以獲得O（1）訪問權限可能是個好主意。 – 2011-03-16 18:17:15

檢查一些這些了，他們apparantly具有良好的分佈

2011-03-16 17:57:11 deek0146

你可能想看看gperf，你可以有點做到這一點如果你不太經常這樣做，並且你的數據設置的很小，那麼你就可以在飛行中使用。如果字符串提前知道，那麼這是方法

2011-03-16 18:51:32 Necrolis

回答