一提到算法題里的哈希我第一反應(yīng)其實不是哈希表數(shù)據(jù)結(jié)構(gòu)的定義而是三個詞快速判斷、空間換時間、去重。不管是剛?cè)腴T的新手還是準(zhǔn)備筆試的應(yīng)聘者跟哈希相關(guān)的題目在各大平臺的出鏡率都相當(dāng)高。這篇內(nèi)容想把哈希題背后的出題邏輯、通用套路和容易踩坑的地方一次性講清楚。核心不是讓你背題而是讓你搞懂什么時候該用哈希用了以后復(fù)雜度會有什么變化以及怎么把哈希和雙指針、排序、滑動窗口這些常見技巧組合起來。無論你是刷了幾十題的新人還是做過幾百題卻總在細節(jié)上翻車的老手這篇文章應(yīng)該都能給你一些可復(fù)用的判斷思路和代碼模板。我會盡量用容易理解的語言講原理然后配上可以直接上手的示例代碼最后再把我實際做題和幫別人排查問題時碰到的坑單獨拿出來說。1. 哈希題的考法共同點先明白出題人在問什么想學(xué)會用哈希解題第一件事不是背API而是識別題目的真實訴求。哈希能解決的算法問題無論題目包裝成數(shù)組、字符串、鏈表還是矩陣本質(zhì)上幾乎都能歸納成下面三種情形之一成對存在、出現(xiàn)次數(shù)、唯一標(biāo)識。1.1 成對存在找配得上的元素最經(jīng)典的兩數(shù)之和就是這種。給你一個數(shù)組和一個目標(biāo)值問你哪兩個數(shù)的加和等于目標(biāo)值。最直接的雙層循環(huán)當(dāng)然是正確的時間復(fù)雜度O(n2)但如果數(shù)組長度上萬基本就跑不動了。換成哈希的思路就很簡單遍歷的時候把當(dāng)前這個數(shù)記為value那么我需要的另一半就是target減value。如果這一半已經(jīng)在哈希表里說明前面某個位置已經(jīng)出現(xiàn)過和目標(biāo)配對的值直接返回兩個下標(biāo)如果不在就把當(dāng)前值和下標(biāo)存進哈希。def two_sum(nums, target): seen {} for i, value in enumerate(nums): need target - value if need in seen: return [seen[need], i] seen[value] i return []這里就體現(xiàn)了哈希最大的優(yōu)勢一次遍歷邊存邊查查找時間從O(n)降到平均O(1)整體時間復(fù)雜度變成O(n)。出題人其實不是在考你怎么找到兩個數(shù)而是在考你怎么能在一次遍歷內(nèi)完成查找和記錄。只要把題目能識別成存在一個元素和當(dāng)前元素滿足某種關(guān)系就可以第一時間往哈希方向想。1.2 出現(xiàn)次數(shù)統(tǒng)計誰多誰少、誰重復(fù)了還有一種特別高頻的考法給你字符串或者數(shù)組問某個字符出現(xiàn)了幾次、哪些元素重復(fù)了、誰出現(xiàn)的次數(shù)最多。這種本質(zhì)就是在做頻次統(tǒng)計。部分題目可以用排序加雙指針來做但哈希往往是實現(xiàn)最簡單、理解成本最低的方案。以多數(shù)元素為例給一個數(shù)組返回出現(xiàn)次數(shù)超過一半的那個元素。最樸素的想法是兩個循環(huán)統(tǒng)計每個數(shù)的出現(xiàn)次數(shù)但更優(yōu)雅的方法是用哈希記錄每個數(shù)已經(jīng)出現(xiàn)的次數(shù)并在過程中判斷是否超過閾值。對于這類問題哈希真正省掉的不是那一次次比較而是重新掃描整個數(shù)組的重復(fù)勞動。你只需要把每個元素往哈希表里塞一次之后所有的判斷都是O(1)級別。另一個很有代表性的例子是字母異位詞分組。異位詞的意思是組成字母相同但排列不同比如ate和eat就是一對。如果兩個字符串是異位詞那么它們排序后的結(jié)果完全一致。用排序結(jié)果作為哈希鍵把同一組詞歸到一個桶里代碼會特別干凈。def group_anagrams(strs): from collections import defaultdict groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())這里面的技巧是用排序后的字符串作為鍵。排序本身是O(k log k)k是一個單詞的長度通常很小整個算法算下來批量排序也遠比兩兩比較字符串要劃算。1.3 唯一標(biāo)識快速判斷這件事之前有沒有見過第三種常見場景是判斷是否出現(xiàn)過或者建立從某個對象到另一個對象的映射。比如鏈表里判斷是否有環(huán)或者記錄一個坐標(biāo)對是否已經(jīng)訪問過。這類問題你完全可以不用哈希改用數(shù)組、Set或者布爾矩陣但哈希的可擴展性最好——它不要求你知道待處理元素的取值范圍也不要求元素必須是整數(shù)。所以刷哈希題之前我建議你先把題目歸個類是找另一半、是統(tǒng)計頻次、還是判斷唯一性。分類做對了代碼怎么寫基本就有思路了。2. 哈希表內(nèi)部怎么工作搞懂?dāng)?shù)組加鏈表才敢談優(yōu)化很多刷題教程會直接從API用法開始講哈希但我覺得要真正會用哈希解題至少應(yīng)該知道它底層做了什么。哈希表的核心思路可以概括成一句話用一個計算函數(shù)把任意類型的鍵映射成一個數(shù)組下標(biāo)。不同的鍵可能被映射到同一個下標(biāo)這種情況叫沖突解決沖突的典型辦法是在同一個下標(biāo)下面掛一個鏈表也就是大多數(shù)人見到的數(shù)組加鏈表結(jié)構(gòu)。2.1 哈希函數(shù)、沖突與擴容哈希函數(shù)是哈希表性能好壞的關(guān)鍵。函數(shù)設(shè)計得好鍵分布得均勻查找就是一次數(shù)組訪問函數(shù)設(shè)計得差大量鍵擠在同一個位置哈希表就退化成了鏈表復(fù)雜度回到O(n)。這也是為什么實際哈希表的實現(xiàn)會考慮擾動函數(shù)、紅黑樹轉(zhuǎn)換、負載因子擴容這些工程細節(jié)。負載因子可以簡單理解為桶里裝了多少數(shù)據(jù)的擁擠程度。當(dāng)已有元素數(shù)量除以桶總數(shù)超過某個閾值時哈希表會自動擴容把桶數(shù)量加大再把所有元素重新映射一遍。這個過程叫rehash開銷不小所以在筆試?yán)锶绻隳芴崆肮浪銛?shù)據(jù)量給哈希表指定一個足夠的初始容量往往能省掉大量擴容時間。以主流語言為例語言常用哈希結(jié)構(gòu)底層實現(xiàn)概要無序/有序Pythondict / set哈希表鍵需要可哈希有序插入序但依賴版本JavaHashMap / HashSet數(shù)組加鏈表鏈表過長轉(zhuǎn)紅黑樹無序Cunordered_map / unordered_set哈希表實現(xiàn)無序Gomap哈希桶加溢出桶隨機無序2.2 刷題時真正需要記住的只有三件事第一哈希的平均查找時間是O(1)但這是平均情況不是絕對保證。第二哈希表的空間開銷并不小每個鍵值對都要額外存儲哈希信息所以空間換時間這個說法是準(zhǔn)確的。第三哈希表對鍵的類型有要求不是所有對象都能直接作為鍵。在Python里只有不可變類型才能放進dict或set當(dāng)key列表、字典這類可變對象會直接報類型錯誤。這也是為什么很多人用坐標(biāo)做題時會選擇用元組而不是列表。你說這些底層細節(jié)對刷題有用嗎當(dāng)然有用。比如你遇到了一個兩數(shù)之和的變種題要求不能用額外空間這時候你就得意識到哈希雖然好用但違背了空間限制必須退回排序或雙指針。如果不知道哈希占用額外空間這個題一上來就會做錯方向。3. 以計數(shù)器為骨架的哈希解法三道題能復(fù)用一套代碼如果看多了哈希相關(guān)的題你會發(fā)現(xiàn)很多題的核心就是一個計數(shù)器也就是用一個字典來記錄每個鍵出現(xiàn)的次數(shù)。這種解法本身并不復(fù)雜難的是你能否識別出這個題其實只需要一個計數(shù)器就能搞定。3.1 從每個字符出現(xiàn)的次數(shù)到判斷字符串能否重新排列判斷一個字符串能否通過重排變成另一個字符串其實就是判斷兩個字符串的字符構(gòu)成是否完全一致。最簡單的做法就是分別統(tǒng)計兩個字符串中每個字符的出現(xiàn)次數(shù)然后比較統(tǒng)計結(jié)果是否相等。Python里甚至可以不用遍歷比較直接用Counter對象比較Counter(s) Counter(t)。表面上看這是一行代碼背后其實已經(jīng)做了兩次數(shù)頻統(tǒng)計。這類題的通式代碼是這樣的from collections import Counter def can_permute(s1, s2): if len(s1) ! len(s2): return False return Counter(s1) Counter(s2)這個通式的要點在于凡是涉及判斷兩個集合的構(gòu)成是否一致都可以先統(tǒng)計頻次再比較頻次表。無論是異位詞、重排、還是字符串能否通過刪除一個字符變成另外一個本質(zhì)上都在這個框架里。3.2 計數(shù)器加排序的兩種思路對比處理字符串分組這類問題時有兩種常見思路。第一種是排序后當(dāng)鍵代碼簡單但每處理一個字符串都要做一次排序第二種是計數(shù)后當(dāng)鍵也就是把每個字符的出現(xiàn)次數(shù)拼成一個固定的表示形式比如a3b2c1用它當(dāng)哈希鍵。第二種思路的核心在于它把同一組異位詞統(tǒng)一映射到同一個鍵上不需要排序每次只遍歷一次字符串所以在字符種類有限且字符串?dāng)?shù)量比較大的場景下更有優(yōu)勢。代碼大致是from collections import defaultdict def group_anagrams_by_count(strs): groups defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 key tuple(count) groups[key].append(s) return list(groups.values())注意這里的key用的是tuple(count)因為列表不能作為字典鍵轉(zhuǎn)成元組后就可以進行哈希了。這個細節(jié)很容易被忽略但恰恰是很多初學(xué)者在本地運行報錯的原因。當(dāng)題目給的是小寫字母時長度26的計數(shù)數(shù)組是okay的但如果是Unicode字符或數(shù)字混合的情況就要改成通用Counter方案。拿到這類題先看字符范圍再決定用計數(shù)數(shù)組還是通用哈希這會節(jié)省不少時間。4. 哈希配合雙指針滑動窗口維護合法狀態(tài)才是靈魂單純使用哈希的題目難度通常不高真正容易拉開差距的是哈希加滑動窗口的復(fù)合題。這類題表面上是雙指針但窗口內(nèi)狀態(tài)的合法性往往需要一個額外的哈希表來維護。4.1 最長無重復(fù)字符子串窗口加哈希的教科書給定一個字符串請你找出其中不含有重復(fù)字符的最長子串的長度是高頻中的高頻。思路不復(fù)雜用兩個指針維護一個窗口右指針負責(zé)擴展窗口并記錄字符出現(xiàn)位置當(dāng)遇到重復(fù)字符時左指針跳到重復(fù)字符上一次出現(xiàn)位置的后面同時更新哈希中記錄的字符位置。def length_of_longest_substring(s: str) - int: pos {} left 0 ans 0 for right, ch in enumerate(s): if ch in pos and pos[ch] left: left pos[ch] 1 pos[ch] right ans max(ans, right - left 1) return ans這里有個非常關(guān)鍵的細節(jié)判斷是否存在重復(fù)字符時不只是判斷ch in pos還要判斷pos[ch] left。原因很簡單窗口左邊界已經(jīng)移動之后舊位置如果再出現(xiàn)不算重復(fù)因為那些字符已經(jīng)不在當(dāng)前窗口范圍內(nèi)了。忽略這個判斷這個代碼就會在abba這種用例上出錯。4.2 哈希表記錄的三種形態(tài)位置、次數(shù)、最新值在滑動窗口類題目中哈希表里的值會以三種形態(tài)出現(xiàn)。第一種存位置像上面這個例子。第二種存次數(shù)比如最小覆蓋子串這類題需要通過哈希表統(tǒng)計滑動窗口內(nèi)某個字符還需要多少個。第三種存最新狀態(tài)比如某些需要維護最近一次出現(xiàn)的場景。存位置時要時刻注意收斂左指針時的邊界條件存次數(shù)時要注意更新頻率的增減是否可能讓狀態(tài)誤判存最新值時要小心過期數(shù)據(jù)被重復(fù)使用。招數(shù)本身不復(fù)雜但很多人掛了是因為對什么時候更新哈希、什么時候讀取哈希沒有理清。我的建議是寫代碼前先在注釋里把窗口的合法定義寫出來再開始動代碼。哈希只是工具窗口的規(guī)則才是靈魂。5. 把復(fù)雜對象拍平成哈希鍵處理坐標(biāo)題和緩存設(shè)計的關(guān)鍵哈希表不僅能存整數(shù)和字符串還能存元組、對象甚至你自定義的結(jié)構(gòu)。但筆試和面試中很多人在什么可以當(dāng)鍵這個問題上吃虧。最常見的例子是處理坐標(biāo)類題目。5.1 坐標(biāo)對、矩陣狀態(tài)與元組鍵如果題目給你一個矩陣問是否存在某個坐標(biāo)模式比如某個點是否在之前出現(xiàn)過你可以把坐標(biāo)轉(zhuǎn)成元組(x, y)直接作為哈希鍵。在Python里元組是不可變類型也是可哈希的所以下面這種寫法完全合法visited {} visited[(2, 3)] True如果是二維平面棋盤上某個格子的狀態(tài)甚至可以直接用(row, col)作為鍵去存儲狀態(tài)值。刷題時把多個值拼成一個不可變元組是建模的一招暗器。有時候你需要的鍵其實是兩個點組成的邊這時候可以拼(x1, y1, x2, y2)這樣的四元組只要不擔(dān)心空間哈?？偰軒湍惆褟?fù)雜問題建模成鍵到值的快速查找。5.2 緩存設(shè)計哈希加雙向鏈表的經(jīng)典形態(tài)哈希在工程里最知名的應(yīng)用之一就是LRU緩存也就是最近最少使用淘汰策略。這個題目在面試中出現(xiàn)頻率極高因為它同時考查哈希表的隨機訪問能力和鏈表的順序維護能力。思路是哈希表負責(zé)O(1)快速找到節(jié)點雙向鏈表負責(zé)維護訪問的時間順序。每次訪問一個鍵就把對應(yīng)節(jié)點移到鏈表頭部緩存滿了就刪除鏈表尾部的節(jié)點并同時從哈希表里移除對應(yīng)鍵。如果只給哈希表訪問是快了但無法維護順序如果只給鏈表維護順序方便但查找慢。兩者結(jié)合剛好互相補充。這類題的價值不僅在于記住實現(xiàn)代碼更在于理解哈希和其他數(shù)據(jù)結(jié)構(gòu)組合的思路。很多看似復(fù)雜的題目其實就是把哈希當(dāng)成一個加速查找的索引再用其他結(jié)構(gòu)解決順序、大小、窗口這類問題。5.3 自定義對象作為哈希鍵時的注意事項有基礎(chǔ)以后你可能會遇到需要把自定義對象放哈希表的情況。在Java里如果你不重寫hashCode和equals兩個內(nèi)容相同的對象會被當(dāng)成兩個不同的鍵這會導(dǎo)致你明明往哈希里存了數(shù)據(jù)卻查不到。在Python中則要注意把對象轉(zhuǎn)成可哈希的表示比如使用元組、凍結(jié)集合或自定義__hash__方法。筆試的時候能不用自定義對象就盡量不用自定義對象哪怕繁瑣一點用普通元組表示狀態(tài)更穩(wěn)妥也更容易調(diào)試。6. 筆試和工程里的哈希差異別再在本地測完就交很多人刷題的時候把Python的dict用得非常順手但到了真正的工程環(huán)境哈希表的行為會和提供算法答案很不一樣。這些問題不會直接暴露在大多數(shù)線上判題的用例里但做技術(shù)討論或者項目開發(fā)時會突然變成事故。6.1 遍歷順序帶來的隱性Bug我用Go寫過一個數(shù)據(jù)聚合的小任務(wù)最開始用map存儲分組結(jié)果然后直接按map順序輸出結(jié)果每次運行輸出順序都不一樣。查到最后才發(fā)現(xiàn)Go的map遍歷本身就是隨機的語言層面的設(shè)計就是為了強制開發(fā)者不依賴遍歷順序。如果你需要穩(wěn)定順序必須先把鍵排序或者改用有序結(jié)構(gòu)。Python 3.7以后dict保留插入順序Java的HashMap不保證順序C的unordered_map也不保證。這類差異筆試?yán)锶绻簧婕绊樞蜉敵鐾ǔ]事但如果出題人給了一個需要按固定順序返回結(jié)果的題目你就要反思一下是不是該換用有序映射了。6.2 并發(fā)修改哈希表并不總是線程安全在并發(fā)場景下使用哈希表要格外小心。Java的HashMap在多線程并發(fā)寫入時可能引發(fā)數(shù)據(jù)覆蓋甚至無限循環(huán)所以工程上往往會改用ConcurrentHashMap。Go的map在并發(fā)讀寫時會直接觸發(fā)運行時panic。刷題時完全不用考慮這些但如果你在項目里寫過一個被并發(fā)訪問的普通map就會明白那些標(biāo)準(zhǔn)庫的坑不是危言聳聽。如果你的面試環(huán)節(jié)涉及系統(tǒng)設(shè)計或?qū)嶋H項目提問能主動說出我用的是并發(fā)安全的哈希結(jié)構(gòu)并說明了并發(fā)讀寫的取舍這通常會是一個加分點。6.3 哈希函數(shù)和對象哈希值的坑自己實現(xiàn)哈希函數(shù)或者在某個哈希結(jié)構(gòu)里存放大量非基礎(chǔ)類型數(shù)據(jù)時最容易忽略的是哈希值的分布質(zhì)量。比如用hash x * 31 y這類簡單公式處理坐標(biāo)時如果數(shù)據(jù)存在規(guī)律性可能讓大量鍵映射到同一個桶。筆試也許不會直接考哈希函數(shù)設(shè)計但你知道這個原理就能在任何需要把對象映射為一個整數(shù)的場景里留個心眼。7. 收尾的個人清單我判一道題該不該用哈希的思考順序?qū)懥诉@么多最后還是想分享一套我自己做題時用來判斷這道題要不要上哈希的思考順序。這套順序不是萬能的但幫我減少了很多無效嘗試。第一步看題目有沒有查找動作。無論是找數(shù)、找下標(biāo)、找狀態(tài)只要需要反復(fù)查找優(yōu)先考慮哈希。第二步看題目有沒有去重或頻次的描述。判斷重復(fù)元素、統(tǒng)計字符次數(shù)、找出現(xiàn)次數(shù)最多的元素這些基本是哈希的主場。第三步看有沒有成對關(guān)系。兩數(shù)之和、四數(shù)相加、判斷是否存在對稱組合這些題要配對一般也可以走哈希。第四步看是否存在空間限制。如果題目明確要求O(1)額外空間哈?；局荒芊艞夀D(zhuǎn)向排序加雙指針。在實際做題和幫別人梳理代碼的時候我發(fā)現(xiàn)把自己的解法先歸類到上面其中一類能減少不少跑偏時間。哈希題看著花樣多核心獵物就那幾種。把底層原理、API差異和這四步判斷在腦子里過一遍大部分哈希題都能找到清晰的解法路徑。最后再分享一個小技巧每做完一道哈希題把這道題提煉成一句話放到自己的筆記里比如這道題用排序后的字符串當(dāng)鍵這道題用元組當(dāng)鍵存儲坐標(biāo)訪問狀態(tài)。積累一段時間后你會發(fā)現(xiàn)那些看起來全新的題目其實只是你筆記本里幾個套路的變體。