什么是良好的哈希函數？我在大學的數據結構課程中看到了很多哈希函數和應用程序，但是我大多數都知道要創建一個好的哈希函數非常困難。為了避免發生沖突，我的教授說：function Hash(key) return key mod PrimeNumberend（mod是C和類似語言的％運算符）質數應為哈希表的大小。我知道這是一個不錯的功能，可以避免碰撞，而又可以避免快速碰撞，但是我怎樣才能制造出更好的呢？是否有針對數字鍵的字符串鍵更好的哈希函數？
3 回答
白板的微信
TA貢獻1883條經驗 獲得超3個贊
沒有通用哈希的“良好哈希函數”之類的東西（是的，我知道有“通用哈?！敝惖臇|西，但這不是我的意思）。取決于上下文，不同的標準確定哈希的質量。已經有兩個人提到SHA。這是一個加密哈希，對于哈希表（您可能要說的）根本沒有好處。
哈希表有非常不同的要求。但是，仍然很難普遍地找到一個好的哈希函數，因為不同的數據類型會公開不同的可以哈希的信息。根據經驗，最好將一種類型的所有信息均等地考慮在內。這并不總是那么容易甚至不可能。出于統計原因（并因此產生沖突），在問題空間（即所有可能的對象）上產生良好的分布也很重要。這意味著，當對100到1050之間的數字進行哈希處理時，讓最高有效位在哈希表中扮演重要角色是不好的，因為對于90％的對象，該數字將為0。讓最后三個數字更重要數字確定哈希。
同樣，在對字符串進行哈希處理時，考慮所有字符也很重要–除非事先知道所有字符串的前三個字符都相同，考慮這些便是浪費。
實際上，這是我建議閱讀Knuth在《計算機編程藝術》第一卷中說的內容之一。3.另一本好書是朱麗安·沃克（Julienne Walker）的《散列的藝術》。
qq_笑_17
TA貢獻1818條經驗 獲得超7個贊
哈希函數有兩個主要目的：
將數據點均勻分散到n位。
安全地識別輸入數據。
不知道您要使用的哈希是不可能推薦哈希的。
如果您只是在程序中創建哈希表，則無需擔心該算法的可逆性或可破解性……SHA-1或AES對此完全沒有必要，最好使用FNV的變體。FNV與您提到的簡單質數調制相比，具有更好的分散性（從而減少了沖突），并且更適應于各種輸入大小。
如果您使用散列來隱藏和驗證公共信息（例如對密碼或文檔進行哈希處理），則應使用由公眾審查審查的主要哈希算法之一。哈希函數休息室是一個不錯的起點。
添加回答
舉報
0/150
提交
取消