第三章 哈希表

文章目錄

• ​​第三章 哈希表​​
• ​​一、概念​​

• ​​1.1哈希表​​
• ​​1.2哈希函數​​
• ​​1.3哈希碰撞​​

• ​​二、常見的三種哈希結構​​
• ​​三、題型​​

一、概念

1.1哈希表

哈希表（hash table），國内稱為散清單。

哈希表是根據關鍵碼的值而直接進行通路的資料結構

可以把哈希表了解成數組；哈希表是根據關鍵碼也就是數組索引下标通路元素：

那麼哈希表能解決什麼問題呢，一般哈希表都是用來快速判斷一個元素是否出現集合裡。

例如要查詢一個名字是否在這所學校裡。

1.2哈希函數

哈希函數，把學生的姓名直接映射為哈希表上的索引，然後就可以通過查詢索引下标快速知道這位同學是否在這所學校裡了。

哈希函數相當于一個轉換器，一個加密解碼的過程：

1.3哈希碰撞

如圖所示，小李和小王都映射到了索引下标 1 的位置，這一現象叫做哈希碰撞。

一般哈希碰撞有兩種解決方法， 拉鍊法和線性探測法。

二、常見的三種哈希結構

當我們想使用哈希法來解決問題的時候，我們一般會選擇如下三種資料結構。

• 數組
• set（集合）
• map（映射）

總結一下，當我們遇到了要快速判斷一個元素是否出現集合裡的時候，就要考慮哈希法。

但是哈希法也是犧牲了空間換取了時間，因為我們要使用額外的數組，set或者是map來存放資料，才能實作快速的查找。

三、題型

• 數組哈希法

​​242.有效的字母異位詞​​

• set集合哈希法

​​349.兩個數組的交集​​

​​15.三數之和​​

• map映射哈希法