首先，我們來下一個定義：哈希表是根據(jù)關(guān)鍵碼的值而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。

哈希表的定義：

一看到這個這個定義是不是有點懵逼

這里舉了一個例子：【?數(shù)組】 就是一張哈希表。

那么我們就來對應(yīng)一下哈希表的定義：

? ? ? ??關(guān)鍵碼的值就是數(shù)組下標

? ? ? 數(shù)組可以直接訪問

那么哈希表能解決什么問題捏？ 由于關(guān)鍵值來索引，我們可以快速判斷一個元素是否出現(xiàn)集合里面。

舉個例子： 要在學(xué)校里面找到我的名字，一水的人名存在哈希表里面。我們通過關(guān)鍵碼（學(xué)號）找到俺。 但是要怎么裝學(xué)生進哈希表里面捏？

? ?我們引入：【哈希函數(shù)】就是把學(xué)生名 和哈希表的關(guān)鍵碼依次對應(yīng)上，然后通過關(guān)鍵碼找到學(xué)生名

我們說到數(shù)組就是hash table但是，總有一個名字不小心用到同一個學(xué)號的時候。這個時候就是遇到了哈希碰撞。

遇到哈希碰撞，我們用拉鏈法和線性探測法。

拉鏈法：

啥叫拉鏈??？ 字面意思：拉一條鏈子把沖突的連起來。

如圖所示就是拉鏈法，需要注意的是：需要選擇合適的hash表大小

常見的三種哈希結(jié)構(gòu)

當(dāng)我們想使用哈希法來解決問題的時候，我們一般會選擇如下三種數(shù)據(jù)結(jié)構(gòu)。

• 數(shù)組

• set （集合）

• map(映射