上面 HashSet 和 HashMap 都使用了 散列表來做數(shù)據(jù)的檢索吟温，那么什么是散列表 ，這個(gè)又有什么優(yōu)點(diǎn)呢 ？
散列表也叫作哈希表（hash table）谈山，這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系智亮。只要給出一個(gè)Key忆某，就可以高效查找到它所匹配的Value，時(shí)間復(fù)雜度接近于O(1)阔蛉。
是不是想到了 Map 弃舒？
散列表是如何根據(jù)Key來快速找到它所匹配的 Value 呢 ？
在目前所學(xué)的數(shù)據(jù)結(jié)構(gòu)中状原，數(shù)組的查詢效率是最高的聋呢。散列表本質(zhì)就是一個(gè)數(shù)組。不同的是數(shù)組的下標(biāo)是數(shù)字颠区，但是散列表的下標(biāo)是字符串削锰。這就需要設(shè)計(jì)一個(gè)中轉(zhuǎn)站，通過某種方式毕莱，把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換器贩。這個(gè)中轉(zhuǎn)站就叫作哈希函數(shù)。
在不同的語言中朋截，哈希函數(shù)的實(shí)現(xiàn)是不一樣的蛹稍。我們以Java的HashMap為例，來看看哈希函數(shù)的實(shí)現(xiàn)部服。
在Java及大多數(shù)面向?qū)ο蟮恼Z言中唆姐，每一個(gè)對象都有屬于自己的hashcode，這個(gè)hashcode是區(qū)分不同對象的重要標(biāo)識廓八。無論對象自身的類型是什么奉芦，它們的hashcode都是一個(gè)整型變量胆描。
既然都是整型變量，想要轉(zhuǎn)化成數(shù)組的下標(biāo)也就不難實(shí)現(xiàn)了仗阅。最簡單的轉(zhuǎn)化方式是什么呢昌讲？是按照數(shù)組長度進(jìn)行取模運(yùn)算
<
index = HashCode (Key) % Array.length
其實(shí)JDK中的哈希函數(shù)為了提升效率，使用的是位運(yùn)算减噪。我們就假設(shè)使用的是模運(yùn)算
通過哈希函數(shù)短绸，我們可以把字符串或其他類型的Key，轉(zhuǎn)化成數(shù)組的下標(biāo)index筹裕。如給出一個(gè)長度為8的數(shù)組醋闭，則當(dāng)
key=001121時(shí)
index = HashCode ("001121") % Array.length = 1420036703 % 8 = 7
而當(dāng)key=this時(shí)，
index = HashCode ("this") % Array.length = 3559070 % 8 = 6
散列表的讀寫操作
寫操作就是在散列表中插入新的鍵值對（在JDK中叫作Entry）朝卒。如調(diào)用hashMap.put("002931", "王五")证逻，意思是插入一組Key為002931、Value為王五的鍵值對抗斤。具體該怎么做呢囚企？
通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)5瑞眼。
-
如果數(shù)組下標(biāo)5對應(yīng)的位置沒有元素龙宏，就把這個(gè)Entry填充到數(shù)組下標(biāo)5的位置
篇.png
由于數(shù)組的長度是有限的，當(dāng)插入的Entry越來越多時(shí)伤疙，不同的Key通過哈希函數(shù)獲得的下標(biāo)有可能是相同的银酗。例如002936這個(gè)Key對應(yīng)的數(shù)組下標(biāo)是2；002947這個(gè)Key對應(yīng)的數(shù)組下標(biāo)也是2徒像。
圖片.png
這種情況黍特，就叫作哈希沖突
解決哈希沖突的方法主要有兩種，一種是開放尋址法锯蛀，一種是鏈表法
- 開放尋址法的原理很簡單灭衷，當(dāng)一個(gè)Key通過哈希函數(shù)獲得對應(yīng)的數(shù)組下標(biāo)已被占用時(shí)，我們可以“另謀高就”谬墙，尋找下一個(gè)空檔位置
-
HashMap數(shù)組的每一個(gè)元素不僅是一個(gè)Entry對象今布，還是一個(gè)鏈表的頭節(jié)點(diǎn)。每一個(gè)Entry對象通過next指針指向它的下一個(gè)Entry節(jié)點(diǎn)拭抬。當(dāng)新來的Entry映射到與之沖突的數(shù)組位置時(shí)部默，只需要插入到對應(yīng)的鏈表中即可
圖片1.png
讀操作（get）
讀操作就是通過給定的Key，在散列表中查找對應(yīng)的Value造虎。例如調(diào)用 hashMap.get("002936")傅蹂，意思是查找Key為002936的Entry在散列表中所對應(yīng)的值
- 通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)2。
- 找到數(shù)組下標(biāo)2所對應(yīng)的元素份蝴，如果這個(gè)元素的Key是002936犁功，那么就找到了；如果這個(gè)Key不是002936也沒關(guān)系婚夫，由于數(shù)組的每個(gè)元素都與一個(gè)鏈表對應(yīng)浸卦，我們可以順著鏈表慢慢往下找，看看能否找到與Key相匹配的節(jié)點(diǎn)案糙。
