哈希表

Hash table(也稱為散列表蛾默、哈希表)，當(dāng)我們需要存儲(chǔ)集合或字典瑰排，使用線性表贯要、樹去存儲(chǔ)時(shí)，元素在存儲(chǔ)結(jié)構(gòu)中的位置與元素的關(guān)鍵碼之間不存在直接的對(duì)應(yīng)關(guān)系椭住，所以在要搜索一個(gè)元素時(shí)都需要進(jìn)行一系列的關(guān)鍵碼比較崇渗，搜索的效率取決于搜索過(guò)程進(jìn)行的比較次數(shù)。而散列表（Hash table）是表示集合和字典的另一種有效方法，它提供了一種完全不同的存儲(chǔ)和搜索方式宅广，通過(guò)關(guān)鍵碼映射到表中某個(gè)位置來(lái)存儲(chǔ)元素葫掉，然后根據(jù)關(guān)鍵碼用同樣的方式直接訪問(wèn)。

用自己的話解析

存儲(chǔ)數(shù)據(jù)時(shí)跟狱，用其他結(jié)構(gòu)都需要對(duì)關(guān)鍵碼一一比較俭厚，搜索效率可能比較低。而哈希表是將關(guān)鍵碼和存儲(chǔ)位置建立一個(gè)映射關(guān)系驶臊，如存儲(chǔ)時(shí)套腹，關(guān)鍵字.hashCode()的方法得到一個(gè)數(shù)組的下標(biāo)，然后把該Entry（存儲(chǔ)對(duì)象）存儲(chǔ)在該Bucket（桶）里资铡，那么就能大大提高搜索效率。由于hashCode()的計(jì)算規(guī)則幢码，有可能不同的Entry得到的下標(biāo)是一樣的（哈希沖突）笤休，Bucket的結(jié)構(gòu)就設(shè)計(jì)成單鏈表，存儲(chǔ)時(shí)症副，如果Bucket不為空店雅，則把Entry放進(jìn)單鏈表里。在單鏈表搜索時(shí)對(duì)比關(guān)鍵碼獲得Entry贞铣。

為什么重寫類的equals方法時(shí)闹啦，也需要重寫hashCode方法

正確的狀態(tài)：當(dāng)兩個(gè)不對(duì)象相等，即equals方法返回false時(shí)辕坝，但兩對(duì)象hashCode方法返回的值相等窍奋，那豈不是天下大亂了？
通過(guò)hashCode就無(wú)法在哈希表中獲取到正確的對(duì)象酱畅。所以一定要保證不相等的對(duì)象琳袄，返回的hashCode也不一致。另外纺酸，兩個(gè)對(duì)象的hashCode()的數(shù)值相等窖逗，但兩個(gè)對(duì)象用equals方法不一定相等。

equals和==

==用于比較引用和比較基本數(shù)據(jù)類型時(shí)具有不同的功能：
比較基本數(shù)據(jù)類型餐蔬，如果兩個(gè)值相同碎紊，則結(jié)果為true
而在比較引用時(shí)，如果引用指向內(nèi)存中的同一對(duì)象樊诺，結(jié)果為true;

equals()
作為方法仗考，實(shí)現(xiàn)對(duì)象的比較。由于==運(yùn)算符不允許我們進(jìn)行覆蓋啄骇，也就是說(shuō)它限制了我們的表達(dá)痴鳄。因此我們復(fù)寫equals()方法，達(dá)到比較對(duì)象內(nèi)容是否相同的目的缸夹。而這些通過(guò)==運(yùn)算符是做不到的痪寻。

object類的equals()方法的比較規(guī)則為：如果兩個(gè)對(duì)象的類型一致螺句，并且內(nèi)容一致，則返回true,這些類有：
java.io.file,java.util.Date,java.lang.string,包裝類（Integer,Double等）

String s1=new String("abc");
String s2=new String("abc");
System.out.println(s1==s2); //返回false
System.out.println(s1.equals(s2)); //返回true

一些哈希函數(shù)的實(shí)現(xiàn)方法

直接定址法：這個(gè)方法我們?cè)谏鲜隼又杏杏玫竭^(guò)橡类，取關(guān)鍵字的或關(guān)鍵的某一個(gè)線性函數(shù)值為哈希地址蛇尚。即：Hash(key)=key或者Hash(key)=a*key+b。這種構(gòu)造方法下由于地址集合和關(guān)鍵字集合大小一樣顾画，所以并不會(huì)有沖突的發(fā)生取劫。但是這種方法并不常用。
除留余數(shù)法：這個(gè)方法我們?cè)谏鲜隼又幸灿杏玫竭^(guò)研侣，取關(guān)鍵字被某一個(gè)不大于哈希表長(zhǎng)m的數(shù)p除后所余得的數(shù)為哈希地址谱邪。即Hash(key)=key MOD p,p<=m(m為哈希表長(zhǎng))。這種方法比較簡(jiǎn)單也很常用庶诡。
數(shù)字分析法：就是取關(guān)鍵字的若干位數(shù)組成哈希地址惦银。當(dāng)然我們?cè)谌〉臅r(shí)候要對(duì)位數(shù)進(jìn)行分析，盡量減少?zèng)_突末誓。
平方取中法：取關(guān)鍵字平方后的中間若干位組成哈希地址扯俱。相比于數(shù)字分析法優(yōu)點(diǎn)在于一個(gè)數(shù)平方之后的中間的幾位數(shù)和原來(lái)的數(shù)都有關(guān)，因此哈希地址是隨機(jī)的喇澡。

可以看到：在哈希函數(shù)構(gòu)造的時(shí)候都是使用的數(shù)字迅栅，但如果我們的關(guān)鍵字不為數(shù)字的時(shí)候，我們要先將關(guān)鍵字轉(zhuǎn)化為數(shù)字晴玖，再用哈希函數(shù)得到哈希地址读存。如上述例子中我們利用學(xué)生姓名作為關(guān)鍵字，我們首先要得到學(xué)生姓名小寫拼音的ＡSCII碼窜醉，再用ASCII碼作為哈希函數(shù)的自變量宪萄，從而得到哈希地址。

哈希表處理沖突的方法

之前講過(guò)哈希表的沖突是不可避免的只能減少的榨惰，那么如何處理沖突也成了一個(gè)不可避免的問(wèn)題拜英。

什么是處理沖突呢？：由關(guān)鍵字得到的哈希地址上已經(jīng)有記錄存在了琅催，那么“處理沖突”就是要為該關(guān)鍵字的記錄找到一個(gè)“沒(méi)有記錄存在”的哈希地址居凶。在處理沖突的過(guò)程中可能得到一個(gè)地址序列Hi(i=1,2,3,4,5,……)。我們?cè)谔幚砉_突的時(shí)候可能得到的另一個(gè)哈希地址H1也是有記錄的藤抡，我們要求下一個(gè)地址H2侠碧，如果H2依然沖突，則找H3,依次類推缠黍，直至Hi上沒(méi)有記錄為止弄兜。

（1）開放地址法：Hi=(Hash(key)+di)MOD m

其中：Hash(key)為哈希函數(shù)，di為增量序列，m為哈希表長(zhǎng)替饿。
1语泽、di=1,2,3,4,5……,m-1時(shí)稱線性探測(cè)再散列；
2视卢、di=1₂,-1₂,2₂,-2₂……….,+k₂,-k₂(k<=m/2)稱之為二次探測(cè)再散列踱卵。
3、di=偽隨機(jī)數(shù)序列据过，稱之為隨機(jī)探測(cè)在散列惋砂。

（2）再哈希法：Hi=RHashi(key) i=0,1,2,3,4….,k. RHashi均是不同的哈希函數(shù)，就是說(shuō)在同義詞產(chǎn)生地址沖突的時(shí)候用另一個(gè)哈希函數(shù)去求得另一個(gè)哈希地址绳锅，一直到不再有沖突

（3）鏈地址法：鏈地址法我們?cè)谏鲜隼佑杏玫竭^(guò)西饵。

（4）建立公共溢出區(qū)：設(shè)哈希函數(shù)產(chǎn)生的哈希地址集為[0，m-1]鳞芙，則分配兩個(gè)表：

一個(gè)基本表ElemType base_tbl[m]罗标；每個(gè)單元只能存放一個(gè)元素；

一個(gè)溢出表ElemType over_tbl[k]积蜻；只要關(guān)鍵碼對(duì)應(yīng)的哈希地址在基本表上產(chǎn)生沖突，則所有這樣的元素一律存入該表中彻消。查找時(shí)竿拆，對(duì)給定值kx 通過(guò)哈希函數(shù)計(jì)算出哈希地址i，先與基本表的base_tbl[i]單元比較宾尚，若相等丙笋，查找成功；否則煌贴，再到溢出表中進(jìn)行查找御板。

HashMap的resize

當(dāng)hashmap中的元素越來(lái)越多的時(shí)候，碰撞的幾率也就越來(lái)越高（因?yàn)閿?shù)組的長(zhǎng)度是固定的）牛郑，所以為了提高查詢的效率怠肋，就要對(duì)hashmap的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中淹朋，所以這是一個(gè)通用的操作笙各，很多人對(duì)它的性能表示過(guò)懷疑，不過(guò)想想我們的“均攤”原理础芍，就釋然了杈抢，而在hashmap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置仑性，并放進(jìn)去惶楼，這就是resize。

那么hashmap什么時(shí)候進(jìn)行擴(kuò)容呢？
當(dāng)hashmap中的元素個(gè)數(shù)超過(guò)數(shù)組大小loadFactor時(shí)歼捐，就會(huì)進(jìn)行數(shù)組擴(kuò)容何陆，loadFactor的默認(rèn)值為0.75，也就是說(shuō)窥岩，默認(rèn)情況下甲献，數(shù)組大小為16，那么當(dāng)hashmap中元素個(gè)數(shù)超過(guò)160.75=12的時(shí)候颂翼，就把數(shù)組的大小擴(kuò)展為216=32晃洒，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置朦乏，而這是一個(gè)非常消耗性能的操作球及，所以如果我們已經(jīng)預(yù)知hashmap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高h(yuǎn)ashmap的性能呻疹。比如說(shuō)吃引，我們有1000個(gè)元素new HashMap(1000), 但是理論上來(lái)講new HashMap(1024)更合適，不過(guò)上面annegu已經(jīng)說(shuō)過(guò)刽锤，即使是1000镊尺，hashmap也自動(dòng)會(huì)將其設(shè)置為1024。 但是new HashMap(1024)還不是更合適的并思，因?yàn)?.751000 < 1000, 也就是說(shuō)為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適庐氮，既考慮了&的問(wèn)題，也避免了resize的問(wèn)題宋彼。