什么是散列表
散列表又被稱(chēng)為哈希表,包含一個(gè)鍵key、一個(gè)值value它們之間的對(duì)應(yīng)關(guān)系是一對(duì)一,散列表就提供了鍵key和值value的對(duì)應(yīng)關(guān)系,基本結(jié)構(gòu)如下。

鍵值不會(huì)重復(fù)所以通過(guò)鍵就可以找到與之對(duì)應(yīng)的值,一般散列表查詢(xún)的時(shí)間復(fù)雜度為O(1),那么為什么散列表會(huì)這么快呢?
哈希函數(shù)
在分析原因之前我們需要知道散列表其存儲(chǔ)底層是數(shù)組,正是利用了數(shù)組下標(biāo)獲取元素效率高的特點(diǎn),但我們需要注意的是數(shù)組下標(biāo)是整型,而散列表的鍵值可不一定是整型,為什么散列表還能通過(guò)鍵高效獲取值呢?這就需要聊到哈希函數(shù),所謂的哈希函數(shù)就是將散列表的鍵轉(zhuǎn)換為存儲(chǔ)數(shù)組的下標(biāo),再通過(guò)下標(biāo)獲取散列表的值,獲取過(guò)程如下。

哈希函數(shù)如何實(shí)現(xiàn)
那么哈希函數(shù)如何實(shí)現(xiàn)呢?每個(gè)語(yǔ)言會(huì)有自己的計(jì)算邏輯,這里以JAVA為例。如果想要自己設(shè)計(jì)一個(gè)哈希函數(shù)第一步是需要取到每個(gè)鍵唯一且為整數(shù)的標(biāo)識(shí),在JAVA中有這種功能的函數(shù)被稱(chēng)為hashCode方法,是每個(gè)對(duì)象唯一的標(biāo)識(shí),所以鍵對(duì)應(yīng)的哈希函數(shù)就可以采用如下邏輯(JAVA中必然不可能如此簡(jiǎn)單還會(huì)通過(guò)一系列的位運(yùn)算提升效率,這里只是簡(jiǎn)單討論)。
// key.hashCode()調(diào)用鍵的hashCode方法得到唯一的int值
// arr.length表示散列表底層數(shù)組的長(zhǎng)度
int index = key.hashCode()%arr.length;
哈希碰撞
無(wú)論多好的哈希函數(shù)都避免不了的一個(gè)問(wèn)題就是,兩個(gè)不相同的哈希值可能計(jì)算出來(lái)的數(shù)組下標(biāo)為同一個(gè)。
假設(shè)數(shù)組長(zhǎng)度為6,需要放入兩個(gè)鍵key1和key2,key1的hashCode值為3,key2的hashCode值為9,那么通過(guò)與數(shù)組長(zhǎng)度模運(yùn)算得到兩個(gè)數(shù)組下標(biāo)都是3,如果按照數(shù)組的存儲(chǔ)方式,后面存儲(chǔ)的必然會(huì)把前面存儲(chǔ)的值覆蓋,這種場(chǎng)景被稱(chēng)為哈希碰撞。
為解決哈希碰撞提出了兩種方法,分別為鏈表法和開(kāi)放尋址法。
開(kāi)放尋址法
開(kāi)放尋址法其原理就是,當(dāng)存儲(chǔ)元素的鍵下標(biāo)被占用時(shí),自動(dòng)查找下一個(gè)空擋位置存放值,如下

存在一個(gè)元素Entry2,計(jì)算其數(shù)組下標(biāo)為2,也就是Entry3的位置,計(jì)算出來(lái)的數(shù)組下標(biāo)被占用,那么就往下查找下一個(gè)元素但是被Entry4占用,再去查找為空的位置,直到查找到數(shù)組下標(biāo)為4的位置,插入元素保存即可。
這種方法在JAVA中的經(jīng)典應(yīng)用就是ThreadLocal~
鏈表法
鏈表法就是將散列表由單純的數(shù)組存儲(chǔ)改為數(shù)組+鏈表組合的形式存儲(chǔ),每個(gè)數(shù)組中的元素都可以理解為鏈表的頭節(jié)點(diǎn),當(dāng)需要存儲(chǔ)元素時(shí),先判斷該下標(biāo)元素是否為空如果為空之間作為頭節(jié)點(diǎn)插入,如果不為空則將該數(shù)組下標(biāo)元素頭節(jié)點(diǎn)指向需要插入的元素。

JAVA中的HashMap就是采用的鏈表法來(lái)解決哈希沖突,當(dāng)然鏈表法不是萬(wàn)無(wú)一失,當(dāng)鏈表過(guò)長(zhǎng)那么檢索的效率必然降低因?yàn)殒湵頇z索需要遍歷鏈表,時(shí)間復(fù)雜度為O(n),所以HashMap中還會(huì)涉及到擴(kuò)容,擴(kuò)容后將所有的元素重新哈希,以此來(lái)達(dá)到縮短鏈表長(zhǎng)度的目的。