HashMap的底層實現(xiàn)原理大部分Java工程師都能聊上幾句數(shù)組加鏈表鏈表長度到8再轉(zhuǎn)紅黑樹。可一旦話題換成TreeMap與TreeSet的實現(xiàn)原理能講清楚的人就少了一半。我在剛開始啃這兩個類源碼時也有同樣的困惑——明明都是Map憑什么TreeMap的遍歷天然有序排序的代價又在哪里TreeSet去重到底靠什么這些問題如果不把底層數(shù)據(jù)結(jié)構(gòu)摸透用起來總會踩到幾個不痛不癢但很坑的錯誤。今天這篇就系統(tǒng)地把TreeMap和TreeSet的底褲扒干凈從紅黑樹講起一路看到put、get、刪除的源碼路徑再落到實戰(zhàn)里真正值得注意的陷阱。無論你是準(zhǔn)備面試還是要在一堆有序數(shù)據(jù)里做區(qū)間查詢都能從這里拿到可以直接用的東西。1. 先從“憑什么有序”說起TreeMap的底層契約1.1 TreeMap與HashMap的本質(zhì)差異HashMap大家都知道核心是哈希表通過數(shù)組加鏈表/紅黑樹來存儲鍵值對。哈希定位最大的特點是快平均O(1)但代價是無序——哈希函數(shù)打散了元素在內(nèi)存里的物理順序遍歷的時候你根本不知道下一個出來的鍵是誰。TreeMap走的完全是另一條路。它不哈希而是維護(hù)一棵排序二叉樹。所有鍵按照“左小右大”的規(guī)則存放在樹里任何時刻對這棵樹做中序遍歷得到的序列都是嚴(yán)格升序的。這個“有序”不是在遍歷時才臨時排序而是在每次插入、刪除時就已經(jīng)通過樹的自平衡機(jī)制維護(hù)好了。TreeMap的puts、gets、deletes全部落在從根到葉子的路徑上時間復(fù)雜度穩(wěn)定在O(logN)樹的高度就是log級別的。也就是說TreeMap和HashMap的差異不是“快慢”這么簡單而是數(shù)據(jù)組織方式不同一個靠哈希桶定位一個靠排序樹定位。理解了這一點后面看它的所有API行為都會很順。1.2 排序的物理載體紅黑樹到底是一棵什么樣的樹先復(fù)習(xí)一下二叉搜索樹BST左子樹所有節(jié)點小于根右子樹所有節(jié)點大于根中序遍歷天然有序。BST最大的問題在于退化——如果你按順序插入1、2、3、4、5樹會變成一根鏈表查詢復(fù)雜度退化成O(N)。紅黑樹就是加了五條顏色規(guī)則的BST目標(biāo)是把樹的高度控制在log級別。它不像AVL樹那樣嚴(yán)格追求左右子樹高度差不超過1而是通過顏色約束做到“近似平衡”。紅黑樹允許最長路徑是最短路徑的兩倍但因為有這個上界任何操作路徑都不會超過2log2(N1)所以所有操作都能保證O(logN)。TreeMap為什么選紅黑樹而不是AVL因為紅黑樹的平衡代價更小。AVL為了追求絕對平衡插入刪除時頻繁旋轉(zhuǎn)寫操作慢紅黑樹放寬了平衡條件犧牲一點查詢常數(shù)換來更少的結(jié)構(gòu)調(diào)整。對TreeMap這種偏寫、偏范圍操作的場景是更務(wù)實的選擇。1.3 TreeSet只是“只用了Key的TreeMap”很多人以為TreeSet是另一套數(shù)據(jù)結(jié)構(gòu)其實它就是一棵只關(guān)心“鍵”的TreeMap。TreeSet內(nèi)部持有一個NavigableMapE,Object的引用默認(rèn)就是TreeMap實例。你把元素add進(jìn)TreeSet它干的事情就是把元素當(dāng)作TreeMap的key放進(jìn)去value統(tǒng)一用一個固定的Object占位符。這個設(shè)計在源碼里表現(xiàn)得特別直白public class TreeSetE extends AbstractSetE implements NavigableSetE, Cloneable, java.io.Serializable { private static final Object PRESENT new Object(); private transient NavigableMapE,Object m; public TreeSet() { this(new TreeMap()); } public boolean add(E e) { return m.put(e, PRESENT) null; } public boolean remove(Object o) { return m.remove(o) ! null; } public boolean contains(Object o) { return m.containsKey(o); } }所以TreeSet的排序、去重、范圍查詢等行為全部繼承自TreeMap。把TreeMap的紅黑樹機(jī)制弄明白TreeSet就只剩下“適配器模式”這一層皮了。這也是為什么JDK源碼設(shè)計里復(fù)用性可以做到這么極致——一個底層數(shù)據(jù)結(jié)構(gòu)換個接口包裝就成了另一個集合類。2. 紅黑樹的五條鐵律與TreeMap的平衡藝術(shù)2.1 五條規(guī)則從哪兒來紅黑樹對每個節(jié)點涂上黑或紅并遵守五條規(guī)則每個節(jié)點不是紅色就是黑色。根節(jié)點是黑色。每個葉子節(jié)點NIL是黑色。紅色節(jié)點的兩個子節(jié)點必須都是黑色也就是說紅節(jié)點不能挨著紅節(jié)點。從任意節(jié)點到其每個葉子節(jié)點的路徑上黑色節(jié)點的數(shù)量必須相同。這五條規(guī)則的核心作用是把樹的高度限定在O(logN)內(nèi)。直覺是這樣因為規(guī)則5任何一條路徑上的黑節(jié)點數(shù)相同因為規(guī)則4一條路徑上不能連續(xù)出現(xiàn)兩個紅節(jié)點。所以最長路徑是“黑紅黑紅”交替最多只是最短路徑全黑的兩倍。有了這個上界TreeMap的查找、插入、刪除就都能保證對數(shù)級復(fù)雜度。我在剛接觸的時候一直覺得規(guī)則5是最難理解的其實它就是在保證“每條路一樣沉”讓樹不會往某個方向畸形生長。這和以前玩天平有點像兩邊的黑節(jié)點數(shù)必須持平誰多誰少都失衡。2.2 插入默認(rèn)紅色破壞規(guī)則也分三種情況TreeMap插入新節(jié)點時默認(rèn)把它涂成紅色。為什么因為紅色節(jié)點不會破壞規(guī)則5也就是不會改變?nèi)魏温窂缴系暮诠?jié)點數(shù)唯一的風(fēng)險是碰到紅父節(jié)點造成“紅紅相連”違反規(guī)則4。這樣就把問題限定在一個局部修起來快。新的紅色節(jié)點插入后按父節(jié)點和叔叔節(jié)點的顏色分三種情況處理父節(jié)點為黑色直接插入什么事都不用做。父紅、叔叔紅把父和叔變黑把祖父變紅然后從祖父繼續(xù)往上調(diào)整因為祖父變紅后可能會和它的父節(jié)點產(chǎn)生新的沖突。父紅、叔叔黑需要旋轉(zhuǎn)加變色。如果新節(jié)點在父親的同側(cè)LL或RR做一次旋轉(zhuǎn)加變色如果在異側(cè)LR或RL先旋轉(zhuǎn)成同側(cè)再處理。這個流程比較繞但只要記住“旋轉(zhuǎn)就是調(diào)整父子關(guān)系不改變中序遍歷結(jié)果”就夠了。TreeMap里的fixAfterInsertion方法核心代碼其實就是按這個邏輯寫的。我簡化記錄一下while (x ! null x ! root colorOf(parentOf(x)) RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,V y rightOf(parentOf(parentOf(x))); // 叔叔 if (colorOf(y) RED) { // 情況一變色上溯 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x rightOf(parentOf(x))) { // 情況二先左旋變成情況三 x parentOf(x); rotateLeft(x); } // 情況三右旋 變色 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } // 對稱方向就不展開了 } setColor(root, BLACK);老實說源碼比這個還要密一些但骨架就在這里。真正優(yōu)化過的紅黑樹插入調(diào)整平均只需要常數(shù)次旋轉(zhuǎn)最多兩次剩下的都是變色。所以即使面對幾百萬條數(shù)據(jù)TreeMap的插入也不會有明顯的卡頓。2.3 刪除為什么比插入麻煩得多刪除是紅黑樹實現(xiàn)里最頭疼的部分。林納斯說過刪除一個節(jié)點比插入要難一個數(shù)量級紅黑樹刪除尤其如此。如果一個節(jié)點是紅色直接刪除就好因為紅色不會影響黑高。麻煩的是刪除黑色節(jié)點——它會讓某條路徑上的黑節(jié)點數(shù)變少違反規(guī)則5。修復(fù)的思路是引入“雙重黑色”的概念先當(dāng)成那個位置欠了一個黑然后看兄弟節(jié)點的顏色來決定怎么還債。TreeMap的fixAfterDeletion主要按兄弟節(jié)點的情況分兄弟是紅色旋轉(zhuǎn)一次把兄弟變黑父變紅重新定位。兄弟是黑色且兄弟的兩個孩子都是黑色兄弟變紅問題向上推一層。兄弟是黑色但至少有一個紅孩子通過旋轉(zhuǎn)加變色把黑色補(bǔ)回來并直接結(jié)束。這些情況我自己剛開始也背不下來后來發(fā)現(xiàn)關(guān)鍵是理解“借顏色”的思想刪除黑色節(jié)點等于拿走了路徑上一個黑修復(fù)就是想辦法讓其他路徑勻出一個黑來或者把問題推到父節(jié)點去解決。因為單次刪除的旋轉(zhuǎn)次數(shù)最多三次所以即使最壞情況也只是O(logN)的變色加常數(shù)次旋轉(zhuǎn)。2.4 TreeMap如何利用紅黑樹實現(xiàn)O(logN)復(fù)雜度紅黑樹保證樹高不超過2log2(N1)所以從根開始找任何一個鍵最多走這么深。TreeMap的put要先找到合適葉子位置get要先沿路徑比較delete要找到節(jié)點再修復(fù)復(fù)雜度全都由樹高決定。這也是TreeMap和HashMap最大的性能分水嶺HashMap平均O(1)TreeMap穩(wěn)定O(logN)但反過來HashMap沒有序TreeMap天然有序。這種取舍在工程上非常經(jīng)典。3. TreeMap源碼實現(xiàn)put、get與迭代器的真實執(zhí)行路徑3.1 Entry節(jié)點結(jié)構(gòu)和比較器注入TreeMap內(nèi)部定義了一個靜態(tài)內(nèi)部類Entry它是整棵紅黑樹的基本單元static final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; EntryK,V right; EntryK,V parent; boolean color BLACK; Entry(K key, V value, EntryK,V parent) { this.key key; this.value value; this.parent parent; } // getKey/getValue/setValue/equals/hashCode 略 }可以看出每個節(jié)點除了key/value還要額外維護(hù)left、right、parent三個引用和一個布爾顏色。這也是TreeMap內(nèi)存占用比HashMap大的原因之一——每個節(jié)點多了好幾個指針。下面這個結(jié)構(gòu)特點在后面聊性能時會再次出現(xiàn)。TreeMap支持兩種排序方式自然排序和自定義Comparator。private final Comparator? super K comparator; SuppressWarnings(unchecked) final int compare(Object k1, Object k2) { return comparator null ? ((Comparable? super K) k1).compareTo((K) k2) : comparator.compare((K) k1, (K) k2); }看到?jīng)]有如果構(gòu)造時沒傳ComparatorTreeMap會把key強(qiáng)轉(zhuǎn)成Comparable然后調(diào)用compareTo。所以使用TreeMap的時候key要么實現(xiàn)Comparable要么必須在構(gòu)造時給Comparator否則第一次插入就會拋ClassCastException。這個細(xì)節(jié)很基礎(chǔ)但很多人第一次見TreeMap的空構(gòu)造器時都會踩到。3.2 put全流程比較、下鉆、掛載、修復(fù)TreeMap的put方法邏輯非常清晰可以拆成四步從根節(jié)點開始用compare方法比較當(dāng)前key和節(jié)點key。小于0走左子樹大于0走右子樹直到找到插入位置。如果中途發(fā)現(xiàn)key已經(jīng)存在直接用新value替換舊value返回舊value。如果走到null位置創(chuàng)建一個新Entry掛上去然后調(diào)用fixAfterInsertion做紅黑修復(fù)。public V put(K key, V value) { EntryK,V t root; if (t null) { compare(key, key); // 檢查key類型順便觸發(fā)空檢查 root new Entry(key, value, null); size 1; modCount; return null; } Comparator? super K cpr comparator; if (cpr ! null) { do { parent t; cmp cpr.compare(key, t.key); if (cmp 0) t t.left; else if (cmp 0) t t.right; else return t.setValue(value); } while (t ! null); } // 其他分支類似最后創(chuàng)建新節(jié)點并調(diào)整 EntryK,V e new Entry(key, value, parent); if (cmp 0) parent.left e; else parent.right e; fixAfterInsertion(e); size; modCount; return null; }注意TreeMap的value是允許為null的但key默認(rèn)不允許null。為什么因為compare方法在key為null時根本沒法比較自然序調(diào)用null.compareTo會直接NPE。前面說了除非你傳一個能處理null的比較器否則TreeMap的鍵必須非空。這個和HashMap能存null鍵值形成鮮明對比后面坑里再細(xì)說。3.3 迭代器如何做到“天然有序”TreeMap能按升序遍歷靠的是迭代器使用中序遍歷。所謂中序遍歷就是“左子樹 → 當(dāng)前節(jié)點 → 右子樹”的順序由于BST左小右大的特性結(jié)果天然升序。TreeMap的EntryIterator在實現(xiàn)next時內(nèi)部其實是調(diào)用了successor方法static K,V TreeMap.EntryK,V successor(EntryK,V t) { if (t null) return null; else if (t.right ! null) { EntryK,V p t.right; while (p.left ! null) p p.left; return p; } else { EntryK,V p t.parent; EntryK,V ch t; while (p ! null ch p.right) { ch p; p p.parent; } return p; } }邏輯不復(fù)雜如果當(dāng)前節(jié)點有右子樹后繼就是右子樹里最左的那個節(jié)點否則向上找第一個“自己是父節(jié)點左孩子”的祖先那個祖先就是后繼。迭代器的失敗保護(hù)也依賴modCount——如果遍歷時TreeMap被結(jié)構(gòu)性修改再調(diào)next就會拋ConcurrentModificationException。這點和ArrayList的行為一致。如果你需要反向遍歷TreeMap還提供了descendingMap()返回的視圖迭代順序是降序的。它不是一個新副本而是同一個樹上的反向視圖這個設(shè)計在Java集合框架里很常見。3.4 刪除后繼替換與雙黑修復(fù)在TreeMap里的落點TreeMap的removeEntry走的是標(biāo)準(zhǔn)的二叉搜索樹刪除路線被刪節(jié)點有兩個孩子時找后繼右子樹最小節(jié)點把后繼的key/value復(fù)制到被刪節(jié)點上然后實際去刪后繼節(jié)點。后繼節(jié)點至多只有一個右孩子所以真正的物理刪除很簡單。如果刪除的節(jié)點是黑色就調(diào)用fixAfterDeletion做紅黑修復(fù)。最后size--modCount。整個過程我不會在文章里貼全源碼因為那個fixAfterDeletion分支如果畫出來會有四個case加鏡像太長了。但只要記住實際刪除的往往不是“最初想刪的那個節(jié)點”而是它“中序遍歷后面的繼任者”。這個后繼替換思路在很多有序數(shù)據(jù)結(jié)構(gòu)里都能看到比如二叉搜索樹的remove甚至跳表刪除也是一樣的思想。4. TreeSet一個披著Set外衣的TreeMap4.1 核心構(gòu)造器與方法委托的背后TreeSet的實現(xiàn)原理用一句話概括就是委托TreeMap。JDK內(nèi)部給了它一個NavigableMap類型的引用m默認(rèn)構(gòu)造器直接new一個TreeMappublic TreeSet() { this(new TreeMap()); } public TreeSet(Comparator? super E comparator) { this(new TreeMap(comparator)); } TreeSet(NavigableMapE,Object m) { this.m m; }第三個構(gòu)造器是包級私有的專門服務(wù)于subSet、headSet等視圖方法。TreeSet的add和remove前面已經(jīng)看過如果給TreeSet構(gòu)造傳了一個已有的TreeMap那它們的view就是共用的同一棵樹。TreeSet和HashSet的區(qū)別也在這里體現(xiàn)出來特性TreeSetHashSet底層結(jié)構(gòu)TreeMap紅黑樹HashMap哈希表排序性按比較器或自然序升序無序去重依據(jù)compareTo/compare 0hashCode equals核心復(fù)雜度O(logN)O(1) 平均是否允許null默認(rèn)不允許會NPE允許一個null這張表基本就是面試?yán)锔哳l對比題的完整答案。4.2 去重判定不是equals是compareTreeSet最容易被忽視的點是它的“相等”定義。HashSet去重依賴hashCode和equalsTreeSet去重卻只看比較器的返回值compare(a, b) 0就算同一個元素。這意味著你甚至可以構(gòu)造出兩個equals返回false、但compare返回0的對象它們放進(jìn)TreeSet會被當(dāng)成重復(fù)元素第二個add會返回false。反過來如果compare永遠(yuǎn)不返回0即使兩個對象equals為trueTreeSet也能同時存下兩個——這會讓集合行為徹底“跑偏”。JDK文檔明確建議Comparator應(yīng)該和equals保持一致性但因為它只是建議很多人就忽略了結(jié)果線上出現(xiàn)“去重去不掉”或“誤去重”的詭異問題。實際開發(fā)里我的建議是如果對象同時需要放HashSet和TreeSet一定要讓compareTo和equals的定義保持一致。做不到的話至少保證單一容器里只依賴一種判定邏輯不要交叉使用。4.3 子集合視圖subSet/headSet/tailSet的實現(xiàn)邏輯TreeSet的范圍視圖方法返回的不是一份拷貝而是一個“視圖”public NavigableSetE subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); }這里構(gòu)造的TreeSet內(nèi)部持有的m是原TreeMap的子映射視圖。往子集合里add元素原集合也會多出這個元素原集合刪了元素子集合也看不到它。這種視圖機(jī)制的好處是零拷貝、操作直接映射到底層紅黑樹代價是如果你沒意識到這一點很容易在修改子集合時“意外影響”全量數(shù)據(jù)。我見過有人拿subSet做臨時過濾過濾完不清空結(jié)果原集合一直包含那些“不該存在”的數(shù)據(jù)排查半天才發(fā)現(xiàn)是視圖的傳染性。這不算TreeSet的bug而是設(shè)計上的約定用之前必須清楚。5. 實戰(zhàn)用法與選型有序Map在真實需求里的打開方式5.1 區(qū)間查詢subMap、headMap、tailMap的用法與邊界TreeMap最有價值的地方不是簡單的排序遍歷而是范圍查詢。比如你有大量帶時間戳的日志要查某一分鐘內(nèi)有哪些記錄用HashMap就只能全遍歷用TreeMap就是一條subMap調(diào)用TreeMapLong, String eventMap new TreeMap(); eventMap.put(1700000000000L, start); eventMap.put(1700000001000L, slow); eventMap.put(1700000002000L, end); NavigableMapLong, String window eventMap.subMap(1700000000000L, true, 1700000000200L, true);subMap返回的是位于[fromKey, toKey]之間的視圖兩個boolean參數(shù)控制是否包含邊界。headMap(toKey)取小于toKey的部分tailMap(fromKey)取大于等于fromKey的部分。這些操作都是基于紅黑樹從根開始定位邊界再向后遍歷所以復(fù)雜度是O(logN m)m是返回的元素數(shù)量尤其在大量數(shù)據(jù)下優(yōu)勢非常明顯。用的時候有個習(xí)慣要注意JDK很多范圍習(xí)慣叫“左閉右開”但subMap的邊界默認(rèn)是包含頭、不包含尾除非你顯式指定inclusive。所以判斷區(qū)間時一定要想清楚自己的業(yè)務(wù)是閉區(qū)間還是開區(qū)間否則多一條記錄少一條記錄是常事。5.2 最近鄰匹配與有序彈出floorKey、ceilingKey、pollFirstEntry除了范圍查詢TreeMap還能做“查找最接近某個值”的操作這是HashMap完全做不到的ceilingKey(k)返回大于等于k的最小鍵找不到返回null。floorKey(k)返回小于等于k的最大鍵。lowerKey(k)返回嚴(yán)格小于k的最大鍵。higherKey(k)返回嚴(yán)格大于k的最小鍵。舉個實際場景系統(tǒng)要給請求分配端口端口池里有一批空閑端口每次分配“最接近某個基準(zhǔn)值的端口”用ceilingEntry就能直接命中再比如優(yōu)惠券過期時間表里要找到一張“過期時間剛好大于當(dāng)前時間”的券不用遍歷全表直接ceilingKey(now)就行。還有一組方法叫pollFirstEntry / pollLastEntry返回并移除最小/最大的鍵值對。配合這兩個方法和TreeMap的有序性我經(jīng)常直接把它當(dāng)“有序隊列”用任務(wù)按優(yōu)先級入隊每次pollFirstEntry取最緊急的那個比PriorityQueue多出來的優(yōu)勢是還能直接按區(qū)間條件批量取出任務(wù)。這個用法很冷門但實戰(zhàn)效率極高。5.3 與HashMap、LinkedHashMap的選擇矩陣容器順序平均復(fù)雜度典型場景HashMap無序O(1)快速等值查找、緩存LinkedHashMap插入序/訪問序O(1)LRU緩存、保持寫入順序TreeMapkey自然序/自定義序O(logN)范圍查詢、排序遍歷、最近鄰LinkedHashMap雖然也是“有序”但它保持的是插入順序或訪問順序不是key的邏輯順序。如果需求是“按key大小排序再讀取”例如榜單按分?jǐn)?shù)高低、價格區(qū)間檢索LinkedHashMap就完全無能為力只能TreeMap上場。這是選型時最容易搞混的一點。順帶說一句HashMap底層在極端哈希沖突時也會用紅黑樹。JDK 8以后當(dāng)鏈表長度超過8且數(shù)組容量達(dá)到64鏈表會轉(zhuǎn)成紅黑樹目的就是把最壞情況下沖突桶里的查找從O(N)壓到O(logN)。這也說明紅黑樹在JDK里不只是TreeMap/TreeSet在用它已經(jīng)是哈希沖突兜底方案的一部分了。至于布隆過濾器那種“只判斷存在性、不關(guān)心有序”的場景和紅黑樹壓根不是一類工具——它允許誤判但省內(nèi)存沒法做范圍查詢所以兩者沒有可比性別混為一談。6. 踩坑復(fù)盤真正讓我翻車的三個場景6.1 可變鍵的災(zāi)難字段變更后整棵樹直接“錯亂”有次我用一個自定義對象做TreeMap的key比較器按對象的id字段排序。業(yè)務(wù)邏輯里有個操作會直接修改對象的id值然后我再用這個對象調(diào)用get返回null而原key明明還在map里。當(dāng)時第一反應(yīng)是懷疑比較器寫錯了打印出來才發(fā)現(xiàn)樹里那個鍵的“位置”還是舊的id對應(yīng)的位置可對象本身的id已經(jīng)變了。原因就在紅黑樹的機(jī)制上樹的平衡只在put和remove時根據(jù)當(dāng)時的比較結(jié)果調(diào)整它不會感知對象字段的變化。你把一個鍵的排序字段改了樹里的物理位置卻沒有跟著變后續(xù)所有查找、范圍判斷都會拿新值和舊位置比自然找不到。這個坑的根治辦法很簡單用作key的對象必須不可變或者至少保證參與比較的字段在整個生命周期里不動。如果業(yè)務(wù)確實要修改排序字段那就先remove再重新put不要試圖原地改。類似的坑在HashSet/HashMap里也有——修改了參與hashCode計算的字段會導(dǎo)致元素“丟”在舊桶里。只是TreeMap的樹結(jié)構(gòu)讓這個問題更隱蔽因為它表面看還像那么回事。6.2 比較器與equals不一致同一批對象在兩套集合里“判若兩樣”另一個案例更典型。項目中有一批用戶對象兩個對象只要id相同就認(rèn)為相同于是我寫Comparator時只比較id但沒有同步重寫equalsequals仍然比較所有字段。結(jié)果就是同一份數(shù)據(jù)放進(jìn)TreeSet能去重放進(jìn)HashSet去重失敗。更麻煩的是兩個地方的數(shù)據(jù)匯總時出現(xiàn)了“一邊說重復(fù)、一邊說不重復(fù)”的矛盾最后只能寫額外邏輯去對齊。這個坑的根子是Comparator和equals的契約不一致。TreeSet拿Comparator當(dāng)唯一標(biāo)準(zhǔn)HashSet拿equals/hashCode當(dāng)唯一標(biāo)準(zhǔn)你讓它們各執(zhí)一詞行為必然打架。我現(xiàn)在的習(xí)慣是寫任何比較器之前先問自己“這個東西放進(jìn)TreeSet和HashSet時我希望它們對重復(fù)的定義一樣嗎”如果一樣就強(qiáng)制保證compare返回0時equals也為true否則寧可拋異常也別靜默容忍。6.3 null處理一個NPE引發(fā)的排查疲勞第一次在項目里用TreeMap存配置往里面put了一個null鍵結(jié)果直接炸了NullPointerException。我第一反應(yīng)是TreeMap出bug了后來翻源碼才發(fā)現(xiàn)自然排序的compare方法調(diào)用null的compareTo這個異常是必然的。TreeMap允許null值但默認(rèn)不允許null鍵TreeSet則連null元素都裝不進(jìn)去因為add(null)會轉(zhuǎn)成put(null, PRESENT)一樣NPE。如果你想在TreeMap里用null鍵唯一的辦法是自定義Comparator并且在比較器里顯式處理null比如Comparator.nullsFirst或nullsLast。但這會引入更多邊界兩個null鍵在nullsFirst下會被視為相等直接互相覆蓋。說實話在有序容器里塞null鍵業(yè)務(wù)設(shè)計本身就要打個問號我后來基本都是提前在入口做非空校驗。還有個很容易誤判的點TreeMap的value允許為null所以get(key)返回null時你分不清楚是“鍵不存在”還是“鍵存在但value為null”。如果需要判斷鍵是否存在一定用containsKey別拿get的結(jié)果當(dāng)存在性依據(jù)。這個規(guī)則其實也適用于HashMap但在TreeMap里會因為你下意識認(rèn)為“它那么嚴(yán)格應(yīng)該不會允許null”而更容易踩。6.4 性能邊界紅黑樹不是萬能銀彈TreeMap的優(yōu)秀是相對“手動維持有序”來說的它的常數(shù)并不小。每個Entry除了key/value還帶著left、right、parent和color內(nèi)存開銷比HashMap桶里的Node高不少。我曾經(jīng)壓過百萬級的隨機(jī)數(shù)插入TreeMap的耗時大概是HashMap的兩到三倍這在量級上不算離譜但如果你只是要一個能快速查到元素、無所謂順序的緩存拿TreeMap來存就是平白給內(nèi)存和CPU上稅。更現(xiàn)實的問題是線程安全。TreeMap本身不是線程安全的并發(fā)寫會出問題。如果你既需要有序又需要并發(fā)安全應(yīng)該考慮ConcurrentSkipListMap底層用跳表無鎖并發(fā)范圍查詢一樣支持只是內(nèi)部結(jié)構(gòu)完全不同。跳表的原理和紅黑樹有相似之處都是通過多層索引加速查找但跳表對并發(fā)友好得多CAS改節(jié)點比紅黑樹的旋轉(zhuǎn)變色好實現(xiàn)得多。所以選型時別只看接口長一樣底層機(jī)制決定了它們的并發(fā)性能上限。最后一句話收束我自己的經(jīng)驗凡是需要“有序集合范圍切片最近鄰查找”這三個能力里的任何一個TreeMap/TreeSet都是第一默認(rèn)選項但前提是你從一開始就把鍵設(shè)計成不可變對象把比較器寫成和equals一致的規(guī)則。這個小習(xí)慣比任何源碼細(xì)節(jié)都更能幫你少踩坑。另外還有一個我很常用的冷門技巧NavigableMap接口提供了pollFirstEntry和pollLastEntry配合subMap用一棵TreeMap就能實現(xiàn)一個支持按區(qū)間批量彈出任務(wù)的有序隊列省掉自己維護(hù)PriorityQueue外加時間戳的麻煩。等你真正跑過幾輪百萬級數(shù)據(jù)體會過那棵紅黑樹在動態(tài)插入和刪除之間保持平衡的穩(wěn)定感你自然就會明白為什么JDK作者會把這個結(jié)構(gòu)安放在兩個最常用的有序集合類底部。