轉(zhuǎn)載：http://blog.csdn.net/tanggao1314/article/details/51457585
構(gòu)造hash函數(shù)的方法
- 直接定址法：
直接定址法是以數(shù)據(jù)元素關(guān)鍵字k本身或它的線性函數(shù)作為它的哈希地址快耿，即：H（k）=k 或 H（k）=a×k+b 囊陡； (其中a,b為常數(shù))。
- 數(shù)字分析法：
假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, …, us)掀亥，分析關(guān)鍵字集中的全體撞反，并從中提取分布均勻的若干位或它們的組合作為地址。
數(shù)字分析法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法搪花。即當(dāng)關(guān)鍵字的位數(shù)很多時(shí)遏片，可以通過(guò)對(duì)關(guān)鍵字的各位進(jìn)行分析，丟掉分布不均勻的位撮竿，作為哈希值吮便。它只適合于所有關(guān)鍵字值已知的情況。
- 折疊法：
將關(guān)鍵字分割成若干部分幢踏，然后取它們的疊加和為哈希地址髓需。兩種疊加處理的方法：移位疊加:將分 割后的幾部分低位對(duì)齊相加；邊界疊加:從一端沿分割界來(lái)回折疊房蝉，然后對(duì)齊相加僚匆。
- 平方取中法：
這是一種常用的哈希函數(shù)構(gòu)造方法。這個(gè)方法是先取關(guān)鍵字的平方搭幻，然后根據(jù)可使用空間的大小白热，選取平方數(shù)是中間幾位為哈希地址。
哈希函數(shù) H(key)=“key2的中間幾位”因?yàn)檫@種方法的原理是通過(guò)取平方擴(kuò)大差別粗卜，平方值的中間幾位和這個(gè)數(shù)的每一位都相關(guān)屋确，則對(duì)不同的關(guān)鍵字得到的哈希函數(shù)值不易產(chǎn)生沖突，由此產(chǎn)生的哈希地址也較為均勻。
- 減去法：
減去法是數(shù)據(jù)的鍵值減去一個(gè)特定的數(shù)值以求得數(shù)據(jù)存儲(chǔ)的位置攻臀。
- 基數(shù)轉(zhuǎn)換法：
將十進(jìn)制數(shù)X看作其他進(jìn)制焕数，比如十三進(jìn)制，再按照十三進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)刨啸，提取其中若干位作為X的哈希值堡赔。一般取大于原來(lái)基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)應(yīng)該是互素的设联。
- 除留余數(shù)法：
除留余數(shù)法的模p取不大于表長(zhǎng)且最接近表長(zhǎng)m素?cái)?shù)時(shí)效果最好善已，且p最好取1.1n～1.7n之間的一個(gè)素?cái)?shù)（n為存在的數(shù)據(jù)元素個(gè)數(shù)）。
- 隨機(jī)數(shù)法：
設(shè)定哈希函數(shù)為:H(key) = Random(key)其中离例，Random 為偽隨機(jī)函數(shù)
此法適于：對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)换团。
9．隨機(jī)乘數(shù)法：
亦稱為“乘余取整法”。隨機(jī)乘數(shù)法使用一個(gè)隨機(jī)實(shí)數(shù)f,0≤f<1,乘積fk的分?jǐn)?shù)部分在0～1之間宫蛆，用這個(gè)分?jǐn)?shù)部分的值與n（哈希表的長(zhǎng)度）相乘艘包，乘積的整數(shù)部分就是對(duì)應(yīng)的哈希值，顯然這個(gè)哈希值落在0～n-1之間耀盗。其表達(dá)公式為：Hash(k)=「n(fk%1)」其中“fk%1”表示fk 的小數(shù)部分想虎，即fk%1=fk-「fk」
10．字符串?dāng)?shù)值哈希法：
在很都情況下關(guān)鍵字是字符串，因此這樣對(duì)字符串設(shè)計(jì)Hash函數(shù)是一個(gè)需要討論的問(wèn)題叛拷。下列函數(shù)是取字符串前10個(gè)字符來(lái)設(shè)計(jì)的哈希函數(shù)舌厨。
- 旋轉(zhuǎn)法：
旋轉(zhuǎn)法是將數(shù)據(jù)的鍵所代表的的數(shù)字中的部分位進(jìn)行旋轉(zhuǎn)。旋轉(zhuǎn)法通常并不直接使用在哈希函數(shù)上忿薇，而是搭配其他哈希函數(shù)使用裙椭。
例如，某學(xué)校同一個(gè)系的新生（小于100人）的學(xué)號(hào)前5位數(shù)是相同的煌恢，只有最后2位數(shù)不同骇陈，我們將最后一位數(shù)震庭，旋轉(zhuǎn)放置到第一位瑰抵，其余的往右移。
解決“ 沖突 ”的方法
常用的解決沖突方法有以下四種：
1.開放定址法
這種方法也稱再散列法器联，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)二汛，以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p1拨拓，如果p1仍然沖突肴颊，再以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p2渣磷，…婿着，直到找出一個(gè)不沖突的哈希地址pi ，將相應(yīng)元素存入其中。
主要有以下三種：
（1）線性探測(cè)再散列
沖突發(fā)生時(shí)竟宋，順序查看表中下一單元提完，直到找出一個(gè)空單元或查遍全表。
（2）二次探測(cè)再散列
沖突發(fā)生時(shí)丘侠，在表的左右進(jìn)行跳躍式探測(cè)徒欣，比較靈活。
（3）偽隨機(jī)探測(cè)再散列
具體實(shí)現(xiàn)時(shí)蜗字，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器打肝，（如i=(i+p) % m），并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)挪捕。
2.再哈希法
這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
Hi=RH1(key) i=1粗梭，2习蓬，…章咧，k
當(dāng)哈希地址Hi=RH1(key)發(fā)生沖突時(shí)，再計(jì)算Hi=RH2（key）……亲轨，直到?jīng)_突不再產(chǎn)生妄讯。這種方法不易產(chǎn)生聚集孩锡，但增加了計(jì)算時(shí)間。
3.拉鏈法
這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表亥贸，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中躬窜，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行炕置。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況荣挨。
4.建立公共溢出區(qū)
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素朴摊，一律填入溢出表
常見hash算法
了解了hash基本定義默垄，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以說(shuō)是目前應(yīng)用最廣泛的Hash算法甚纲，而它們都是以 MD4 為基礎(chǔ)設(shè)計(jì)的口锭。那么他們都是什么意思呢?
這里簡(jiǎn)單說(shuō)一下：
（1）MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的，MD 是 Message Digest 的縮寫介杆。它適用在32位字長(zhǎng)的處理器上用高速軟件實(shí)現(xiàn) —— 它是基于 32 位操作數(shù)的位操作來(lái)實(shí)現(xiàn)的鹃操。
（2）MD5
MD5(RFC 1321)是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組春哨，其輸出是4個(gè)32位字的級(jí)聯(lián)荆隘，與 MD4 相同。MD5比MD4來(lái)得復(fù)雜赴背，并且速度較之要慢一點(diǎn)椰拒，但更安全晶渠，在抗分析和抗差分方面表現(xiàn)更好
（3）SHA-1 及其他
SHA1是由NIST NSA設(shè)計(jì)為同DSA一起使用的，它對(duì)長(zhǎng)度小于264的輸入燃观，產(chǎn)生長(zhǎng)度為160bit的散列值乱陡，因此抗窮舉(brute-force)性更好。SHA-1 設(shè)計(jì)時(shí)基于和MD4相同原理,并且模仿了該算法仪壮。
那么這些Hash算法到底有什么用呢?
Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個(gè)方面：
- 文件校驗(yàn)
我們比較熟悉的校驗(yàn)算法有奇偶校驗(yàn)和CRC校驗(yàn)憨颠，這2種校驗(yàn)并沒有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測(cè)并糾正數(shù)據(jù)傳輸中的信道誤碼积锅，但卻不能防止對(duì)數(shù)據(jù)的惡意破壞爽彤。
MD5 Hash算法的"數(shù)字指紋"特性，使它成為目前應(yīng)用最廣泛的一種文件完整性校驗(yàn)和(Checksum)算法缚陷，不少Unix系統(tǒng)有提供計(jì)算md5 checksum的命令适篙。
- 數(shù)字簽名
Hash 算法也是現(xiàn)代密碼體系中的一個(gè)重要組成部分。由于非對(duì)稱算法的運(yùn)算速度較慢箫爷，所以在數(shù)字簽名協(xié)議中嚷节，單向散列函數(shù)扮演了一個(gè)重要的角色。 對(duì) Hash 值虎锚，又稱"數(shù)字摘要"進(jìn)行數(shù)字簽名硫痰，在統(tǒng)計(jì)上可以認(rèn)為與對(duì)文件本身進(jìn)行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點(diǎn)窜护。
- 鑒權(quán)協(xié)議
如下的鑒權(quán)協(xié)議又被稱作挑戰(zhàn)--認(rèn)證模式：在傳輸信道是可被偵聽效斑，但不可被篡改的情況下，這是一種簡(jiǎn)單而安全的方法柱徙。
