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