翻開我之前的學(xué)習(xí)記錄這兩天一直在跟哈希表死磕。今天是第6天也是哈希表專題的第二輪。比起第一輪那種“原來還有這么神奇的數(shù)據(jù)結(jié)構(gòu)”的新鮮感這一輪我重點(diǎn)盯的是兩件事一是哈希表的底層實(shí)現(xiàn)到底怎么回事二是大家天天掛在嘴邊的“哈希表”和“字典”究竟是不是同一個(gè)東西。如果你也在系統(tǒng)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)或者在準(zhǔn)備面試又或者在項(xiàng)目里總是遇到“HashMap查詢慢”“dict內(nèi)存大”之類的困惑這篇文章應(yīng)該適合你。我會(huì)從原理、實(shí)現(xiàn)、刷題用法、實(shí)戰(zhàn)踩坑四個(gè)維度把這幾天摸出來的經(jīng)驗(yàn)完整記錄下來。全程沒有繞彎的教科書話術(shù)都是我自己手寫、實(shí)測、跑過例子的結(jié)論。1. 哈希表的底層邏輯它在解決什么問題1.1 哈希表本質(zhì)上是一套“空間換時(shí)間”的方案先聊一個(gè)基礎(chǔ)問題在沒有哈希表之前我們想存一堆“鍵值對(duì)”并快速按key取值該怎么辦最笨的方案是線性表像個(gè)檔案柜一樣一格一格擺好。插入的時(shí)候直接丟在末尾很方便但查找的時(shí)候得從頭翻到尾數(shù)據(jù)量一大就變成災(zāi)難。另一種方案是用有序結(jié)構(gòu)比如二叉搜索樹、跳表查找是 O(log n)已經(jīng)好了很多但仍然不是“一步到位”。哈希表的思路完全不一樣。它先把key通過一個(gè)“哈希函數(shù)”加工成一個(gè)數(shù)字再讓這個(gè)數(shù)字直接對(duì)應(yīng)到數(shù)組的下標(biāo)。想象你去圖書館借書管理員并不滿書架翻找而是根據(jù)索書號(hào)直接走到對(duì)應(yīng)的那一排那一格。存儲(chǔ)和讀取都精確到位置不用對(duì)比、不用遍歷。這就是為什么哈希表在平均情況下能做到 O(1) 的插入、刪除、查找。代價(jià)是什么呢是一個(gè)容量確定的數(shù)組。數(shù)組開小了裝不下幾組數(shù)據(jù)開大了內(nèi)存空著也是成本。典型的以空間換時(shí)間。我在實(shí)際寫代碼時(shí)經(jīng)常用一句話給自己提神哈希表不是“存數(shù)據(jù)的地方”而是一張“根據(jù)key直接定位地址的地圖”。只要哈希函數(shù)穩(wěn)定、沖突足夠少這張地圖就能讓查詢像讀數(shù)組一樣快。1.2 哈希函數(shù)的選擇與沖突處理的取舍哈希函數(shù)是哈希表的心臟。它負(fù)責(zé)把任意類型的key字符串、數(shù)字、對(duì)象映射成數(shù)組下標(biāo)。最基礎(chǔ)也最常見的做法是取模運(yùn)算index hash(key) % capacity但這里有幾個(gè)細(xì)節(jié)非常影響效果。第一hash(key) 本身要足夠“散”。如果寫了一個(gè)糟糕的哈希函數(shù)比如把字符串每個(gè)字符的ASCII碼簡單相加那么 “abc” 和 “cab” 會(huì)得到完全相同的值沖突率會(huì)直線上升。關(guān)于這點(diǎn)我在手寫實(shí)現(xiàn)時(shí)特意參考了 Java String 的經(jīng)典思路對(duì)每個(gè)字符執(zhí)行result result * 31 charValue。乘以 31 是個(gè)經(jīng)驗(yàn)值因?yàn)?31 是質(zhì)數(shù)能降低碰撞概率而且現(xiàn)代CPU對(duì)n*31可以用(n5)-n的位運(yùn)算優(yōu)化速度快。第二capacity 的選擇有講究。如果數(shù)組長度是 2 的冪取模運(yùn)算hash % capacity可以等價(jià)替換成hash (capacity - 1)位運(yùn)算會(huì)比除法快不少。Java HashMap 就是這么干的默認(rèn)容量 16擴(kuò)容時(shí)翻倍始終保持 2 的冪。但這么做有一個(gè)副作用——低位的分布直接決定了哈希質(zhì)量所以 Java HashMap 在計(jì)算下標(biāo)前還會(huì)對(duì) hash 值做一次“擾動(dòng)”處理把高位的隨機(jī)性擴(kuò)散到低位。第三沖突處理方案要在“時(shí)間”和“空間”之間權(quán)衡。主流有兩種鏈地址法數(shù)組的每個(gè)格子不是存一個(gè)元素而是掛一條鏈表。沖突的元素直接掛在同一個(gè)鏈表后面。Java HashMap、C unordered_map 都是這種思路。開放尋址法某個(gè)下標(biāo)被占了就按某種探測規(guī)則去找下一個(gè)空位。Python 的 dict 底層用的就是開放尋址法配合隨機(jī)探測的序列。我個(gè)人的體會(huì)是鏈地址法實(shí)現(xiàn)簡單、刪除方便但鏈表太長后查詢會(huì)退化開放尋址法對(duì)緩存更友好、內(nèi)存緊湊但刪除操作處理起來很麻煩裝得太滿時(shí)性能會(huì)急轉(zhuǎn)直下。這也是為什么 Python dict 雖然“內(nèi)存占用大”但實(shí)際查詢非常快的原因之一。2. 哈希表和字典到底是什么關(guān)系2.1 從“字典”這個(gè)詞說起抽象與實(shí)現(xiàn)的區(qū)別“哈希表”和“字典”的區(qū)別是我這次復(fù)習(xí)最先想通的點(diǎn)也是很多人面試時(shí)被問懵的地方。先明確一個(gè)概念字典Dictionary/Map是一種抽象數(shù)據(jù)類型ADT。它定義的是“能做什么”——提供 key 到 value 的映射支持 put、get、delete 這幾類操作。至于內(nèi)部用數(shù)組還是樹字典本身并不關(guān)心。哈希表則是一種具體的數(shù)據(jù)結(jié)構(gòu)。它用數(shù)組 哈希函數(shù)來實(shí)現(xiàn)“根據(jù) key 定位”的機(jī)制。也就是說哈希表是“字典”眾多實(shí)現(xiàn)方式中的一種而且是目前最主流、性能最好的一種。用一個(gè)類比你想實(shí)現(xiàn)“按姓名查電話號(hào)碼”的功能這是字典的需求你決定用一本按姓氏拼音排序的通訊錄來實(shí)現(xiàn)這本通訊錄就是哈希表。需求層和實(shí)現(xiàn)層不在同一個(gè)維度。為什么不把所有字典都用哈希表實(shí)現(xiàn)因?yàn)楣１碛幸粋€(gè)明顯短板它天生無序。如果你還需要按 key 排序遍歷哈希表就無能為力了這時(shí)可以選擇紅黑樹比如 Java TreeMap、C std::map或者跳表。2.2 不同語言里的實(shí)現(xiàn)差異對(duì)比當(dāng)你翻開各種語言的源碼能看到一件很有趣的事同樣是“字典”這個(gè)抽象概念底層選型完全不同。為此我整理了一張對(duì)比表。語言/庫名稱底層實(shí)現(xiàn)沖突處理key是否有序線程安全JavaHashMap哈希表鏈地址法 鏈表轉(zhuǎn)紅黑樹否否JavaHashtable哈希表鏈地址法否是全方法加鎖性能差JavaTreeMap紅黑樹無是否Pythondict哈希表開放尋址法是3.7 保序否受GIL保護(hù)Cstd::unordered_map哈希表鏈地址法否否Cstd::map紅黑樹無是否Gomap哈希表桶 溢出桶否否這張表給我最大的沖擊是Python 的 dict 在 3.7 之后居然保持了插入順序同時(shí)底層還是哈希表。之前我一直以為 Python dict 的“有序”是用了什么額外結(jié)構(gòu)后來查源碼才知道它是在原來的稀疏數(shù)組之外加了一個(gè)緊湊的索引表讓遍歷時(shí)能按插入順序讀取。這說明“哈希表無序”不是一條鐵律關(guān)鍵還得看怎么設(shè)計(jì)內(nèi)部布局。2.3 面試和項(xiàng)目里怎么回答它們的區(qū)別如果你在面試中被問到“哈希表和字典的區(qū)別”我總結(jié)了一套穩(wěn)的回答框架分三層。第一層定義本質(zhì)。字典是存儲(chǔ)鍵值對(duì)映射的抽象數(shù)據(jù)結(jié)構(gòu)哈希表是實(shí)現(xiàn)這一抽象的一種具體底層結(jié)構(gòu)基于數(shù)組和哈希函數(shù)提供 O(1) 的插入、查詢、刪除。第二層語言命名。Python 里把“用哈希表實(shí)現(xiàn)的字典”直接叫做 dictJava 里有 HashMap、Hashtable、ConcurrentHashMap 之分C 里 unordered_map 才是哈希表而 map 是有序紅黑樹?？吹秸Z言命名差異就要意識(shí)到“字典”和“哈希表”不是等價(jià)關(guān)系。第三層能力邊界。哈希能解決無序鍵值映射問題有序需求就得換樹或跳表哈希表還能用于去重、集合、緩存、布隆過濾器等場景這些都不叫“字典”。如果在項(xiàng)目里做技術(shù)選型我會(huì)再加一層需要線程安全的時(shí)候Java 選 ConcurrentHashMap需要按 key 范圍查詢時(shí)選 TreeMap內(nèi)存要求苛刻而讀多寫少時(shí)可以考慮開放尋址式的自定義哈希表。選型前先把“字典”這個(gè)需求拆開看你才知道底層該用什么。3. 把原理落到代碼手寫一個(gè)可用的哈希表3.1 基礎(chǔ)版鏈地址法的完整實(shí)現(xiàn)要把哈希表真正吃透光看別人的代碼是不夠的。我自己的經(jīng)驗(yàn)是手寫一遍比看十遍源碼都有效。下面是我在復(fù)習(xí)第6天寫出來的一個(gè)可運(yùn)行的簡化版哈希表用 Python 實(shí)現(xiàn)基于鏈地址法。class SimpleHashMap: def __init__(self, capacity16): self.capacity capacity self.buckets [[] for _ in range(capacity)] self.size 0 self.threshold int(capacity * 0.75) def _hash(self, key): # 參考 Java String 的哈希思路result result * 31 char total 0 for ch in str(key): total (total * 31 ord(ch)) % self.capacity return total def put(self, key, value): idx self._hash(key) bucket self.buckets[idx] for i, (k, v) in enumerate(bucket): if k key: bucket[i] (key, value) return bucket.append((key, value)) self.size 1 if self.size self.threshold: self._resize(self.capacity * 2) def get(self, key): idx self._hash(key) for k, v in self.buckets[idx]: if k key: return v raise KeyError(key) def delete(self, key): idx self._hash(key) bucket self.buckets[idx] for i, (k, v) in enumerate(bucket): if k key: del bucket[i] self.size - 1 return raise KeyError(key)這段代碼看起來不長但真實(shí)的哈希表核心要素都在里面了。我逐個(gè)解釋一下幾個(gè)容易忽略的點(diǎn)。_hash方法里的取模有兩個(gè)作用一是把任意大的整數(shù)壓縮到一個(gè)合法下標(biāo)二是讓哈希值始終落在[0, capacity-1]內(nèi)。注意我是在循環(huán)內(nèi)就取了模而不是算完總和再取模這是為了避免總和過大導(dǎo)致性能浪費(fèi)同時(shí)也讓中間結(jié)果的增長可控。put的時(shí)候先遍歷目標(biāo)鏈表的每個(gè)元素。如果 key 已經(jīng)存在說明這是“更新”操作直接替換值只有 key 不存在時(shí)才追加新節(jié)點(diǎn)。這個(gè)細(xì)節(jié)如果漏掉同一個(gè) key 就會(huì)出現(xiàn)兩份記錄取的時(shí)候永遠(yuǎn)拿到舊的。get和delete的邏輯結(jié)構(gòu)完全對(duì)稱先算下標(biāo)、再遍歷鏈表、找到就處理、找不到就拋異常。寫下這三個(gè)方法之后你會(huì)非常直觀地理解哈希表最壞情況什么時(shí)候出現(xiàn)——當(dāng)所有 key 都撞到同一個(gè) bucket 時(shí)遍歷鏈表就和遍歷數(shù)組沒什么區(qū)別O(1) 秒變 O(n)。3.2 加入擴(kuò)容與重新哈希負(fù)載因子的作用上面代碼里我留了一個(gè)_resize方法沒展開這是哈希表的另一條命脈擴(kuò)容。為什么需要擴(kuò)容數(shù)組容量固定了而放入的數(shù)據(jù)越來越多時(shí)每個(gè) bucket 掛的鏈表會(huì)越來越長查詢性能必然下降。這時(shí)候就需要給數(shù)組“變寬”讓鏈表重新攤開。觸發(fā)時(shí)機(jī)用“負(fù)載因子”來控制也就是size / capacity。當(dāng)這個(gè)比值超過某個(gè)閾值大概 0.75 左右就該擴(kuò)容了。0.75 不是拍腦袋定的數(shù)字。太小的負(fù)載因子意味著數(shù)組很大很空浪費(fèi)內(nèi)存太大了意味著鏈表過長性能退化。Java HashMap 把默認(rèn)負(fù)載因子設(shè)成 0.75是一個(gè)在時(shí)間和空間上公認(rèn)比較均衡的經(jīng)驗(yàn)值。我的代碼里threshold int(capacity * 0.75)就是把這個(gè)閾值直接算好避免每次 put 都做一次除法。擴(kuò)容動(dòng)作本身不復(fù)雜但有一個(gè)極其關(guān)鍵的點(diǎn)擴(kuò)容后每個(gè) key 重新計(jì)算出來的下標(biāo)可能會(huì)變。因?yàn)槿∧＿\(yùn)算的分母 capacity 變了。舉個(gè)簡單例子capacity 從 16 變成 32原來hash % 16 5的元素現(xiàn)在hash % 32可能是 5也可能是 21。所以擴(kuò)容不是簡單地把舊數(shù)組元素“搬”到更大的數(shù)組里而是必須逐個(gè)重新哈希、重新插入。下面是我測試時(shí)用的_resize實(shí)現(xiàn)def _resize(self, new_capacity): old_buckets self.buckets self.capacity new_capacity self.buckets [[] for _ in range(new_capacity)] self.threshold int(new_capacity * 0.75) for bucket in old_buckets: for k, v in bucket: idx self._hash(k) self.buckets[idx].append((k, v))這里有個(gè)我踩過的坑擴(kuò)容后size不用動(dòng)因?yàn)樵乜倲?shù)沒有變化。但由于_hash依賴self.capacity而它在_resize里已經(jīng)被更新成了新值所以重新調(diào)用_hash(k)時(shí)用的就是新的模數(shù)計(jì)算出來的下標(biāo)自然屬于新數(shù)組。順序千萬不能反如果先遍歷舊桶再改 capacity那算出來還是舊下標(biāo)插入新數(shù)組就全亂了。3.3 手寫過程中最容易犯的錯(cuò)這一節(jié)我單獨(dú)拎出來寫是因?yàn)檫@幾個(gè)錯(cuò)我都真實(shí)犯過而且不看測試結(jié)果根本發(fā)現(xiàn)不了。第一個(gè)錯(cuò)誤是忘記處理“同 key 更新”的分支。往哈希表里重復(fù) put 同一個(gè) key結(jié)果新增了兩條記錄get 永遠(yuǎn)拿到最早那條。這種情況在測試時(shí)很容易漏掉因?yàn)榇蟛糠譁y試只會(huì) put 不同 key。第二個(gè)錯(cuò)誤是刪除后沒有把鏈表節(jié)點(diǎn)正確移除。用del bucket[i]是安全的但如果你在遍歷的同時(shí)執(zhí)行刪除很容易因?yàn)橄聵?biāo)錯(cuò)位跳過元素或者拋出越界異常。建議先記錄目標(biāo)下標(biāo)遍歷結(jié)束后再統(tǒng)一刪除。第三個(gè)錯(cuò)誤是擴(kuò)容時(shí)沒有遷移干凈。如果直接self.buckets ...而忘了遍歷舊數(shù)組那么擴(kuò)容后所有數(shù)據(jù)直接丟失而且因?yàn)閟ize還停留在舊值整個(gè)表就報(bào)廢了。我建議手寫測試時(shí)打印size、capacity、每個(gè)桶的長度一步一步對(duì)著看。手寫完后我強(qiáng)烈建議再寫一個(gè)最基礎(chǔ)的冒煙測試連續(xù) put 500 個(gè)隨機(jī)鍵值對(duì)再隨機(jī) get 500 次最后 delete 一半再驗(yàn)證剩余數(shù)據(jù)是否完整。這套流程跑通才能說真正理解了哈希表的基本機(jī)制。4. 刷題視角哈希表的三種高頻用法4.1 頻次統(tǒng)計(jì)與“找重復(fù)/找唯一”既然這一篇刷題計(jì)劃里叫“第6天 哈希表2”那當(dāng)然繞不開用哈希表解算法題。我自己的經(jīng)驗(yàn)是哈希表在刷題里其實(shí)就三個(gè)大方向掌握了這三板斧大部分相關(guān)題目都能用上。第一板斧是統(tǒng)計(jì)頻次或者判斷重復(fù)。這類題的核心套路是把遍歷過的元素作為 key 存進(jìn)哈希表value 存出現(xiàn)的次數(shù)或者第一次出現(xiàn)的下標(biāo)。比如經(jīng)典的“兩數(shù)之和”遍歷數(shù)組時(shí)對(duì)當(dāng)前元素x檢查target - x是否已經(jīng)在哈希表里如果在就直接返回答案。這種做法把原本暴力兩重循環(huán)的 O(n2) 降到了 O(n)代價(jià)僅是額外 O(n) 空間。還有一個(gè)常見的變體是“找到出現(xiàn)次數(shù)最多的元素”或“判斷一個(gè)字符串是否能重排成回文串”?；匚拇穷愵}只要統(tǒng)計(jì)每個(gè)字符出現(xiàn)次數(shù)然后數(shù)一數(shù)有多少個(gè)奇數(shù)次字符最多允許一個(gè)奇數(shù)。這種題用哈希表的 key 存字符、value 存頻次代碼寫起來非常順手。我在刷這類題時(shí)總結(jié)出一個(gè)小經(jīng)驗(yàn)?zāi)苡脭?shù)組做“偽哈希表”的優(yōu)先用數(shù)組。如果 key 的范圍是確定的整數(shù)比如 ASCII 碼、26 個(gè)小寫字母直接用長度為 26 或 128 的數(shù)組當(dāng)下標(biāo)表效率比真正的 HashMap 更高還省去了哈希函數(shù)計(jì)算。這也是為什么很多字符串題用“int[26]”而不是 HashMap 的原因。4.2 用哈希表構(gòu)建 O(1) 查詢的緩存結(jié)構(gòu)第二板斧哈希表 雙向鏈表實(shí)現(xiàn) LRU 緩存。這是面試?yán)锓浅劭嫉囊坏澜?jīng)典題也是哈希表在實(shí)際工程中的高價(jià)值應(yīng)用。設(shè)計(jì)思路是需要快速判斷某個(gè) key 是否存在并且能 O(1) 拿到 value這交給哈希表需要維護(hù)數(shù)據(jù)的熱度順序淘汰最久沒用的數(shù)據(jù)這交給雙向鏈表。哈希表的 value 里存的是雙向鏈表的節(jié)點(diǎn)引用而不是單純的值。訪問某個(gè) key 時(shí)先把對(duì)應(yīng)節(jié)點(diǎn)從鏈表原位置摘下來再移到鏈表頭部如果緩存滿了就刪掉鏈表尾部的節(jié)點(diǎn)同時(shí)把這個(gè) key 從哈希表里刪掉。核心要點(diǎn)是哈希表和鏈表必須同步更新。光改鏈表不改哈希表會(huì)留下“幽靈 key”光改哈希表不改鏈表鏈表會(huì)出現(xiàn)懸空引用。我在練這題時(shí)寫了不止三遍每次都會(huì)在某一個(gè)小分支上翻車比如更新已存在的 key 時(shí)忘記調(diào)整節(jié)點(diǎn)位置或者刪除尾部節(jié)點(diǎn)后忘記從哈希表移除對(duì)應(yīng) key。這種組合結(jié)構(gòu)的思維方式比題目本身更值得學(xué)哈希表給人的是“快速定位能力”鏈表給人是“順序維護(hù)能力”兩種一拼很多復(fù)雜需求就能拆解成獨(dú)立的小問題。除了 LRU像 O(1) 的插入/刪除/獲取隨機(jī)元素也是類似套路——哈希表存下標(biāo)動(dòng)態(tài)數(shù)組存值。4.3 分組與狀態(tài)映射“同特征”聚合第三板斧用哈希表把“具備同一特征”的元素分到同一組。典型的題目是“字母異位詞分組”給定一組字符串把字母組成相同但順序不同的詞歸為一類。常規(guī)解法是對(duì)每個(gè)單詞的字符排序排序后的結(jié)果作為 key原單詞作為 value 加入同一個(gè)列表。比如 “eat” 排序后是 “aet”“tea” 排序后也是 “aet”它們就分到同一組。這里哈希表的 key 就是“特征簽名”value 是“擁有該特征的元素集合”。另一個(gè)思路是把 key 設(shè)計(jì)成“每個(gè)字母出現(xiàn)次數(shù)”的多維數(shù)組簽名比如 “eat” 對(duì)應(yīng)的簽名是a:1, e:1, t:1。把簽名編碼成字符串a(chǎn)1e1t1作為 key效果和排序一樣但避免了每次 O(k log k) 的排序開銷。如果是超長字符串這種計(jì)數(shù)簽名的方式往往更快。狀態(tài)映射這類題還可以延展到圖論里的“并查集簡化”“連通分量統(tǒng)計(jì)”等場景。講到根上哈希表承擔(dān)的角色從來都是同一個(gè)把復(fù)雜的、不可比較的特征轉(zhuǎn)化成一個(gè)可比較的、可靠的 key。一旦你習(xí)慣了這種思維方式看到“分組”“歸類”“狀態(tài)記錄”這些關(guān)鍵詞第一反應(yīng)就是能不能用一個(gè)哈希表來落地。5. 實(shí)戰(zhàn)踩坑記錄哈希表的五個(gè)經(jīng)典問題5.1 哈希沖突引起的性能雪崩第一個(gè)坑也是最隱蔽的坑哈希沖突多到一定程度哈希表平均查詢時(shí)間會(huì)從 O(1) 退化到 O(n)。我自己在項(xiàng)目里就遇到過一個(gè)接口平時(shí) 2 毫秒返回某天突然變成 2 秒。排查過程很有意思先看數(shù)據(jù)庫沒慢查詢?cè)倏聪掠畏?wù)也正常最后抓了個(gè) heap dump 才發(fā)現(xiàn)一個(gè) HashMap 里上百萬數(shù)據(jù)全掛在同一個(gè) bucket 下面。原因是業(yè)務(wù) key 是某個(gè)字符串拼接出來的而拼接的那個(gè)底層字段取值只有十幾種再加上這個(gè)字符串哈希值恰好有規(guī)律一取模全撞一起了。遇到這種情況處理手段有幾個(gè)方向換一個(gè)更“散”的哈希種子。Java 的String.hashCode()是固定的但很多哈希表實(shí)現(xiàn)支持自定義哈希函數(shù)或通過隨機(jī)種子打散。把 key 本身改造一下比如拼一個(gè)隨機(jī)因子或者把多個(gè)字段組合成更復(fù)雜的簽名。調(diào)整初始容量和負(fù)載因子減少擴(kuò)容頻率同時(shí)讓桶數(shù)量更大降低碰撞概率。這事的教訓(xùn)是哈希函數(shù)是否均勻必須結(jié)合真實(shí)業(yè)務(wù)數(shù)據(jù)的分布去看。光看算法理論上的均勻沒用線上數(shù)據(jù)往往有自己的偏好說不準(zhǔn)哪個(gè)取值就會(huì)瘋狂集中。5.2 自定義對(duì)象當(dāng) key結(jié)果 get 不到值第二個(gè)坑是關(guān)于 Java 自定義對(duì)象作為 key 時(shí)hashCode()和equals()必須配套實(shí)現(xiàn)。很多人寫了個(gè)類沒重寫 hashCode直接當(dāng)成 HashMap 的 key 塞進(jìn)去結(jié)果存的時(shí)候用的是對(duì)象默認(rèn)地址計(jì)算的哈希取的時(shí)候構(gòu)造了一個(gè)“內(nèi)容相同”的新對(duì)象地址不同哈希不同get 直接返回 null。解決方案是重寫時(shí)遵守三條規(guī)則兩個(gè)對(duì)象 equals 相等則 hashCode 必須相等。hashCode 相等equals 不一定相等這是允許的。重寫 equals 時(shí)必須同時(shí)重寫 hashCode。我還會(huì)在寫完自定義 key 后專門寫個(gè)單元測試故意構(gòu)造兩個(gè)內(nèi)容相同的對(duì)象分別執(zhí)行put和get確保能正常取回。這類問題看起來低級(jí)但實(shí)際踩坑率非常高特別是剛從其他語言轉(zhuǎn)過來的同事。Python 里也有類似的坑。自定義類如果不定義__hash__和__eq__默認(rèn)用對(duì)象身份做哈希如果只定義了__eq__Python 會(huì)直接把__hash__置為 None這個(gè)對(duì)象就沒法放進(jìn) set 或 dict 了。正確做法是同時(shí)定義兩者且保證相等的對(duì)象哈希值一致。5.3 可變對(duì)象做 key改完立刻“失靈”第三個(gè)坑進(jìn)階一些把可變對(duì)象當(dāng)作 key存進(jìn)去之后修改了對(duì)象內(nèi)容。Java 中如果你把 key 對(duì)象的某個(gè)字段改了而 hashCode 依賴這個(gè)字段那么哈希表里存儲(chǔ)時(shí)的位置和現(xiàn)在計(jì)算出來的位置就對(duì)應(yīng)不上了這個(gè)對(duì)象會(huì)“憑空消失”——表還存著舊位置但你已經(jīng)永遠(yuǎn)算不出它的坐標(biāo)。Python 也有同樣問題。list不能當(dāng) dict 的 key 就是因?yàn)樗勺僼uple可以當(dāng) key是因?yàn)樗豢勺?。工程上我的建議很簡單優(yōu)先用不可變類型做 key比如 Java 的 String、IntegerPython 的 str、tuple。如果必須用可變對(duì)象約定“存進(jìn)去之后絕不允許修改”并把這條寫進(jìn)代碼注釋。實(shí)在要改就走“先刪除舊的再插入新的”流程。這條規(guī)則我是在一次搞砸了內(nèi)存緩存之后記住的。當(dāng)時(shí)緩存了一批配置對(duì)象后來業(yè)務(wù)上更新了配置內(nèi)容直接改了對(duì)象的字段結(jié)果緩存命中率掉到幾乎為零排查半天才發(fā)現(xiàn)是 key 的 hashCode 變了。5.4 并發(fā)場景下的使用禁忌第四個(gè)坑是關(guān)于線程安全。Java 的 HashMap 不是線程安全的多線程并發(fā) put 時(shí)JDK 7 時(shí)代甚至可能在擴(kuò)容時(shí)形成循環(huán)鏈表導(dǎo)致下次查詢時(shí)死循環(huán)、CPU 飆滿。JDK 8 改成尾插法后循環(huán)鏈表的問題緩解了但并發(fā) put 仍然可能丟數(shù)據(jù)或者讀到臟值。處理并發(fā)場景我的建議是按嚴(yán)重程度分級(jí)低讀低寫直接加Collections.synchronizedMap簡單粗暴。高并發(fā)讀、寫也多用ConcurrentHashMap它把鎖粒度細(xì)化到桶性能好得多。緩存語義優(yōu)先考慮Caffeine這類專門做本地緩存的類庫而不是自己拿 HashMap 硬做。Python 并發(fā)dict 本身有 GIL 保護(hù)單個(gè)操作但“先檢查再更新”的組合操作不是原子的需要加鎖或使用專門的同步容器。Go 的 map 更需要提高警惕多個(gè) goroutine 同時(shí)讀寫同一個(gè) map 會(huì)直接拋出fatal error: concurrent map writes。官方推薦的并發(fā)同步方案是sync.Mutex或sync.RWMutex如果讀多寫少用sync.Map在某些場景下效果更好。5.5 常見問題速查表最后把這兩天復(fù)習(xí)中遇到最多的問題整理成一張表方便你直接對(duì)照排查?，F(xiàn)象可能原因排查方式解決方案get 返回錯(cuò)誤順序的數(shù)據(jù)key 的 equals/hashCode 未正確實(shí)現(xiàn)打印 hashCode 對(duì)比重寫 hashCode 和 equalskey 存進(jìn)去后查不到可變對(duì)象 key 被修改檢查 key 對(duì)象字段是否變動(dòng)改用不可變 key或先刪后插哈希表查詢突然變慢哈希沖突過多、桶鏈表過長統(tǒng)計(jì)各 bucket 長度分布換哈希函數(shù)、加大容量并發(fā)寫入報(bào)錯(cuò)或丟數(shù)據(jù)線程不安全容器被多線程使用檢查并發(fā)訪問路徑使用 ConcurrentHashMap / 加鎖內(nèi)存占用過高容量開太大、負(fù)載因子設(shè)置不當(dāng)打印 capacity 和 size調(diào)整初始容量與負(fù)載因子這里還有一條很實(shí)用的心得當(dāng)你懷疑哈希表出問題時(shí)不要憑感覺猜寫一段小腳本或者測試代碼把capacity、size、每個(gè)桶的鏈表長度分布都打印出來。數(shù)據(jù)一出來問題基本就定位了。最后說幾句實(shí)操體會(huì)把這幾天手寫哈希表、刷題、排查線上問題的經(jīng)歷串在一起我最大的感受是哈希表這個(gè)結(jié)構(gòu)看起來只有幾行代碼但它牽扯出來的細(xì)節(jié)能寫滿一整篇博文。哈希函數(shù)怎么選、沖突怎么處理、擴(kuò)容為什么必須重新哈希、key 的設(shè)計(jì)規(guī)范、并發(fā)場景的選型每一個(gè)點(diǎn)都是真實(shí)項(xiàng)目里踩過坑才能記住的。如果你也在學(xué)這一塊我真心建議別停留在“會(huì)用 HashMap”這個(gè)層面。找一天時(shí)間把手寫哈希表、手寫 LRU、再刷幾道用哈希表分組的題走一遍第二天再看源碼你會(huì)發(fā)現(xiàn)自己突然能看懂那些注釋里為什么反復(fù)強(qiáng)調(diào) equals 和 hashCode 的一致性了。今天關(guān)于哈希表的記錄就到這里。接下來我計(jì)劃直接把“第7天”的內(nèi)容定成哈希表的應(yīng)用強(qiáng)化把字符串處理、滑動(dòng)窗口、前綴和這些容易和哈希表配合的題型系統(tǒng)地過一遍到時(shí)候再把新的經(jīng)驗(yàn)整理出來分享。