散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。

哈希表中關(guān)鍵碼就是數(shù)組的索引下標(biāo)，然后通過(guò)下標(biāo)直接訪問數(shù)組中的元素，復(fù)雜度O(1)

哈希表本質(zhì)上是個(gè)數(shù)組，實(shí)現(xiàn)哈希表我們可以采用兩種方法：

1、數(shù)組+鏈表

2、數(shù)組+二叉樹

哈希函數(shù)

類似一個(gè)函數(shù)似的，給你一個(gè)值，經(jīng)過(guò)某些加工得到另外一個(gè)值，就像這里的給你個(gè)人名，經(jīng)過(guò)些許加工我們拿到首字母，那么這個(gè)函數(shù)或者是這個(gè)方法在哈希表中就叫做散列函數(shù)，其中規(guī)定的一些操作就叫做函數(shù)法則?

鍵值對(duì)，在jdk中就叫Entry

拉鏈法

剛剛小李和小王在索引1的位置發(fā)生了沖突，發(fā)生沖突的元素都被存儲(chǔ)在鏈表中。 這樣我們就可以通過(guò)索引找到小李和小王了

其實(shí)拉鏈法就是要選擇適當(dāng)?shù)墓１淼拇笮?#xff0c;這樣既不會(huì)因?yàn)閿?shù)組空值而浪費(fèi)大量?jī)?nèi)存，也不會(huì)因?yàn)殒湵硖L(zhǎng)而在查找上浪費(fèi)太多時(shí)間。?

線性探測(cè)法

使用線性探測(cè)法，一定要保證tableSize大于dataSize。 我們需要依靠哈希表中的空位來(lái)解決碰撞問題。

例如沖突的位置，放了小李，那么就向下找一個(gè)空位放置小王的信息。

?