散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內存存儲位置的數(shù)據(jù)結構。

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

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

1、數(shù)組+鏈表

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

哈希函數(shù)

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

鍵值對，在jdk中就叫Entry

拉鏈法

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

其實拉鏈法就是要選擇適當?shù)墓１淼拇笮?#xff0c;這樣既不會因為數(shù)組空值而浪費大量內存，也不會因為鏈表太長而在查找上浪費太多時間。?

線性探測法

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

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

?