爲什麼這是一個糟糕的散列函數？

我目前覆蓋哈希和哈希表，我想知道爲什麼像被認爲是不好的散列函數（僞）以下：爲什麼這是一個糟糕的散列函數？

function hash(String_t word, Int table_size) 
    i = randomly generated number with 0<i<table_size 
    j = ASCII code of the first letter of word 

    return i * j % table_size

假設的i價值可能在函數調用存儲爲了實現一致性（例如使用C中的static關鍵字將i的值存儲在函數範圍內），爲什麼這是一個糟糕的哈希函數？

來源

2016-05-11 JavascriptLoser

一個好的散列函數應該適用於各種輸入大小，只有條件是表大小是一個常數倍大於輸入數。由於以下幾個原因，這不符合該標準：

散列值僅由第一個字母確定。因此，可能的散列值的總數受限於可能的第一個字母的數量，該數字很小。爲大量輸入選擇較大的表格大小沒有任何影響：您仍然會遇到大量碰撞。
由於第一個單詞的字母非常不均勻分佈，所以會產生很多衝突。至少在定義你的函數時使用單詞的所有字母，但你真的需要的不僅僅是那個建議來拯救這個構造。
定義d = gcd（i，表格大小）。在某些情況下，d將大於1，在這種情況下，表格中每個d元素中只有一個元素將有機會被填充：其他元素將會浪費空間（並因此導致更多的碰撞）。也就是說，只有0，d，2d，3d ......可能是一個散列值。至少限制在d = 1的i值，以防止這些退化情況。
我乘以j的最大值偶爾會小於表格大小（當我很小時），這意味着表格的頂端永遠不會被觸摸。浪費更多的空間。

人們通常會試圖想出散列函數，這些散列函數在一般情況下運行良好，並且您可以證明它們的優點。在這裏，你有一個特定的案件的意圖，什麼是最明顯的負面情況，所以非常非常懷疑，你可以證明這個構造的任何積極的事情。「

來源

2016-05-11 11:19:02 TheGreatContini

」散列值僅由第一個字母確定「。散列值是不是由第一個字母和隨機值決定的？另外，d = gcd（i，表格大小）是什麼意思？ – JavascriptLoser

@PythonNewb：取決於你如何看待它！按照我觀察它的方式，隨機值在開始時選擇，然後固定。在該值固定後，如果且僅當它們具有相同的第一個字母時，兩個單詞纔會發生碰撞。 Gcd是最大的公約數。該屬性來自模塊算術。 – TheGreatContini

爲什麼這是一個糟糕的散列函數？

回答

相關問題