一、散列函數(shù)的設(shè)計(jì)準(zhǔn)則：
??1、散列函數(shù)的設(shè)計(jì)不能太復(fù)雜。過(guò)于復(fù)雜的散列函數(shù)，勢(shì)必會(huì)消耗很多計(jì)算時(shí)間，也就間接的影響到散列表的性能。
??2、散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布，這樣才能避免或者最小化散列沖突，而且即便出現(xiàn)沖突，散列到每個(gè)槽里的數(shù)據(jù)也會(huì)比較平均，不會(huì)出現(xiàn)某個(gè)槽內(nèi)數(shù)據(jù)特別多的情況。
二、裝載因子過(guò)大的解決辦法：
??針對(duì)散列表，當(dāng)裝載因子過(guò)大時(shí)，可以進(jìn)行動(dòng)態(tài)擴(kuò)容，重新申請(qǐng)一個(gè)更大的散列表，將數(shù)據(jù)搬移到這個(gè)新散列表中。假設(shè)每次擴(kuò)容都申請(qǐng)一個(gè)原來(lái)散列表大小兩倍的空間。如果原來(lái)散列表的裝載因子是0.8，那經(jīng)過(guò)擴(kuò)容之后，新散列表的裝載因子就下降為原來(lái)的一半，變成了0.4。但針對(duì)散列表的擴(kuò)容，數(shù)據(jù)搬移操作要復(fù)雜很多。因?yàn)樯⒘斜淼拇笮∽兞?，?shù)據(jù)的存儲(chǔ)位置也變了，所以需要通過(guò)散列函數(shù)重新計(jì)算每個(gè)數(shù)據(jù)的存儲(chǔ)位置。
三、如何避免低效的擴(kuò)容：
??為了解決一次性擴(kuò)容耗時(shí)過(guò)多的情況，可以將擴(kuò)容操作穿插在插入操作的過(guò)程中，分批完成。當(dāng)裝載因子觸達(dá)閾值之后，只申請(qǐng)新空間，但并不將老的數(shù)據(jù)搬移到新散列表中。當(dāng)有新數(shù)據(jù)要插入時(shí)，將新數(shù)據(jù)插入新散列表中，并且從老的散列表中拿出一個(gè)數(shù)據(jù)放入到新散列表。每次插入一個(gè)數(shù)據(jù)到散列表，都重復(fù)上面的過(guò)程。經(jīng)過(guò)多次插入操作之后，老的散列表中的數(shù)據(jù)就一點(diǎn)一點(diǎn)全部搬移到新散列表中了。這樣沒有了集中的一次性數(shù)據(jù)搬移，插入操作就都變得很快了。
四、散列表HashMap的舉例分析：
1.初始大?。?/h3>
??HashMap默認(rèn)的初始大小是16，當(dāng)然這個(gè)默認(rèn)值是可以設(shè)置的，如果事先知道大概的數(shù)據(jù)量有多大，可以修改默認(rèn)初始大小。
2.裝載因子和動(dòng)態(tài)擴(kuò)容：
??最大裝載因子默認(rèn)是0.75，當(dāng)HashMap中元素個(gè)數(shù)超過(guò)0.75*capacity（capacity表示散列表的容量）的時(shí)候，就會(huì)啟動(dòng)擴(kuò)容，每次擴(kuò)容都會(huì)擴(kuò)容為原來(lái)的兩倍大小。
3.散列沖突解決方法：
??HashMap底層采用鏈表法來(lái)解決沖突。但即使負(fù)載因子和散列函數(shù)設(shè)計(jì)得再合理，也免不了會(huì)出現(xiàn)拉鏈過(guò)長(zhǎng)的情況，一旦出現(xiàn)拉鏈過(guò)長(zhǎng)，則會(huì)嚴(yán)重影響HashMap的性能。于是，在JDK1.8版本中，為了對(duì)HashMap做進(jìn)一步優(yōu)化，引入了紅黑樹。而當(dāng)鏈表長(zhǎng)度太長(zhǎng)（默認(rèn)超過(guò)8）時(shí)，鏈表就轉(zhuǎn)換為紅黑樹?？梢岳眉t黑樹快速增刪改查的特點(diǎn)，提高HashMap的性能。當(dāng)紅黑樹結(jié)點(diǎn)個(gè)數(shù)少于8個(gè)的時(shí)候，又會(huì)將紅黑樹轉(zhuǎn)化為鏈表。因?yàn)樵跀?shù)據(jù)量較小的情況下，紅黑樹要維護(hù)平衡，比起鏈表來(lái)，性能上的優(yōu)勢(shì)并不明顯。
4.散列函數(shù)：
static final int hash(Object key) {
int h = key.hashCode()；
return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}
其中， hashCode()返回的是Java對(duì)象的hash code。
五、工業(yè)級(jí)的散列表應(yīng)該具有哪些特性？該如何設(shè)計(jì)？
1、應(yīng)該具有的特性：
??(1)：支持快速的查詢、插入、刪除操作
??(2)：內(nèi)存占用合理，不能浪費(fèi)過(guò)多的內(nèi)存空間；
??(3)：性能穩(wěn)定，極端情況下，散列表的性能也不會(huì)退化到無(wú)法接受的情況。
2、設(shè)計(jì)準(zhǔn)則：
??()：設(shè)計(jì)一個(gè)合適的散列函數(shù)；
??()：定義裝載因子閾值，并且設(shè)計(jì)動(dòng)態(tài)擴(kuò)容策略；
??()：選擇合適的散列沖突解決方法。
