一、今日學習目標

掌握哈希表的核心理論（哈希函數、哈希碰撞及解決方法），理解數組、set、map 三種哈希結構的適用場景，并通過「兩個數組的交集」「快樂數」「兩數之和」三道題目，實戰掌握哈希表在快速查找、去重、鍵值映射等場景的應用。

二、核心理論知識

1、哈希表的數學本質

理論知識

哈希表是一種通過「關鍵碼直接訪問數據」的數據結構，其核心是哈希函數—— 將關鍵碼（如數值、字符串）映射為哈希表的索引，實現 O (1) 級別的快速訪問。從數學角度看，哈希函數可表示為：
index=hashFunction(key) mod tableSize

2、哈希碰撞與解決方法

當不同關鍵碼映射到同一索引時，產生哈希碰撞，常見解決方法：

• 拉鏈法：在碰撞索引處構建鏈表，存儲所有沖突元素（如 Java 的 HashMap）。需合理設置tableSize，避免鏈表過長影響效率。
• 線性探測法：當碰撞發生時，依次檢查下一個索引（index+1, index+2...），要求tableSize > dataSize（數據量），確保有足夠空位。

3、三種常見的哈希結構對比

結構	底層實現	使用場景
數組	連續內存	關鍵碼范圍小且連續
set	紅黑樹、哈希表	需去重且無需存儲額外信息
map	紅黑樹、哈希表	需存儲鍵值對

三、實戰解題

1、有效的字母異位詞

題目描述

LeetCode 242 有效的字母異位詞

代碼實現

文章講解

Python代碼

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""record = [0]*26for i in s:record[ord(i)-ord('a')] += 1for i in t:record[ord(i)-ord('a')] -= 1for i in range(26):if record[i] != 0:return  Falsereturn True

調試過程

通過調試發現，看似簡單的計數邏輯，需重點關注輸入合法性（長度、字符范圍）和效率優化（提前終止），這也是哈希表類問題的通用調試要點 —— 既要保證邏輯正確，也要兼顧邊界場景和性能。

2、兩個數組的交集

題目描述

LeetCode 349 兩個數組的交集

代碼實現

文章講解

Python代碼

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""table = {}for num in nums1:table[num] = table.get(num, 0)+1res = set()for num in nums2:if num in table:res.add(num)del table[num]return list(res)

調試過程

最初嘗試用列表存儲結果，未考慮去重，導致輸出包含重復元素（如示例中 nums2 的兩個 4）。改用 set 存儲結果后，自動去重問題解決。

3、快樂數

題目描述

LeetCode 202 快樂數

代碼實現

文章講解

Python代碼

class Solution(object):def isHappy(self, n):""":type n: int:rtype: bool"""seen = []while n != 1:n = sum(int(i)**2 for i in str(n))if n in seen:return Falseseen.append(n)return True

調試過程

最初忽略了「無限循環」的本質，未用 set 記錄中間結果，導致程序陷入死循環。加入 set 后，當檢測到重復的 n 時，可直接判斷為非快樂數。

4、兩數之和

題目描述

LeetCode 1 兩數之和

代碼實現

文章講解

Python代碼

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""records = dict()for index, value in enumerate(nums):if target - value in records:return [records[target - value], index]records[value] = indexreturn []

調試過程

通過調試發現，該解法的關鍵在于哈希表存儲元素與索引的映射，并利用遍歷順序確保重復元素的索引正確性。需注意的邊界條件包括：

1. 重復元素：哈希表覆蓋索引的行為因遍歷順序而不影響結果；

2. 無解情況：需確保代碼返回空列表而非報錯；

3. 特殊數值：負數、零等需驗證哈希表查詢邏輯。

四、易錯點總結

題目	易錯點	解決方法
兩個數組的交集	結果未去重；用數組導致空間浪費	用 set 存儲結果；數值范圍不確定時優先用 set
快樂數	未檢測循環導致死循環；求和時漏處理個位	用 set 記錄中間結果；用 divmod 統一處理各位
兩數之和	用 set 無法存儲下標；忽略元素重復情況	用 map 存儲鍵值對；依賴遍歷順序避免重復使用

五、擴展思考

1.** 哈希函數設計?：好的哈希函數應盡量減少碰撞，可結合數論中的「素數取模」（如 HashMap 的容量為 2?，減少碰撞概率）。
2.?時間復雜度對比 **：

• 數組：查詢 O (1)，但空間復雜度 O (M)（M 為最大可能值）；

• unordered_set/map：查詢 O (1)（平均），空間 O (n)，適合大數據量；

• set/map（紅黑樹）：查詢 O (logn)，但有序，適合需排序的場景。