基本概念
基于線性表鼓蜒、樹(shù)表結(jié)構(gòu)的查找方法枷恕，這類查找方法都是以關(guān)鍵字的比較為基礎(chǔ)的筏养。在查找過(guò)程中只考慮各元素關(guān)鍵字之間的相對(duì)大小，記錄在存儲(chǔ)結(jié)構(gòu)中的位置和其關(guān)鍵字無(wú)直接關(guān)系兄朋，其查找時(shí)間與表的長(zhǎng)度有關(guān)掐禁，特別是當(dāng)結(jié)點(diǎn)個(gè)數(shù)很多時(shí)，查找時(shí)要大量地與無(wú)效結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較颅和，致使查找速度很慢傅事。如果能在元素的存儲(chǔ)位置和其關(guān)鍵字之間建立某種直接關(guān)系，那么在進(jìn)行查找時(shí)峡扩，就無(wú)需做比較或很少次的比較蹭越，按照這種關(guān)系直接由關(guān)鍵字找到相應(yīng)記錄。這就是散列查找(Hash Search)的思想,它通過(guò)對(duì)元素的關(guān)鍵字值進(jìn)行某種運(yùn)算教届，直接求出元素的地址响鹃，即使用關(guān)鍵字到地址的直接轉(zhuǎn)換方法，而不需要反復(fù)比較案训。
在記錄的存儲(chǔ)位置p和它的關(guān)鍵字key之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f买置，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key)。建立了關(guān)鍵字與存儲(chǔ)位置的映射關(guān)系强霎，公式如下：
?????????????p = f（key）
這里把這種對(duì)應(yīng)關(guān)系f稱為散列函數(shù)(哈希（Hash）函數(shù))忿项，p為散列地址。詳情見(jiàn)：Java中hashCode的作用城舞。
一塊連續(xù)的存儲(chǔ)空間中倦卖，用以存儲(chǔ)按散列函數(shù)計(jì)算得到相應(yīng)散列地址的數(shù)據(jù)記錄。這塊連續(xù)存儲(chǔ)空間稱為散列表或哈希表椿争。通常散列表的存儲(chǔ)空間是一個(gè)一維數(shù)組怕膛，散列地址是數(shù)組的下標(biāo)。
散列查找法主要研究以下兩方面的問(wèn)題：
- 如果構(gòu)造散列函數(shù)秦踪；
- 如何處理沖突褐捻。
散列函數(shù)的構(gòu)造方法
直接定址法
可以取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，即：
f(key) = a × key + b
例如：有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表椅邓，其中柠逞，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身景馁。
f(key) = key板壮。
這樣的散列函數(shù)優(yōu)點(diǎn)就是簡(jiǎn)單、均勻合住，也不會(huì)產(chǎn)生沖突绰精，但問(wèn)題是這需要事先知道關(guān)鍵字的分布情況撒璧，適合査找表較小且連續(xù)的情況。由于這樣的限制笨使，在現(xiàn)實(shí)應(yīng)用中不常用卿樱。
數(shù)字分析法
數(shù)字分析法通過(guò)適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布比較均勻硫椰，就可以考慮用這個(gè)方法繁调。
比如11位的手機(jī)號(hào)"188****8888"，極有可能前7位都是相同的靶草，選擇后四位成為散列地址就是不錯(cuò)的選擇蹄胰。
平方取中法
這個(gè)方法計(jì)算很簡(jiǎn)單：取關(guān)鍵字平方后的中間幾位為哈希地址。
假設(shè)關(guān)鍵字是1234奕翔，那么它的平方就是1522756裕寨，再抽取中間的3位就是227，用做散列地址糠悯。
平方取中法比較適合不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況妻往。
折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）互艾，然后取這幾部分的疊加和作為散列地址。
比如關(guān)鍵字是1234567890讯泣，散列表表長(zhǎng)為三位纫普，將它分為四組，123|456|789|0好渠，然后將它們疊加求和123 + 456 + 789 + 0 = 1368昨稼，再求后3位得到散列地址368。
折疊法事先不需要知道關(guān)鍵字的分布拳锚，適合關(guān)鍵字位數(shù)較多的情況假栓。
除留余數(shù)法
取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址。
H(key)=key MOD p (p<=m)
這方法不僅可以對(duì)關(guān)鍵字直接取模霍掺，也可以折疊匾荆、平方取中后再取模。
很顯然杆烁，本方法的關(guān)鍵在于選擇合適的p牙丽，p如果選不好，就可能會(huì)容易產(chǎn)生沖突兔魂。
根據(jù)前輩們的經(jīng)驗(yàn)烤芦，若散列表的表長(zhǎng)為m，通常p為小于或等于表長(zhǎng)（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)析校。
隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)函數(shù)构罗，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址铜涉，即
H(key)=random(key），其中random為隨機(jī)函數(shù)绰播。通常用于關(guān)鍵字長(zhǎng)度不等時(shí)采用此法骄噪。
散列函數(shù)的構(gòu)造方法小結(jié)
在實(shí)際應(yīng)用中，應(yīng)該視不同的情況采用不同的散列函數(shù)蠢箩，這里只能給出一些考慮的因素來(lái)提供參考：
- 計(jì)算散列地址所需的時(shí)間
- 關(guān)鍵字的長(zhǎng)度链蕊；
- 散列表的長(zhǎng)度；
- 關(guān)鍵字的分布情況谬泌；
- 記錄查找的頻率滔韵。
綜合以上等因素，才能決策選擇哪種散列函數(shù)更合適掌实。
處理散列沖突的方法
無(wú)論哈希函數(shù)設(shè)計(jì)有多么精細(xì)陪蜻，都會(huì)產(chǎn)生沖突現(xiàn)象，也就是2個(gè)關(guān)鍵字處理函數(shù)的結(jié)果映射在了同一位置上贱鼻，因此宴卖，有一些方法可以避免沖突。
開(kāi)放定址法(重要)
開(kāi)放地址法有一個(gè)公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）其中邻悬，m為哈希表的表長(zhǎng)症昏。di 是產(chǎn)生沖突的時(shí)候的增量序列。
- 如果di值可能為1,2,3,...m-1父丰，稱線性探測(cè)法肝谭。
- 如果di取值可能為1,-1,4,-4,9,-9,16,-16,...kk,-kk(k<=m/2）
稱二次探測(cè)法。 - 如果di取值可能為偽隨機(jī)數(shù)列蛾扇。稱偽隨機(jī)探測(cè)法攘烛。
開(kāi)發(fā)定址法處理流程請(qǐng)見(jiàn)：散列沖突處理：開(kāi)放定址法
總結(jié)：
開(kāi)放定址法的思路就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址镀首。
鏈地址法(拉鏈法)(重要)
鏈地址法：簡(jiǎn)單來(lái)說(shuō)坟漱，就是數(shù)組加鏈表的結(jié)合。在每個(gè)數(shù)組元素上都一個(gè)鏈表結(jié)構(gòu)更哄，當(dāng)數(shù)據(jù)被Hash后靖秩，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對(duì)應(yīng)下標(biāo)元素的鏈表上竖瘾。
具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱作同義詞沟突。
將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，我們稱這種表為同義詞子表捕传，在散列表中只存儲(chǔ)所有同義詞子表的頭指針惠拭。
JDK1.8之前HashMap底層結(jié)構(gòu)就是哈希表，并且處理散列沖突的方法使用的是拉鏈法。
拉鏈法詳情請(qǐng)見(jiàn)：散列沖突處理：鏈地址法
公共溢出區(qū)法
為所有沖突的關(guān)鍵字建立一個(gè)公共的溢出區(qū)來(lái)存放职辅。
在查找時(shí)棒呛，對(duì)給定值通過(guò)散列函數(shù)計(jì)算出散列地址后，先與基本表的相應(yīng)位置進(jìn)行比對(duì)域携，如果相等簇秒，則查找成功；如果不相等秀鞭，則到溢出表中進(jìn)行順序查找趋观。如果相對(duì)于基本表而言，有沖突的數(shù)據(jù)很少的情況下锋边，公共溢出區(qū)的結(jié)構(gòu)對(duì)查找性能來(lái)說(shuō)還是非常高的皱坛。
