化)
給新手講清楚HashMapJava入門階段的很多事情一下子就能通。這個數(shù)據(jù)結(jié)構(gòu)核心就一句話通過key找到value。登錄系統(tǒng)里拿用戶ID查用戶信息、訂單統(tǒng)計里按日期聚合金額、緩存場景里用請求URL換響應結(jié)果背后全是同一套邏輯——給一個key立刻得到對應的value。偏偏很多人項目里用了很久HashMap一問為什么必須重寫equals和hashCode、為什么容量默認16還必須是2的冪、為什么有時候?qū)懭霂资f條數(shù)據(jù)就卡頓就答不上來了。這篇文章就把這條從key到value的完整鏈路徹底掰開順便把源碼、性能坑、排查方法一次說清。適合誰看正在啃集合源碼的初學者、準備面試的人以及寫代碼時覺得HashMap“時而快時而慢”但說不清原因的開發(fā)者。我會把幾個關鍵概念用廚房、圖書館這種生活場景做類比再配一套可直接落地的操作建議。1. 先從“key找value”這個需求說起1.1 數(shù)組的尷尬和鏈表的慢假設你現(xiàn)在要做一個用戶系統(tǒng)用戶數(shù)據(jù)有ID、姓名、手機號。最常見的需求是給我一個用戶ID把那行用戶信息取出來。如果數(shù)據(jù)用數(shù)組存你得知道ID對應的下標比如第0個格子里存ID1001的用戶第1個格子存ID1002的用戶那就只能強行為ID和下標建立映射關系業(yè)務里根本做不到——用戶ID是1001、1002這種連續(xù)值還好說一旦變成訂單號、手機號、短信驗證碼這種沒有規(guī)律、甚至可能重復的鍵數(shù)組下標立刻失效。有人會說那用鏈表不就行了。鏈表每個節(jié)點可以存兩部分key和value。查找的時候從頭節(jié)點開始逐個比較節(jié)點的key和你要找的key相等就返回value。這個方案靈活但代價是查找復雜度O(n)數(shù)據(jù)量到一萬條還能忍到百萬條就完全沒法用了。每次查找都得把鏈表從頭摸到尾最壞情況下要找滿全場。你真正需要的是一種結(jié)構(gòu)既不用關心下標又不用遍歷全場。這種需求就是哈希表要解決的。1.2 哈希思想的雛形算出一個位置來哈希表的想法其實很樸素。你去圖書館借書管理員不會帶你從第一排書架開始找而是先看索書號索書號本身就包含了分類體系走到對應分區(qū)順著編號一摸就拿到了。你去快遞驛站取件快遞員也不會把所有包裹拆開挨個翻他先按手機尾號分貨架再按包裹上的編號找。哈希表做的就是同一件事把任意一個key通過一個計算過程映射成數(shù)組里的某個下標。這個計算過程叫哈希函數(shù)算出來的值叫哈希值數(shù)組里的每個格子叫桶bucket。理論上只要哈希函數(shù)能把不同的key均勻散開每次查找就能直接定位到目標桶時間復雜度接近O(1)。那HashMap只不過是把這套思想在Java里實現(xiàn)了并且加了處理沖突、自動擴容的機制。所以理解HashMap核心就是理解兩件事key怎么變成一個桶下標以及多個key落到同一個桶時怎么辦。2. HashMap的桶位怎么來的hash()與下標定位2.1 hash()為什么要異或高16位先看JDK 8里HashMap計算哈希值的源碼static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }這里有兩個動作先調(diào)用key自身的hashCode()拿到一個int然后把高16位和低16位做異或得到的才是真正參與桶定位的hash值。為什么要折騰這一步因為后續(xù)定位桶的時候用的是數(shù)組長度減一和hash值做按位與。默認數(shù)組長度16對應的二進制是0000 0000 0000 1111按位與會把高28位全部清零只保留最低4位。如果兩個key的hashCode在高位有差異、低位完全相同那它們就會落到同一個桶這就是沖突。而且很多對象的hashCode恰恰在高位差異較大低位區(qū)分度不足。把高16位異或到低16位相當于讓高位的特征也參與低位的運算即使數(shù)組很短散列效果也會好很多。這一步在源碼注釋里叫“擾動函數(shù)”確實是經(jīng)過權(quán)衡后性價比很高的一步。2.2 為什么容量必須是2的冪以及取模優(yōu)化定位桶下標的核心代碼是這一行i (n - 1) hashn是數(shù)組長度。這里用按位與代替取模%原因是位運算比取?？斓枚?。但要成立前提是n必須是2的冪。當n16時n-115二進制是1111n32時n-131二進制是11111全都是低位連續(xù)的1這樣按位與的結(jié)果就等于hash對n取余而且效率更高。HashMap源碼在構(gòu)造時對容量做了一圈處理就是為了保證這一點。你傳入任何初始容量它都會向上補成2的冪static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }你傳3它變成4傳10變成16傳100變成128。這套移位運算把最高位后面的所有位全部填成1最后加個1就是最接近且大于等于原值的2的冪。還有一個好處。擴容時數(shù)組長度翻倍從16變成32原來長度16時下標只由hash低4位決定現(xiàn)在要由低5位決定。新增的那一位如果是0元素留在原地如果是1元素挪到“原下標16”的位置。因為2的冪特性擴容時不需要重新計算每個key的hash值只需要看新增比特位就夠了這也是JDK 8里resize能高效拆分鏈表的原因。2.3 沖突不可避免鏈化和樹化的閾值邏輯哈希函數(shù)設計得再好也不能保證每個key都算到不同桶沖突是必然的。HashMap解決沖突的辦法就是把多個沖突元素放到同一個桶里用鏈表串起來。JDK 8之前一直是這個方案簡單可靠但極端情況下所有key都落在同一個桶鏈表越來越長查找就退化成了O(n)。JDK 8改成了鏈表加紅黑樹的混合結(jié)構(gòu)同一個桶里節(jié)點數(shù)超過8并且整個數(shù)組長度大于等于64就會把鏈表轉(zhuǎn)成紅黑樹。紅黑樹查找復雜度O(log n)在一棵深度幾十的樹里找一個元素跟遍歷幾千個節(jié)點的鏈表是完全不同的量級。為什么閾值是8源碼注釋里給出過一個統(tǒng)計結(jié)論在隨機哈希碼的情況下桶內(nèi)節(jié)點數(shù)達到8的概率大約只有千萬分之六對絕大多數(shù)正常業(yè)務來說幾乎不可能觸發(fā)樹化。反而如果閾值設得太低比如2稍微有點沖突就樹化而樹節(jié)點的內(nèi)存占用是普通節(jié)點的兩倍左右性能反而下降。等紅黑樹節(jié)點數(shù)降到6以下又會變回鏈表這中間留了緩沖區(qū)間避免頻繁在兩種結(jié)構(gòu)之間來回切換。3. put和get的完整源碼鏈路3.1 put(key, value)時發(fā)生了什么JDK 8里put的入口很簡單但背后邏輯值得逐行看public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; int n; // 第一次put時整個表還是空的先擴容初始化 if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 算出桶下標如果槽位是空的直接放進新節(jié)點 int i (n - 1) hash; if ((p tab[i]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; // 桶里已有節(jié)點先比較hash再比較key if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; else if (p instanceof TreeNode) // 桶里已是紅黑樹走紅黑樹插入邏輯 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 桶里是鏈表遍歷找尾部插入如果中途遇到相同key記錄舊節(jié)點 for (int binCount 0; ; binCount) { if ((e p.next) null) { p.next newNode(hash, key, value, null); if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } // e不為空說明存在相同key覆蓋舊value并返回舊value if (e ! null) { V oldValue e.value; e.value value; return oldValue; } } modCount; // 元素數(shù)量超過閾值就擴容 if (size threshold) resize(); return null; }注意幾個細節(jié)。定位到桶以后如果桶里已經(jīng)有節(jié)點先比hash再比對key。比對key的時候用了兩層判斷第一層是引用判斷k key比如你用同一個String對象做key直接引用相等就命中第二層是key.equals(k)處理的是內(nèi)容相同但引用不同的情況比如兩次都傳入字符串1001它們不是同一個對象但equals相等。只有hash相同才有必要做equals比較hash不同就直接認定不是同一個key。這能夠大大減少equals的調(diào)用次數(shù)畢竟哈希定位已經(jīng)把絕大多數(shù)無關key擋在外面了。3.2 get(key)時為什么能精準命中get的鏈路和put高度對稱public V get(Object key) { NodeK,V e; return (e getNode(hash(key), key)) null ? null : e.value; } final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; // 表非空且目標桶位置有節(jié)點才可能找到 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 先檢查第一個節(jié)點 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 第一個節(jié)點沒命中看是樹還是鏈表 if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); // 鏈表逐個比較 do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }這個流程已經(jīng)清晰先通過hash(key)算出哈希值再用(n - 1) hash定位桶桶里節(jié)點碰運氣直接命中命不中就在鏈表或紅黑樹里繼續(xù)比較。之所以說HashMap查詢是“近似O(1)”就是因為大多數(shù)情況下桶里是空的或者只有一兩個節(jié)點一次定位加一兩次比較就出結(jié)果只有沖突嚴重時才會走到后面的鏈表或樹遍歷。3.3 equals和hashCode的契約為什么是命中的前提如果你只重寫equals但不同時重寫hashCode會出大問題。假設你有一個訂單類Orderequals比較的是orderNo但hashCode還是Object的默認實現(xiàn)——基于對象內(nèi)存地址。兩個orderNo完全一樣的訂單對象equals返回true但hashCode不同。第一次put進去用的是對象A第二次get時傳入對象BB的hash值跟A不同桶下標直接不一樣連目標桶都找不到equals根本沒機會執(zhí)行。這就是哈希表最核心的契約equals相等的兩個對象hashCode必須相等。反過來hashCode相等不等于equals相等這是允許的這正是哈希沖突。兩個不同key算到同一個桶最終靠equals來區(qū)分誰是誰。所以正確做法是參與equals比較的字段必須同時參與hashCode計算反之如果hashCode用了某個字段equals也最好用上否則可能出現(xiàn)兩個對象hashCode相同但業(yè)務上含義不同put時被當成同一個key覆蓋的情況。后面第4部分我會給完整示例。4. 實際開發(fā)中容易踩的三個性能坑4.1 初始容量與加載因子的正確姿勢HashMap的默認容量是16加載因子是0.75。加載因子的含義是當元素數(shù)量超過容量 × 0.75時觸發(fā)resize擴容。也就是說默認情況下存到第12個元素HashMap就會擴容到32容量翻倍。很多人不關心這個導致寫入數(shù)據(jù)量大時反復擴容。我實測過往默認HashMap里塞100條數(shù)據(jù)會觸發(fā)至少4次resize每次resize都要重新分配數(shù)組、重新計算所有已有節(jié)點的桶下標、移動節(jié)點。1億條級別的數(shù)據(jù)光是擴容的rehash成本就非?？捎^。正確的初始化方式是按預計數(shù)據(jù)量反推。如果你預計要放100條數(shù)據(jù)int expectedSize 100; MapString, Object map new HashMap((int) (expectedSize / 0.75f) 1);計算下來初始容量設置成134HashMap會自動向上取整為256閾值變成256×0.75192遠超100整個過程不會觸發(fā)擴容。如果直接寫new HashMap(100)容量會向上取成128閾值是96存到第96個元素時還是得擴容一次等于白打算。加載因子0.75是JDK團隊在時間成本和空間成本里取的平衡點。調(diào)小到0.5桶更空、沖突更少、查詢更快但內(nèi)存浪費嚴重調(diào)大到1.0空間利用率高但碰撞概率上升鏈表變長查詢變慢。普通業(yè)務場景不要動這個值真要調(diào)先壓測再調(diào)。4.2 自定義對象當keyequals和hashCode怎么配開發(fā)中最容易出問題的場景是把自定義對象塞進HashMap當key比如訂單、賬號、設備信息。先看一個會翻車的寫法class Order { private String orderNo; private BigDecimal amount; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Order order (Order) o; return Objects.equals(orderNo, order.orderNo); } // 忘記重寫 hashCode }兩個orderNo相同的Order對象equals返回true但hashCode還是默認的地址哈希意味著同一筆訂單兩個不同的對象實例放進Map會被當成兩個key。get的時候傳入另一個同orderNo的對象hash定位直接落到另一個桶結(jié)果永遠是null。排查了半天最后根源就是hashCode沒重寫。正確的版本是這樣class Order { private final String orderNo; private BigDecimal amount; public Order(String orderNo) { this.orderNo orderNo; } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Order order (Order) o; return Objects.equals(orderNo, order.orderNo); } Override public int hashCode() { return Objects.hash(orderNo); } }equals只用orderNo比較hashCode也只由orderNo計算契約一致性滿足。還有一個進階要求key對象盡量不可變。如果你把key放進Map之后又修改了某個參與hashCode計算的字段這個key的hash值就變了再調(diào)用get時按新hash值定位到另一個桶舊桶里的數(shù)據(jù)就永遠找不到了等于內(nèi)存里多了一份永遠不會被訪問的孤兒節(jié)點。String、Integer這類包裝類天生不可變所以是最常用的key類型。自定義類做key時核心字段建議設成final去掉setter從根本上杜絕這個問題。4.3 并發(fā)場景別拿HashMap硬扛HashMap不是線程安全的。多線程同時put時兩個線程可能在同一桶位置寫入后寫的覆蓋先寫的更麻煩的是擴容階段多線程同時觸發(fā)resizeJDK 7里甚至可能形成循環(huán)鏈表get的時候直接死循環(huán)這是當年的經(jīng)典線上事故。JDK 8改成尾插法循環(huán)鏈表問題基本被解決但數(shù)據(jù)丟失、覆蓋問題依然存在因為HashMap的內(nèi)部操作沒有同步機制。并發(fā)場景的正確選擇是ConcurrentHashMap。JDK 8的ConcurrentHashMap放棄了分段鎖改用CAS加synchronized鎖單個桶節(jié)點鎖粒度更細并發(fā)讀的時候基本無鎖寫入時只鎖住目標桶性能遠好于給整個HashMap加synchronized。如果只是低并發(fā)的場景讀多寫少也可以用Collections.synchronizedMap(new HashMap())但這是整表鎖寫操作串行高并發(fā)下吞吐量上不去。記住一個原則共享可變Map要么用ConcurrentHashMap要么不要共享。5. 常見問題排查速查5.1 高頻問題對照表現(xiàn)象可能原因排查方法解決方案查詢越來越慢自定義key的hashCode寫得差大量key落同一桶打印桶內(nèi)節(jié)點數(shù)分布看是否有超長鏈表重寫hashCode讓更多字段參與計算同一對象get不到值只重寫equals沒重寫hashCode或key可變檢查key的equals和hashCode實現(xiàn)的一致性檢查key是否put后被修改遵守契約key字段設final修改后重新放入Map寫入量大時明顯卡頓頻繁擴容rehash成本高看日志中resize觸發(fā)次數(shù)或計算閾值與數(shù)據(jù)量的關系構(gòu)造時用expectedSize / 0.75f 1設置初始容量多線程寫入丟數(shù)據(jù)HashMap并發(fā)不安全高并發(fā)壓測觀察數(shù)據(jù)丟失換成ConcurrentHashMap遍歷結(jié)果順序不穩(wěn)定HashMap本身不保證順序換用LinkedHashMap按寫入順序遍歷用LinkedHashMap按key排序用TreeMapput一個null鍵允許null key放在桶下標0這是設計行為業(yè)務上自行區(qū)分null和空字符串Map內(nèi)存只增不減key被外部引用無法回收檢查key生存周期必要時用WeakHashMap或手動remove5.2 一個快速查看哈希分布的小工具排查自定義對象哈希質(zhì)量的時候我經(jīng)常寫一小段代碼打印桶分布直觀看到?jīng)_突是否嚴重public static void printBucketStats(MapObject, Object map) { try { java.lang.reflect.Field field HashMap.class.getDeclaredField(table); field.setAccessible(true); Object[] table (Object[]) field.get(map); if (table null) { System.out.println(table is empty); return; } int total 0; int maxBin 0; int emptyBin 0; for (Object node : table) { int count 0; Object p node; while (p ! null) { count; p ((java.lang.reflect.Field) p.getClass().getDeclaredField(next)).get(p); } if (count 0) emptyBin; maxBin Math.max(maxBin, count); total count; } System.out.printf(table length%d, total nodes%d, empty bins%d, max bin%d%n, table.length, total, emptyBin, maxBin); } catch (Exception ignored) { // 反射失敗時直接放棄 } }這段代碼用反射拿到HashMap內(nèi)部的table數(shù)組統(tǒng)計每個桶的節(jié)點數(shù)量。如果空桶占比很高、某個桶節(jié)點數(shù)特別多反過來說明hashCode分布不夠均勻。正常業(yè)務數(shù)據(jù)下最大的桶節(jié)點數(shù)應該是個位數(shù)如果出現(xiàn)幾十個節(jié)點的長鏈就得回頭查key的hashCode實現(xiàn)了。我自己的排查經(jīng)驗是HashMap相關的詭異問題90%最后都歸結(jié)到key對象身上。要么equals和hashCode寫得不一致要么key是可變對象被改壞了要么hashCode分布太差導致桶傾斜。把這三條路排查完基本都能定位到根因。6. 再分享一點個人的使用體會文章最后分享一個我實際操作中的體會調(diào)試HashMap問題時不要一上來就懷疑源碼或者并發(fā)先把key的hashCode和equals擺到桌面上看一遍。這兩個方法加起來不到二十行卻是整個HashMap運轉(zhuǎn)的基石絕大多數(shù)“莫名找不到”“莫名覆蓋”的問題都從這里來。另外初始容量這個參數(shù)很多人覺得不設也沒關系量大了才知道代價。我在一個批量導入功能里往Map里灌了大概幾萬條數(shù)據(jù)最初沒設容量導入過程能明顯感覺到后半程變慢。后來按expectedSize / 0.75f 1初始化后耗時直接降了一截代碼只改了一行。這種性價比極高的優(yōu)化項目里多多益善。把從key到桶下標再到節(jié)點的這條鏈路琢磨透了再回頭看ConcurrentHashMap的分段鎖演進、TreeMap的紅黑樹結(jié)構(gòu)甚至是Redis里的哈希表實現(xiàn)都會覺得順理成章。數(shù)據(jù)結(jié)構(gòu)這種東西不怕不熟悉API就怕不理解那個“根據(jù)key找到value”的核心思想。 徹底講透HashMap：從哈希原理到源碼與性能優(yōu)化
給新手講清楚HashMapJava入門階段的很多事情一下子就能通。這個數(shù)據(jù)結(jié)構(gòu)核心就一句話通過key找到value。登錄系統(tǒng)里拿用戶ID查用戶信息、訂單統(tǒng)計里按日期聚合金額、緩存場景里用請求URL換響應結(jié)果背后全是同一套邏輯——給一個key立刻得到對應的value。偏偏很多人項目里用了很久HashMap一問為什么必須重寫equals和hashCode、為什么容量默認16還必須是2的冪、為什么有時候?qū)懭霂资f條數(shù)據(jù)就卡頓就答不上來了。這篇文章就把這條從key到value的完整鏈路徹底掰開順便把源碼、性能坑、排查方法一次說清。適合誰看正在啃集合源碼的初學者、準備面試的人以及寫代碼時覺得HashMap“時而快時而慢”但說不清原因的開發(fā)者。我會把幾個關鍵概念用廚房、圖書館這種生活場景做類比再配一套可直接落地的操作建議。1. 先從“key找value”這個需求說起1.1 數(shù)組的尷尬和鏈表的慢假設你現(xiàn)在要做一個用戶系統(tǒng)用戶數(shù)據(jù)有ID、姓名、手機號。最常見的需求是給我一個用戶ID把那行用戶信息取出來。如果數(shù)據(jù)用數(shù)組存你得知道ID對應的下標比如第0個格子里存ID1001的用戶第1個格子存ID1002的用戶那就只能強行為ID和下標建立映射關系業(yè)務里根本做不到——用戶ID是1001、1002這種連續(xù)值還好說一旦變成訂單號、手機號、短信驗證碼這種沒有規(guī)律、甚至可能重復的鍵數(shù)組下標立刻失效。有人會說那用鏈表不就行了。鏈表每個節(jié)點可以存兩部分key和value。查找的時候從頭節(jié)點開始逐個比較節(jié)點的key和你要找的key相等就返回value。這個方案靈活但代價是查找復雜度O(n)數(shù)據(jù)量到一萬條還能忍到百萬條就完全沒法用了。每次查找都得把鏈表從頭摸到尾最壞情況下要找滿全場。你真正需要的是一種結(jié)構(gòu)既不用關心下標又不用遍歷全場。這種需求就是哈希表要解決的。1.2 哈希思想的雛形算出一個位置來哈希表的想法其實很樸素。你去圖書館借書管理員不會帶你從第一排書架開始找而是先看索書號索書號本身就包含了分類體系走到對應分區(qū)順著編號一摸就拿到了。你去快遞驛站取件快遞員也不會把所有包裹拆開挨個翻他先按手機尾號分貨架再按包裹上的編號找。哈希表做的就是同一件事把任意一個key通過一個計算過程映射成數(shù)組里的某個下標。這個計算過程叫哈希函數(shù)算出來的值叫哈希值數(shù)組里的每個格子叫桶bucket。理論上只要哈希函數(shù)能把不同的key均勻散開每次查找就能直接定位到目標桶時間復雜度接近O(1)。那HashMap只不過是把這套思想在Java里實現(xiàn)了并且加了處理沖突、自動擴容的機制。所以理解HashMap核心就是理解兩件事key怎么變成一個桶下標以及多個key落到同一個桶時怎么辦。2. HashMap的桶位怎么來的hash()與下標定位2.1 hash()為什么要異或高16位先看JDK 8里HashMap計算哈希值的源碼static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }這里有兩個動作先調(diào)用key自身的hashCode()拿到一個int然后把高16位和低16位做異或得到的才是真正參與桶定位的hash值。為什么要折騰這一步因為后續(xù)定位桶的時候用的是數(shù)組長度減一和hash值做按位與。默認數(shù)組長度16對應的二進制是0000 0000 0000 1111按位與會把高28位全部清零只保留最低4位。如果兩個key的hashCode在高位有差異、低位完全相同那它們就會落到同一個桶這就是沖突。而且很多對象的hashCode恰恰在高位差異較大低位區(qū)分度不足。把高16位異或到低16位相當于讓高位的特征也參與低位的運算即使數(shù)組很短散列效果也會好很多。這一步在源碼注釋里叫“擾動函數(shù)”確實是經(jīng)過權(quán)衡后性價比很高的一步。2.2 為什么容量必須是2的冪以及取模優(yōu)化定位桶下標的核心代碼是這一行i (n - 1) hashn是數(shù)組長度。這里用按位與代替取模%原因是位運算比取?？斓枚?。但要成立前提是n必須是2的冪。當n16時n-115二進制是1111n32時n-131二進制是11111全都是低位連續(xù)的1這樣按位與的結(jié)果就等于hash對n取余而且效率更高。HashMap源碼在構(gòu)造時對容量做了一圈處理就是為了保證這一點。你傳入任何初始容量它都會向上補成2的冪static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }你傳3它變成4傳10變成16傳100變成128。這套移位運算把最高位后面的所有位全部填成1最后加個1就是最接近且大于等于原值的2的冪。還有一個好處。擴容時數(shù)組長度翻倍從16變成32原來長度16時下標只由hash低4位決定現(xiàn)在要由低5位決定。新增的那一位如果是0元素留在原地如果是1元素挪到“原下標16”的位置。因為2的冪特性擴容時不需要重新計算每個key的hash值只需要看新增比特位就夠了這也是JDK 8里resize能高效拆分鏈表的原因。2.3 沖突不可避免鏈化和樹化的閾值邏輯哈希函數(shù)設計得再好也不能保證每個key都算到不同桶沖突是必然的。HashMap解決沖突的辦法就是把多個沖突元素放到同一個桶里用鏈表串起來。JDK 8之前一直是這個方案簡單可靠但極端情況下所有key都落在同一個桶鏈表越來越長查找就退化成了O(n)。JDK 8改成了鏈表加紅黑樹的混合結(jié)構(gòu)同一個桶里節(jié)點數(shù)超過8并且整個數(shù)組長度大于等于64就會把鏈表轉(zhuǎn)成紅黑樹。紅黑樹查找復雜度O(log n)在一棵深度幾十的樹里找一個元素跟遍歷幾千個節(jié)點的鏈表是完全不同的量級。為什么閾值是8源碼注釋里給出過一個統(tǒng)計結(jié)論在隨機哈希碼的情況下桶內(nèi)節(jié)點數(shù)達到8的概率大約只有千萬分之六對絕大多數(shù)正常業(yè)務來說幾乎不可能觸發(fā)樹化。反而如果閾值設得太低比如2稍微有點沖突就樹化而樹節(jié)點的內(nèi)存占用是普通節(jié)點的兩倍左右性能反而下降。等紅黑樹節(jié)點數(shù)降到6以下又會變回鏈表這中間留了緩沖區(qū)間避免頻繁在兩種結(jié)構(gòu)之間來回切換。3. put和get的完整源碼鏈路3.1 put(key, value)時發(fā)生了什么JDK 8里put的入口很簡單但背后邏輯值得逐行看public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; int n; // 第一次put時整個表還是空的先擴容初始化 if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 算出桶下標如果槽位是空的直接放進新節(jié)點 int i (n - 1) hash; if ((p tab[i]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; // 桶里已有節(jié)點先比較hash再比較key if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; else if (p instanceof TreeNode) // 桶里已是紅黑樹走紅黑樹插入邏輯 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 桶里是鏈表遍歷找尾部插入如果中途遇到相同key記錄舊節(jié)點 for (int binCount 0; ; binCount) { if ((e p.next) null) { p.next newNode(hash, key, value, null); if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } // e不為空說明存在相同key覆蓋舊value并返回舊value if (e ! null) { V oldValue e.value; e.value value; return oldValue; } } modCount; // 元素數(shù)量超過閾值就擴容 if (size threshold) resize(); return null; }注意幾個細節(jié)。定位到桶以后如果桶里已經(jīng)有節(jié)點先比hash再比對key。比對key的時候用了兩層判斷第一層是引用判斷k key比如你用同一個String對象做key直接引用相等就命中第二層是key.equals(k)處理的是內(nèi)容相同但引用不同的情況比如兩次都傳入字符串1001它們不是同一個對象但equals相等。只有hash相同才有必要做equals比較hash不同就直接認定不是同一個key。這能夠大大減少equals的調(diào)用次數(shù)畢竟哈希定位已經(jīng)把絕大多數(shù)無關key擋在外面了。3.2 get(key)時為什么能精準命中get的鏈路和put高度對稱public V get(Object key) { NodeK,V e; return (e getNode(hash(key), key)) null ? null : e.value; } final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; // 表非空且目標桶位置有節(jié)點才可能找到 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 先檢查第一個節(jié)點 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 第一個節(jié)點沒命中看是樹還是鏈表 if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); // 鏈表逐個比較 do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }這個流程已經(jīng)清晰先通過hash(key)算出哈希值再用(n - 1) hash定位桶桶里節(jié)點碰運氣直接命中命不中就在鏈表或紅黑樹里繼續(xù)比較。之所以說HashMap查詢是“近似O(1)”就是因為大多數(shù)情況下桶里是空的或者只有一兩個節(jié)點一次定位加一兩次比較就出結(jié)果只有沖突嚴重時才會走到后面的鏈表或樹遍歷。3.3 equals和hashCode的契約為什么是命中的前提如果你只重寫equals但不同時重寫hashCode會出大問題。假設你有一個訂單類Orderequals比較的是orderNo但hashCode還是Object的默認實現(xiàn)——基于對象內(nèi)存地址。兩個orderNo完全一樣的訂單對象equals返回true但hashCode不同。第一次put進去用的是對象A第二次get時傳入對象BB的hash值跟A不同桶下標直接不一樣連目標桶都找不到equals根本沒機會執(zhí)行。這就是哈希表最核心的契約equals相等的兩個對象hashCode必須相等。反過來hashCode相等不等于equals相等這是允許的這正是哈希沖突。兩個不同key算到同一個桶最終靠equals來區(qū)分誰是誰。所以正確做法是參與equals比較的字段必須同時參與hashCode計算反之如果hashCode用了某個字段equals也最好用上否則可能出現(xiàn)兩個對象hashCode相同但業(yè)務上含義不同put時被當成同一個key覆蓋的情況。后面第4部分我會給完整示例。4. 實際開發(fā)中容易踩的三個性能坑4.1 初始容量與加載因子的正確姿勢HashMap的默認容量是16加載因子是0.75。加載因子的含義是當元素數(shù)量超過容量 × 0.75時觸發(fā)resize擴容。也就是說默認情況下存到第12個元素HashMap就會擴容到32容量翻倍。很多人不關心這個導致寫入數(shù)據(jù)量大時反復擴容。我實測過往默認HashMap里塞100條數(shù)據(jù)會觸發(fā)至少4次resize每次resize都要重新分配數(shù)組、重新計算所有已有節(jié)點的桶下標、移動節(jié)點。1億條級別的數(shù)據(jù)光是擴容的rehash成本就非?？捎^。正確的初始化方式是按預計數(shù)據(jù)量反推。如果你預計要放100條數(shù)據(jù)int expectedSize 100; MapString, Object map new HashMap((int) (expectedSize / 0.75f) 1);計算下來初始容量設置成134HashMap會自動向上取整為256閾值變成256×0.75192遠超100整個過程不會觸發(fā)擴容。如果直接寫new HashMap(100)容量會向上取成128閾值是96存到第96個元素時還是得擴容一次等于白打算。加載因子0.75是JDK團隊在時間成本和空間成本里取的平衡點。調(diào)小到0.5桶更空、沖突更少、查詢更快但內(nèi)存浪費嚴重調(diào)大到1.0空間利用率高但碰撞概率上升鏈表變長查詢變慢。普通業(yè)務場景不要動這個值真要調(diào)先壓測再調(diào)。4.2 自定義對象當keyequals和hashCode怎么配開發(fā)中最容易出問題的場景是把自定義對象塞進HashMap當key比如訂單、賬號、設備信息。先看一個會翻車的寫法class Order { private String orderNo; private BigDecimal amount; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Order order (Order) o; return Objects.equals(orderNo, order.orderNo); } // 忘記重寫 hashCode }兩個orderNo相同的Order對象equals返回true但hashCode還是默認的地址哈希意味著同一筆訂單兩個不同的對象實例放進Map會被當成兩個key。get的時候傳入另一個同orderNo的對象hash定位直接落到另一個桶結(jié)果永遠是null。排查了半天最后根源就是hashCode沒重寫。正確的版本是這樣class Order { private final String orderNo; private BigDecimal amount; public Order(String orderNo) { this.orderNo orderNo; } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Order order (Order) o; return Objects.equals(orderNo, order.orderNo); } Override public int hashCode() { return Objects.hash(orderNo); } }equals只用orderNo比較hashCode也只由orderNo計算契約一致性滿足。還有一個進階要求key對象盡量不可變。如果你把key放進Map之后又修改了某個參與hashCode計算的字段這個key的hash值就變了再調(diào)用get時按新hash值定位到另一個桶舊桶里的數(shù)據(jù)就永遠找不到了等于內(nèi)存里多了一份永遠不會被訪問的孤兒節(jié)點。String、Integer這類包裝類天生不可變所以是最常用的key類型。自定義類做key時核心字段建議設成final去掉setter從根本上杜絕這個問題。4.3 并發(fā)場景別拿HashMap硬扛HashMap不是線程安全的。多線程同時put時兩個線程可能在同一桶位置寫入后寫的覆蓋先寫的更麻煩的是擴容階段多線程同時觸發(fā)resizeJDK 7里甚至可能形成循環(huán)鏈表get的時候直接死循環(huán)這是當年的經(jīng)典線上事故。JDK 8改成尾插法循環(huán)鏈表問題基本被解決但數(shù)據(jù)丟失、覆蓋問題依然存在因為HashMap的內(nèi)部操作沒有同步機制。并發(fā)場景的正確選擇是ConcurrentHashMap。JDK 8的ConcurrentHashMap放棄了分段鎖改用CAS加synchronized鎖單個桶節(jié)點鎖粒度更細并發(fā)讀的時候基本無鎖寫入時只鎖住目標桶性能遠好于給整個HashMap加synchronized。如果只是低并發(fā)的場景讀多寫少也可以用Collections.synchronizedMap(new HashMap())但這是整表鎖寫操作串行高并發(fā)下吞吐量上不去。記住一個原則共享可變Map要么用ConcurrentHashMap要么不要共享。5. 常見問題排查速查5.1 高頻問題對照表現(xiàn)象可能原因排查方法解決方案查詢越來越慢自定義key的hashCode寫得差大量key落同一桶打印桶內(nèi)節(jié)點數(shù)分布看是否有超長鏈表重寫hashCode讓更多字段參與計算同一對象get不到值只重寫equals沒重寫hashCode或key可變檢查key的equals和hashCode實現(xiàn)的一致性檢查key是否put后被修改遵守契約key字段設final修改后重新放入Map寫入量大時明顯卡頓頻繁擴容rehash成本高看日志中resize觸發(fā)次數(shù)或計算閾值與數(shù)據(jù)量的關系構(gòu)造時用expectedSize / 0.75f 1設置初始容量多線程寫入丟數(shù)據(jù)HashMap并發(fā)不安全高并發(fā)壓測觀察數(shù)據(jù)丟失換成ConcurrentHashMap遍歷結(jié)果順序不穩(wěn)定HashMap本身不保證順序換用LinkedHashMap按寫入順序遍歷用LinkedHashMap按key排序用TreeMapput一個null鍵允許null key放在桶下標0這是設計行為業(yè)務上自行區(qū)分null和空字符串Map內(nèi)存只增不減key被外部引用無法回收檢查key生存周期必要時用WeakHashMap或手動remove5.2 一個快速查看哈希分布的小工具排查自定義對象哈希質(zhì)量的時候我經(jīng)常寫一小段代碼打印桶分布直觀看到?jīng)_突是否嚴重public static void printBucketStats(MapObject, Object map) { try { java.lang.reflect.Field field HashMap.class.getDeclaredField(table); field.setAccessible(true); Object[] table (Object[]) field.get(map); if (table null) { System.out.println(table is empty); return; } int total 0; int maxBin 0; int emptyBin 0; for (Object node : table) { int count 0; Object p node; while (p ! null) { count; p ((java.lang.reflect.Field) p.getClass().getDeclaredField(next)).get(p); } if (count 0) emptyBin; maxBin Math.max(maxBin, count); total count; } System.out.printf(table length%d, total nodes%d, empty bins%d, max bin%d%n, table.length, total, emptyBin, maxBin); } catch (Exception ignored) { // 反射失敗時直接放棄 } }這段代碼用反射拿到HashMap內(nèi)部的table數(shù)組統(tǒng)計每個桶的節(jié)點數(shù)量。如果空桶占比很高、某個桶節(jié)點數(shù)特別多反過來說明hashCode分布不夠均勻。正常業(yè)務數(shù)據(jù)下最大的桶節(jié)點數(shù)應該是個位數(shù)如果出現(xiàn)幾十個節(jié)點的長鏈就得回頭查key的hashCode實現(xiàn)了。我自己的排查經(jīng)驗是HashMap相關的詭異問題90%最后都歸結(jié)到key對象身上。要么equals和hashCode寫得不一致要么key是可變對象被改壞了要么hashCode分布太差導致桶傾斜。把這三條路排查完基本都能定位到根因。6. 再分享一點個人的使用體會文章最后分享一個我實際操作中的體會調(diào)試HashMap問題時不要一上來就懷疑源碼或者并發(fā)先把key的hashCode和equals擺到桌面上看一遍。這兩個方法加起來不到二十行卻是整個HashMap運轉(zhuǎn)的基石絕大多數(shù)“莫名找不到”“莫名覆蓋”的問題都從這里來。另外初始容量這個參數(shù)很多人覺得不設也沒關系量大了才知道代價。我在一個批量導入功能里往Map里灌了大概幾萬條數(shù)據(jù)最初沒設容量導入過程能明顯感覺到后半程變慢。后來按expectedSize / 0.75f 1初始化后耗時直接降了一截代碼只改了一行。這種性價比極高的優(yōu)化項目里多多益善。把從key到桶下標再到節(jié)點的這條鏈路琢磨透了再回頭看ConcurrentHashMap的分段鎖演進、TreeMap的紅黑樹結(jié)構(gòu)甚至是Redis里的哈希表實現(xiàn)都會覺得順理成章。數(shù)據(jù)結(jié)構(gòu)這種東西不怕不熟悉API就怕不理解那個“根據(jù)key找到value”的核心思想。