冰凍非一日之寒

上一篇文章中，我們舉了身份證號為關(guān)鍵字的例子闷愤。這里整葡，我們假設(shè)真的有一個無限大的空間，那么讥脐，可以直接將身份證號作為索引嗎遭居？

顯然不合適。因為旬渠，并不是所有的身份證號都是18位的俱萍，對于那些位數(shù)在17位以下的，就太浪費這個大空間了告丢。

設(shè)計哈希函數(shù)的原則是枪蘑，將我們所關(guān)心的鍵通過哈希函數(shù)求出索引，“鍵”通過哈希函數(shù)得到的“索引”分布越均勻越好(實際上芋齿，實現(xiàn)起來非常困難)

那么腥寇，對于像身份證號這樣的大整數(shù)為關(guān)鍵字時，該怎么計算對應(yīng)的索引呢觅捆？

或者像復(fù)合類赦役、字符串、浮點數(shù)這樣類型的關(guān)鍵字栅炒，該如何計算它們對應(yīng)的索引呢掂摔？

對于哈希函數(shù)來說术羔，我們只能將整型數(shù)據(jù)作為關(guān)鍵字來求解索引。所以乙漓，不管什么類型的關(guān)鍵字级历，我們應(yīng)該先將其轉(zhuǎn)化為整型類型的數(shù)據(jù)。

按照這個思路叭披，以下介紹幾種最簡單寥殖、最基礎(chǔ)、最一般涩蜘、最通用的哈希函數(shù)

整型

小范圍正整數(shù)直接使用

例如嚼贡，上一篇講的ASCII值作為關(guān)鍵字

再例如，一個班有30個學生同诫，1—30表示每位學生對應(yīng)的學號粤策，并作為關(guān)鍵字

像這樣的小范圍正整數(shù)，可以直接將關(guān)鍵字作為索引误窖，存儲到數(shù)組中去

小范圍負整數(shù)進行偏移

例如叮盘，-100～100的數(shù)作為關(guān)鍵字，這時可以每個數(shù)都加上100霹俺，變?yōu)?～200的正整數(shù)

這樣柔吼，就可以將關(guān)鍵字直接作為索引存儲到數(shù)組中去

大整數(shù)取模

例如，身份證號作為關(guān)鍵字吭服，412637199707096354

取后四位(6354)嚷堡。也就是，mod 10000

假如艇棕，取后六位(096354)蝌戒。即，mod 100 0000 這樣沼琉，會分布不均勻

對于身份證號來說北苟，后六位的前兩位(09)代表著日期數(shù)，也就是1～31的數(shù)字打瘪。那么友鼻，這個六位數(shù)不會達到32 0000這么大，中國這么多人口闺骚，顯然這個數(shù)字是不夠的彩扔，這也就造成了索引分布不均勻

這也就體現(xiàn)了哈希函數(shù)的復(fù)雜性，也說明了具體問題要具體分析僻爽。

上面的取模方式還有一個問題虫碉，沒有有效利用所有信息。我們這樣取模胸梆，只是利用了關(guān)鍵字的一部分敦捧，也就是不管這個人是哪個地區(qū)哪個年份出生的须板，都有可能存儲到一個地址中去，這樣會增加哈希沖突的概率兢卵。那么习瑰，該如何解決這個問題呢？

一個簡單的解決辦法：模一個素數(shù)

為什么要模一個素數(shù)呢秽荤？簡單舉個例子

圖片發(fā)自簡書App

顯然甜奄，模一個素數(shù)，結(jié)果會分布的更均勻王滤，哈希沖突的概率也會變小贺嫂。我們該如何選擇這個素數(shù)呢滓鸠？相關(guān)的領(lǐng)域?qū)＜乙呀?jīng)為我們研究出了答案雁乡。

圖片發(fā)自簡書App

假如，需要存儲的數(shù)在2^5～2^6之間糜俗，模上53就可以了踱稍。

注：這個表并不是唯一的，一個區(qū)間內(nèi)可以有多個素數(shù)

浮點型

將浮點型解析成大整型悠抹，之后再相應(yīng)取模(如上)

字符串

先看一個例子

圖片發(fā)自簡書App

把一個整數(shù)用科學計數(shù)法來表示珠月，同樣，字符串也可以類似表示楔敌。將這個字符串看成26進制啤挎，是因為有26個小寫字母，如果字符串中有大寫字母或者標點符號卵凑，那么看成26進制顯然是不夠的庆聘，可以看成是100進制或者256進制等。顯然勺卢，這個進制是用戶可以自己選擇的伙判，我們用 B 來表示這個進制

圖片發(fā)自簡書App

每一個小寫字母對應(yīng)一個數(shù)字，這樣我們把字符串也轉(zhuǎn)化成了大整型黑忱，之后就可以利用上面取模的方式計算哈希值了宴抚。

字符串哈希函數(shù)

這樣就可以計算出字符串的哈希值了。當B是一個比較大的數(shù)或者字符串比較長時甫煞，求B的k次方是比較浪費時間的菇曲，所以我們可以優(yōu)化這個表達式

哈希函數(shù)*優(yōu)化

這樣就省去了求次方運算。但是抚吠，還有可能會出現(xiàn)整型溢出的情況常潮，當B是一個很大的數(shù)字或者字符串很長的時候，我們可以再次優(yōu)化這個表達式

哈希函數(shù)*再次優(yōu)化

這樣埃跷，每退出一個小括號蕊玷，數(shù)字都會變成比M先得數(shù)字邮利，就不會出現(xiàn)溢出情況了

復(fù)合類

假如我們自己定義一個類，日期類

Date：year垃帅，month延届，day

為這個Date類設(shè)計哈希函數(shù)，可以像字符串那樣贸诚，將類的屬性值看著是一個字符

復(fù)合類哈希函數(shù)

這樣方庭，就求出了復(fù)合類的哈希值。

求哈希函數(shù)原則

原則

一致性：當關(guān)鍵字相同時酱固，經(jīng)過哈希函數(shù)求出的哈希值也是相同的械念。

反過來是不成立的，即當哈希值相同時關(guān)鍵字不一定相同运悲。哈希值相同龄减，取模后得到的索引也相同，即不同的關(guān)鍵字對應(yīng)的存儲位置相同班眯，這也就是所謂的哈希沖突希停。

高效性：我們設(shè)計哈希函數(shù)就是為了高效存儲數(shù)據(jù)，如果哈希函數(shù)的設(shè)計就消耗過多性能署隘，那么就得不償失了

均勻性：通過哈希函數(shù)求出的索引必須是分布均勻的宠能。

以上，就是轉(zhuǎn)化為整型求哈希函數(shù)磁餐。但是违崇，這并不是求哈希函數(shù)唯一的方法。