Set 家族全是 Map 的“只存 key 版”Set的核心承諾是元素不重復(fù)。但如果你讀HashSet源碼會(huì)發(fā)現(xiàn)一件很有意思的事——它自己幾乎不存數(shù)據(jù)去重邏輯全靠一個(gè)HashMap。這一篇揭開(kāi)Set家族借 Map 上位的秘密順便把LinkedHashSet和TreeSet的底層也一并講清。一、HashSet 的真相包裝了一個(gè) HashMap看HashSet的字段和構(gòu)造器就明白了privatetransientHashMapE,Objectmap;privatestaticfinalObjectPRESENTnewObject();// 占位 valuepublicHashSet(){mapnewHashMap();}HashSet把元素當(dāng)作HashMap的key存進(jìn)去value 統(tǒng)一用一個(gè)靜態(tài)空對(duì)象PRESENT占位。add方法publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;// key 已存在則 put 返回舊 value非 null→ false}put返回null說(shuō)明這個(gè) key 之前不存在add 成功返回 true如果 key 已存在put返回PRESENT非 nulladd 返回 false——去重就是靠 HashMap 的 key 不可重復(fù)實(shí)現(xiàn)的。所以HashSet的元素就是map.keySet()。二、去重的契約equals hashCode既然底層是 HashMap 的 key那HashSet判斷兩個(gè)元素是不是同一個(gè)用的就是 HashMap 那套先比 hashCode再比 equals見(jiàn) HashMap 篇。所以把自定義對(duì)象放進(jìn) HashSet必須正確重寫(xiě)equals和hashCode否則只重寫(xiě)equals不重寫(xiě)hashCode兩個(gè)邏輯相等的對(duì)象可能 hashCode 不同 → 落到不同桶 → 都被加進(jìn)去去重失效。只重寫(xiě)hashCode不重寫(xiě)equalshashCode 相同但 equals 不同 → 掛在同一個(gè)桶的鏈表上被認(rèn)為不同元素照樣去重失效。經(jīng)典反例你new User(張三)兩次如果User沒(méi)重寫(xiě)這兩個(gè)方法HashSet 會(huì)當(dāng)它倆是不同的人。重寫(xiě)后才會(huì)判定重復(fù)、只留一個(gè)。三、性能add/contains/remove 都是 O(1)因?yàn)橹苯游薪o HashMapHashSet的增、查、刪平均復(fù)雜度都是 O(1)。這是它相對(duì)于手寫(xiě) List 遍歷 contains的最大優(yōu)勢(shì)——后者是 O(n)。四、LinkedHashSet保插入序的 SetLinkedHashSet是HashSet的子類(lèi)構(gòu)造時(shí)建的是LinkedHashMapHashSet(intinitialCapacity,floatloadFactor,booleandummy){mapnewLinkedHashMap(initialCapacity,loadFactor);}所以它 HashSet 的去重能力 LinkedHashMap 的插入順序。遍歷時(shí)按你 add 的順序輸出而不是 HashSet 那種無(wú)序。代價(jià)同樣是節(jié)點(diǎn)多兩個(gè)引用、內(nèi)存略大。適合要去重、又想按添加順序展示的場(chǎng)景比如去重后的用戶操作流水。五、TreeSet排序的 SetTreeSet底層是TreeMap元素當(dāng)作 key同樣用PRESENT占位publicTreeSet(){this(newTreeMapE,Object());}特性元素自動(dòng)排序自然序或構(gòu)造時(shí)傳Comparator。元素必須可比較否則add拋ClassCastException不允許 null除非比較器允許。增刪查 O(log n)。實(shí)現(xiàn)NavigableSet支持first()、last()、lower()、higher()、subSet()等范圍/鄰近操作。適合要去重且要排序/取區(qū)間的場(chǎng)景比如排行榜去重后取 Top N。六、三兄弟怎么選需求選誰(shuí)去重不關(guān)心順序要最快HashSet去重 按插入順序遍歷LinkedHashSet去重 排序 范圍查詢(xún)TreeSet對(duì)應(yīng)底層一目了然HashSet→HashMapLinkedHashSet→LinkedHashMapTreeSet→TreeMap。整個(gè) Set 家族就是 Map 家族的只存 key 版記住這層關(guān)系Set 的行為就全解釋得通了。七、常見(jiàn)坑可變對(duì)象改了參與 equals/hashCode 的字段就從 Set 里消失了對(duì)象入 Set 后改字段它的哈希桶位置變了再contains/remove找不到成了游離垃圾。規(guī)則放進(jìn) HashSet/HashMap 的 key 必須是不可變對(duì)象或至少別改參與哈希的字段。遍歷時(shí)刪除用迭代器for (String x : set) set.remove(x)拋ConcurrentModificationException要用it.remove()。HashSet 允許一個(gè) null只有一個(gè)因?yàn)?key 不可重復(fù)TreeSet 不允許 null。八、面試追問(wèn)QHashSet 怎么保證不重復(fù)元素作 HashMap 的 keyvalue 用固定占位對(duì)象add 時(shí)map.put返回非 null 說(shuō)明 key 已存在返回 false 去重。Q為什么 HashSet 比 List 去重快List 去重要contains遍歷 O(n)HashSet 靠哈希 O(1)。QHashSet 和 TreeSet 的 null 策略為何相反HashSet 底層 HashMap 允許一個(gè) null keyTreeSet 底層 TreeMap 要靠比較器排 keynull 無(wú)法參與比較故不允許?？偨Y(jié)Set 家族沒(méi)有自己的存儲(chǔ)全是借 MapHashSet 包 HashMap、LinkedHashSet 包 LinkedHashMap、TreeSet 包 TreeMap元素作 key、統(tǒng)一用占位 value。去重本質(zhì)是 HashMap 的 key 不可重復(fù)前提是正確實(shí)現(xiàn) equals/hashCode 且 key 不可變。按只去重 / 去重保序 / 去重排序三檔選 HashSet / LinkedHashSet / TreeSet。