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