函數計算哈希數，它到底做了什麼，爲什麼？

我知道這個函數正在做一些哈希數字，，但不明白這個函數的目的是什麼？爲什麼「res * 31 + * key」？爲什麼31？函數計算哈希數，它到底做了什麼，爲什麼？

unsigned int HashAlg(char* key) 
{ 
    unsigned int res = 0; 

    while (*key != 0) 
    { 
     res = res * 31 + *key; 
     ++key; 
    } 

    return res; 
}

來源

2013-03-19 Yuval

可能的重複[爲什麼Java的hashCode（）在字符串中使用31作爲乘數？]（http://stackoverflow.com/questions/299304/why-does-javas-hashcode- in-string-use-31-as-a-multiplier） – Rudi 2013-03-19 16:32:39

爲什麼「資源* 31 + *鍵」

假設，如果它只是res = res + *key發生了什麼;那麼散列會將所有的值加起來。這將產生相同的散列，像hello，elloh，olleh，loleh等排列的字符串。乘以大於1的值使得這種可能性更小。

爲什麼31？

可能是爲了避免2的權力，它會簡單地向左移動一個值，並在幾個班次後丟失值。 2的非冪次可以避免這個問題。

來源

2013-03-19 12:01:15 Jens

你好，請你詳細解釋一下「爲什麼31」的更多細節？ – Yuval 2013-03-19 12:39:45

那麼，爲了在輸入範圍內接近散列的均勻分佈並避免散列衝突，有幾個數學原因可以選擇一個素數並避免兩次冪。 – Jens 2013-03-19 12:48:35

好的，素數如何幫助這裏？ – Yuval 2013-03-19 12:54:01

該實現是D.J.的乘法字符串散列函數的變體。伯恩斯坦：

unsigned djb_hash (void *key, int len) 
{ 
    unsigned char *p = key; 
    unsigned h = 0; 
    int i; 

    for (i = 0; i < len; i++) 
    h = 33 * h + p[i]; 

    return h; 
}

的散列函數的目的等這些是映射的搜索鍵，像字符串"item1"，向其中然後可以在哈希表中使用的索引，高速緩存等;簡單地說，散列值給了我們表格中應該存儲"item1"的相應記錄的位置。哈希表反過來用於實現關聯數組和動態集。欲瞭解更多詳情，我建議從Wikipedia page開始。

您可以看到，在您的實施中，常數33已切換爲31。沒有什麼真正的數學工作可以明確證明素數和哈希函數之間的關係。在散列函數中使用素數的基本概念圍繞轉換散列函數的當前狀態的概念（應用某種形式的數學運算，例如乘法或對散列值的加法）。結果被限制爲新的散列值，其應該在統計學上具有較高的熵值或者換句話說對於新散列值中的任何位都具有非常低的位偏置。簡而言之，當你用一個素數乘以一組隨機數時，所得到的數字（當在一個比特級上分析時）應該不顯示是一種狀態還是另一種狀態，即P(Bi = 1) ~= 0.5。沒有具體的證據證明情況是這樣，或者只發生在素數上，它似乎是我們似乎必須遵循的持續的自我宣傳直覺。這些屬性是後驗判斷的，這意味着我們嘗試用選定的常量分析散列函數（或PRNG）屬性，並開發一種常數「運行良好」的直覺，即生成特定分佈或演示雪崩效應，產生一個均勻分佈特定的一組輸入等

來源

2013-03-19 12:02:37

好吧，你希望散列函數儘可能以均勻分佈生成所有的值，所以你想使用一個常量，使得（_n_ * _k_）％_table_size_可以產生所有的值0到_table_size_。_k_與_table_size_不能共同被整除的情況就是這種情況。素數不能與除自身以外的任何其他物質共同分割，所以它們是最安全的選擇。 – 2013-03-19 12:21:27

不是最安全的先驗，但肯定是首先要考慮的。 – 2013-05-31 12:59:51

函數計算哈希數，它到底做了什麼，爲什麼？

回答

相關問題