冰凍非一日之寒
上一篇文章中，我們舉了身份證號(hào)為關(guān)鍵字的例子。這里，我們假設(shè)真的有一個(gè)無限大的空間，那么，可以直接將身份證號(hào)作為索引嗎？
顯然不合適。因?yàn)?，并不是所有的身份證號(hào)都是18位的，對(duì)于那些位數(shù)在17位以下的，就太浪費(fèi)這個(gè)大空間了。
設(shè)計(jì)哈希函數(shù)的原則是，將我們所關(guān)心的鍵通過哈希函數(shù)求出索引，“鍵”通過哈希函數(shù)得到的“索引”分布越均勻越好(實(shí)際上，實(shí)現(xiàn)起來非常困難)
那么，對(duì)于像身份證號(hào)這樣的大整數(shù)為關(guān)鍵字時(shí)，該怎么計(jì)算對(duì)應(yīng)的索引呢？
或者像復(fù)合類、字符串、浮點(diǎn)數(shù)這樣類型的關(guān)鍵字，該如何計(jì)算它們對(duì)應(yīng)的索引呢？
對(duì)于哈希函數(shù)來說，我們只能將整型數(shù)據(jù)作為關(guān)鍵字來求解索引。所以，不管什么類型的關(guān)鍵字，我們應(yīng)該先將其轉(zhuǎn)化為整型類型的數(shù)據(jù)。
按照這個(gè)思路，以下介紹幾種最簡單、最基礎(chǔ)、最一般、最通用的哈希函數(shù)
整型
小范圍正整數(shù)直接使用
例如，上一篇講的ASCII值作為關(guān)鍵字
再例如，一個(gè)班有30個(gè)學(xué)生，1—30表示每位學(xué)生對(duì)應(yīng)的學(xué)號(hào)，并作為關(guān)鍵字
像這樣的小范圍正整數(shù)，可以直接將關(guān)鍵字作為索引，存儲(chǔ)到數(shù)組中去
小范圍負(fù)整數(shù)進(jìn)行偏移
例如，-100～100的數(shù)作為關(guān)鍵字，這時(shí)可以每個(gè)數(shù)都加上100，變?yōu)?～200的正整數(shù)
這樣，就可以將關(guān)鍵字直接作為索引存儲(chǔ)到數(shù)組中去
大整數(shù)取模
例如，身份證號(hào)作為關(guān)鍵字，412637199707096354
取后四位(6354)。也就是，mod 10000
假如，取后六位(096354)。即，mod 100 0000 這樣，會(huì)分布不均勻
對(duì)于身份證號(hào)來說，后六位的前兩位(09)代表著日期數(shù)，也就是1～31的數(shù)字。那么，這個(gè)六位數(shù)不會(huì)達(dá)到32 0000這么大，中國這么多人口，顯然這個(gè)數(shù)字是不夠的，這也就造成了索引分布不均勻
這也就體現(xiàn)了哈希函數(shù)的復(fù)雜性，也說明了具體問題要具體分析。
上面的取模方式還有一個(gè)問題，沒有有效利用所有信息。我們這樣取模，只是利用了關(guān)鍵字的一部分，也就是不管這個(gè)人是哪個(gè)地區(qū)哪個(gè)年份出生的，都有可能存儲(chǔ)到一個(gè)地址中去，這樣會(huì)增加哈希沖突的概率。那么，該如何解決這個(gè)問題呢？
一個(gè)簡單的解決辦法：模一個(gè)素?cái)?shù)
為什么要模一個(gè)素?cái)?shù)呢？簡單舉個(gè)例子
顯然，模一個(gè)素?cái)?shù)，結(jié)果會(huì)分布的更均勻，哈希沖突的概率也會(huì)變小。我們?cè)撊绾芜x擇這個(gè)素?cái)?shù)呢？相關(guān)的領(lǐng)域?qū)＜乙呀?jīng)為我們研究出了答案。
假如，需要存儲(chǔ)的數(shù)在2^5～2^6之間，模上53就可以了。
注：這個(gè)表并不是唯一的，一個(gè)區(qū)間內(nèi)可以有多個(gè)素?cái)?shù)
浮點(diǎn)型
將浮點(diǎn)型解析成大整型，之后再相應(yīng)取模(如上)
字符串
先看一個(gè)例子
把一個(gè)整數(shù)用科學(xué)計(jì)數(shù)法來表示，同樣，字符串也可以類似表示。將這個(gè)字符串看成26進(jìn)制，是因?yàn)橛?6個(gè)小寫字母，如果字符串中有大寫字母或者標(biāo)點(diǎn)符號(hào)，那么看成26進(jìn)制顯然是不夠的，可以看成是100進(jìn)制或者256進(jìn)制等。顯然，這個(gè)進(jìn)制是用戶可以自己選擇的，我們用 B 來表示這個(gè)進(jìn)制
每一個(gè)小寫字母對(duì)應(yīng)一個(gè)數(shù)字，這樣我們把字符串也轉(zhuǎn)化成了大整型，之后就可以利用上面取模的方式計(jì)算哈希值了。
這樣就可以計(jì)算出字符串的哈希值了。當(dāng)B是一個(gè)比較大的數(shù)或者字符串比較長時(shí)，求B的k次方是比較浪費(fèi)時(shí)間的，所以我們可以優(yōu)化這個(gè)表達(dá)式
這樣就省去了求次方運(yùn)算。但是，還有可能會(huì)出現(xiàn)整型溢出的情況，當(dāng)B是一個(gè)很大的數(shù)字或者字符串很長的時(shí)候，我們可以再次優(yōu)化這個(gè)表達(dá)式
這樣，每退出一個(gè)小括號(hào)，數(shù)字都會(huì)變成比M先得數(shù)字，就不會(huì)出現(xiàn)溢出情況了
復(fù)合類
假如我們自己定義一個(gè)類，日期類
Date：year，month，day
為這個(gè)Date類設(shè)計(jì)哈希函數(shù)，可以像字符串那樣，將類的屬性值看著是一個(gè)字符
這樣，就求出了復(fù)合類的哈希值。
求哈希函數(shù)原則
一致性：當(dāng)關(guān)鍵字相同時(shí)，經(jīng)過哈希函數(shù)求出的哈希值也是相同的。
反過來是不成立的，即當(dāng)哈希值相同時(shí)關(guān)鍵字不一定相同。哈希值相同，取模后得到的索引也相同，即不同的關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)位置相同，這也就是所謂的哈希沖突。
高效性：我們?cè)O(shè)計(jì)哈希函數(shù)就是為了高效存儲(chǔ)數(shù)據(jù)，如果哈希函數(shù)的設(shè)計(jì)就消耗過多性能，那么就得不償失了
均勻性：通過哈希函數(shù)求出的索引必須是分布均勻的。
以上，就是轉(zhuǎn)化為整型求哈希函數(shù)。但是，這并不是求哈希函數(shù)唯一的方法。
