上一節介紹了哈希表的原理與設計方法，這一節則直接python中現有的哈希表類型：哈希集合 set（集合）和哈希映射 dict（字典）來解決實際應用（刷題）。

零、概念
在介紹實際應用之前，有一個概念我認為是應該了解的，那就是可哈希（hashable）。官方的術語介紹如下：

一個對象的哈希值如果在其生命周期內絕不改變，就被稱為 可哈希 （它需要具有 __hash__() 方法），并可以同其他對象進行比較（它需要具有 __eq__() 方法）。可哈希對象必須具有相同的哈希值比較結果才會相同。

可哈希性使得對象能夠作為字典鍵或集合成員使用，因為這些數據結構要在內部使用哈希值。

大多數 Python 中的不可變內置對象都是可哈希的；可變容器（例如列表或字典）都不可哈希；不可變容器（例如元組和 frozenset）僅當它們的元素均為可哈希時才是可哈希的。 用戶定義類的實例對象默認是可哈希的。 它們在比較時一定不相同（除非是與自己比較），它們的哈希值的生成是基于它們的 id()。

我的理解就是：由于python實現的集合和字典是基于哈希表或哈希函數的，為了確保鍵的唯一性（鍵與哈希值一 一對應），則規定集合成員和字典中的鍵必須是可哈希的，這意味著其值在其生命周期內不會改變，所以又叫做不可變的。這樣， Python 就可以創建一個唯一的哈希值來識別它，字典可以使用它來跟蹤唯一鍵和集合來跟蹤唯一值。

不可變類型（immutable types）：int, float, decimal, complex, bool, string, tuple, range, frozenset, bytes

可變類型（mutable types）：list, dict, set, bytearray, user-defined classes

一、哈希集合的應用

集合是用來存儲非重復值的數據結構，因此，很自然地想到用集合進行查重和去重。

217.存在重復元素

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:hashset = set() # 初始化for i in nums:if i in hashset: # 元素是否為集合的成員return Trueelse:hashset.add(i) # 元素添加到集合return False

136. 只出現一次的數字

class Solution:def singleNumber(self, nums: List[int]) -> int:ans = set()for num in nums:if num in ans:ans.remove(num)else:ans.add(num)return ans.pop()

雖然可以用集合解決，但是此題最優的做法是位運算，原理是相同的數做異或運算 ^ 會得到0，而一個數與0做異或會得到這個數本身。所以，數組里面所有相同的數異或會得到0，而那個只出現一次的數再與0做異或，直接得到結果本身，代碼如下：

class Solution:def singleNumber(self, nums: List[int]) -> int:ans = nums[0]for i in range(1, len(nums)):ans = ans ^ nums[i]return ans

349. 兩個數組的交集

用自帶的set，顯然 return list(set(nums1) & set(nums2)) 即可，如果是自己實現取交集的操作呢？

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:set1 = set(nums1)set2 = set(nums2)return self.set_intersection(set1, set2)def set_intersection(self, set1, set2) -> List[int]:if len(set1) > len(set2): # 考慮較小的數組return self.set_intersection(set2, set1)return [x for x in set1 if x in set2]

小技巧，兩個數組的交集一定是在較小的數組當中。

202. 快樂數

class Solution:def isHappy(self, n: int) -> bool:notHappy = set()while True:numbers = list(str(n))total = 0for number in numbers:total += int(number) ** 2if total == 1:return Trueelif total in notHappy: # 陷入無限循環return Falseelse:notHappy.add(total)n = total

不停重復這個過程，直到這個數等于1（是快樂數），或者這個數等于之前出現過的數（陷入無限循環）。

二、哈希映射的應用

哈希映射是用于存儲 (key, value) 鍵值對的一種實現，這意味著，我們在需要存儲比鍵 key 的信息更多的信息（值 value 的信息）時，需要用到哈希映射。python中的對應自帶類型為字典 dict。

1. 兩數之和

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:record = dict()for i, num in enumerate(nums):if target - num in record:return [record[target - num], i]else:record[num] = i

這里的字典，就不僅存放了 nums 中不同元素的索引（作為鍵 key），還存放了 target - num 的值（作為值 value），這樣當有元素等于這個值時，說明它們之和為target，同時可以輸出它們的對應索引（鍵 key）。

更多關于兩數、三數、四數之和的題解，可以看我的這篇文章。

205. 同構字符串

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:s_table = dict()t_table = dict()for i in range(len(s)):if (s[i] in s_table and s_table[s[i]] != t[i]) or (t[i] in t_table and t_table[t[i]] != s[i]):return Falseelse: if s[i] not in s_table:s_table[s[i]] = t[i] # s到t的關系if t[i] not in t_table:t_table[t[i]] = s[i] # t到s的關系return True

判斷兩個字符串是否同構，即存在某種對應關系，注意這個關系得是雙向成立的，因為可能字符串1中 a -> b 一定成立，但是字符串2中 b -> a 不一定成立。

599. 兩個列表的最小索引總和

class Solution:def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:RestaurantTable = dict()ans = list()num = 2005 # 大于2000即可for i, restaurant1 in enumerate(list1):RestaurantTable[restaurant1] = ifor j, restaurant2 in enumerate(list2):if restaurant2 in RestaurantTable and RestaurantTable[restaurant2] + j <= num:if RestaurantTable[restaurant2] + j < num:ans.clear()ans.append(restaurant2)num = RestaurantTable[restaurant2] + jelse:ans.append(restaurant2)return ans

用字典記錄一個數組中的餐廳和對應索引值，再遍歷另一個數組，如果出現同一個餐廳并且索引之和小于等于當前的最小值 num，則更新 ans 和 num（小于）或者添加餐廳到 ans（等于）。

387. 字符串中的第一個唯一字符

class Solution:def firstUniqChar(self, s: str) -> int:Hashtable = dict()for i, char in enumerate(s):if char in Hashtable:Hashtable[char] = -1else:Hashtable[char] = ians = len(s)for char in Hashtable:if Hashtable[char] != -1 and Hashtable[char] < ans:ans = Hashtable[char]return ans if ans != len(s) else -1

遍歷字符串，新出現的字符記錄其索引，后面如果重復出現該字符，則值變成 -1（無論多少次出現都是 -1）。然后從ans = len(s) 開始，找到具有最小索引值的字符，若不存在則返回 -1。

350. 兩個數組的交集 II

class Solution:def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:if len(nums1) > len(nums2):return self.intersect(nums2, nums1)c = collections.Counter()for n in nums1:c[n] += 1 ans = list()for m in nums2:if m in c and c[m] > 0:ans.append(m)c[m] -= 1return ans

開頭還是小技巧，交集一定在較小的數組中。然后這里用到的是計數器類型 collections.Counter()，它是一個 dict 的子類，用于計數可哈希對象。它的特點就是如果引用的鍵沒有任何記錄，就返回一個0，而不是報錯 KeyError 。這里的計數器用于存放元素在數組 nums1 出現的次數，然后遍歷數組 nums2，每次邊添加結果邊計數器減一。這樣就能使得輸出結果中每個元素出現的次數，與元素在兩個數組中出現次數的最小值一致。

219. 存在重復元素 II

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:hashtable = dict()for i, num in enumerate(nums):if num in hashtable and abs(i - hashtable[num]) <= k:return Trueelse:hashtable[num] = ireturn False

用字典記錄元素和它的索引值，后面出現相同元素時判斷是否符合條件，不符合條件就更新索引值（離下一個相同元素更近）。

220. 存在重復元素 III

class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:table = dict()for i in range(len(nums)):bucket_num = nums[i] // (t + 1) # 取商數作為桶的編號，每個桶大小為 t + 1# 存在當前編號的桶，即桶里面已經有東西了，則它們的值一定相差不大于 tif bucket_num in table:return Truetable[bucket_num] = nums[i]# 存在上一個編號的桶，到里面看看是否符合條件if (bucket_num - 1) in table and abs(table[bucket_num - 1] - nums[i]) <= t:return True# 存在下一個編號的桶，到里面看看是否符合條件if (bucket_num + 1) in table and abs(table[bucket_num + 1] - nums[i]) <= t:return True# 當 i 大于等于 k 時，下次遍歷（i + 1）就不能考慮 nums[i-k] 了if i >= k:table.pop(nums[i - k] // (t + 1))return False

這題的核心思想就是分桶（分組），將遍歷得到的數按數值范圍放入不同的桶中（注意是取商數分桶而不是取余數），每個桶的大小為 t + 1。這樣當有兩個數出現在同一個桶時，它們的差距一定是小于等于 t 的；同一個桶中只有一個的話，就到相鄰的桶看看是否符合條件，不相鄰的桶就不用考慮了（值的差距一定大于 t）；最后要把距離當前索引 k 的那個值對應的桶刪掉（索引的差距大于 k）。

359. 日志速率限制器

class Logger:def __init__(self):"""Initialize your data structure here."""self.hashtable = dict()def shouldPrintMessage(self, timestamp: int, message: str) -> bool:"""Returns true if the message should be printed in the given timestamp, otherwise returns false.If this method returns false, the message will not be printed.The timestamp is in seconds granularity."""if message in self.hashtable:if timestamp >= self.hashtable[message]:self.hashtable[message] = timestamp + 10return Trueelse:return Falseelse:self.hashtable[message] = timestamp + 10return True

用字典記錄信息和它下一次可以打印的時間，實際上只有打印過并且沒到下一次時間的信息會返回False，其余都是更新時間并返回True。

總結

以上是生活随笔為你收集整理的哈希表（散列表）基础概念与经典题目（Leetcode题解-Python语言）之中——实际应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。