c - hashing資料結構 - hashing演算法



如何在C中編寫哈希函數? (2)

加密哈希強調使任何人都難以故意創建衝突。 對於哈希表,重點通常是快速產生合理的結果傳播。 因此,這兩者通常是完全不同的(特別是,加密散列通常慢得多)。

對於典型的散列函數,結果僅受類型限制 - 例如,如果它返回size_t,則返回任何可能的size_t完全沒問題。 您可以將輸出範圍縮小到表格的大小(例如,使用除以表格大小的餘數除以表格的大小,通常應該是素數)。

舉個例子,一個相當典型的普通哈希函數可能看起來像:

// warning: untested code.
size_t hash(char const *input) { 

    const int ret_size = 32;
    size_t ret = 0x555555;
    const int per_char = 7;

    while (*input) { 
        ret ^= *input++;
        ret = ((ret << per_char) | (ret >> (ret_size - per_char));
   }
   return ret;
}

這裡的基本思想是讓輸入字符串的每一位都影響結果,並且(盡可能快地)使結果的每一位都受到至少部分輸入的影響。 請注意,我並不是特別推薦這個作為一個很好的哈希函數 - 只是試圖說明你想要完成的一些基礎知識。

https://src-bin.com

哈希表被認為是存儲/檢索數據的最快/最好的方式。

我對哈希表的理解,哈希如下(請糾正我,如果我錯了或請添加如果還有更多):

  • 哈希表只是一個存儲值的數組(單維或多維)。
  • 散列是在數組中查找索引/位置以插入/檢索數據的過程。 您獲取一個數據項並將其作為鍵傳遞給散列函數,您將獲得索引/位置插入/檢索數據的位置。

我有個問題:

哈希函數是否用於存儲/檢索安全應用程序中用於MD5,HMAC,SHA-1等認證的加密哈希函數中的數據DIFFERENT?

它們以什麼方式不同?

  • 如何在C中編寫哈希函數?
  • 它有一些標准或指導方針嗎?
  • 我們如何確保哈希函數的輸出,即索引不超出範圍?

如果你能提一些好的鏈接來更好地理解這些,那就太好了。


Answer #1

設計目標不同。

例如,使用加密哈希函數 ,哈希和哈希函數不能用於確定原始數據或產生相同哈希的任何其他數據。

與哈希表和其他數據結構一起使用的哈希函數不需要這樣的安全屬性。 如果散列函數很快並且它會將輸入集均勻地分配到可能的散列集中(以避免不必要的聚類/衝突),這通常就足夠了。





hash-function