注：源碼系列文章主要是對某付費(fèi)專欄的總結(jié)記錄粤铭。如有侵權(quán)，請聯(lián)系刪除杂靶。
HashSet梆惯、TreeSet 兩個(gè)類是在 Map 的基礎(chǔ)上組裝起來的類，我們學(xué)習(xí)的側(cè)重點(diǎn)吗垮，主要在于 Set 是如何利用 Map 現(xiàn)有的功能垛吗，來達(dá)成自己的目的的，也就是說如何基于現(xiàn)有功能進(jìn)行創(chuàng)新抱既，然后再看看一些改變的小細(xì)節(jié)职烧。
1 HashSet
1.1 類注釋
- 底層實(shí)現(xiàn)基于 HashMap，所以迭代時(shí)不能保證按照插入順序防泵，或者其它順序進(jìn)行迭代蚀之；
- add、remove捷泞、contanins足删、size 等方法的耗時(shí)性能，是不會(huì)隨著數(shù)據(jù)量的增加而增加的锁右，這個(gè)主要跟 HashMap 底層的數(shù)組結(jié)構(gòu)有關(guān)失受，不管數(shù)據(jù)量多大，不考慮 hash 沖突的情況下咏瑟，時(shí)間復(fù)雜度都是 O(1)拂到；
- 線程不安全的，如果需要請自行加鎖码泞，或者使用
Collections.synchronizedSet兄旬； - 迭代過程中，如果數(shù)據(jù)結(jié)構(gòu)被改變余寥，會(huì)快速失敗的领铐，拋出
ConcurrentModificationException異常。
我們之前也看過 List宋舷、Map 的類注釋绪撵，我們發(fā)現(xiàn) 2、3祝蝠、4 點(diǎn)信息在類注釋中都有提到音诈，所以如果有人問 List、Map绎狭、Set 三者的共同點(diǎn)细溅，那么就可以說說這三點(diǎn)。
1.2 HashSet 是如何組合 HashMap 的
剛才是從類注釋 1 中看到坟岔，HashSet 的實(shí)現(xiàn)是基于 HashMap 的谒兄，在 Java 中，要基于基礎(chǔ)類進(jìn)行創(chuàng)新實(shí)現(xiàn)社付，有兩種方法：
- 繼承基礎(chǔ)類承疲，覆寫基礎(chǔ)類的方法，比如說繼承 HashMap鸥咖，覆寫其 add 方法燕鸽；
- 組合基礎(chǔ)類，通過調(diào)用基礎(chǔ)類的方法啼辣，來復(fù)用基礎(chǔ)類的能力啊研。
HashSet 使用的就是組合 HashMap，其優(yōu)點(diǎn)如下：
- 繼承表示父子類是同一事物，而 Set 和 Map 本來就是想表達(dá)兩種事物党远，所以繼承不妥削解，而且 Java 語法限制，子類只能繼承一個(gè)父類沟娱，后續(xù)難以擴(kuò)展氛驮。
- 組合更加靈活，可以任意的組合現(xiàn)有的基礎(chǔ)類济似，并且可以在基礎(chǔ)類方法的基礎(chǔ)上進(jìn)行擴(kuò)展矫废、編排，而且方法可以任意命名，無需和基礎(chǔ)類的方法名稱保持一致。
我們工作中声怔，如果碰到類似問題汰规，我們的原則也是盡量多用組合，少用繼承。
組合就是把 HashMap 當(dāng)做自己的一個(gè)局部變量，以下是 HashSet 的組合實(shí)現(xiàn)：
// 把 HashMap 組合進(jìn)來，key 是 HashSet 的 key俩功，value 是下面的 PRESENT
private transient HashMap<E,Object> map;
// HashMap 中的 value
private static final Object PRESENT = new Object();
從這兩個(gè)屬性可以看到：
- 我們在使用 HashSet 時(shí)，比如 add 方法碰声，只有一個(gè)入?yún)⒐铗眩M合的 Map 的 add 方法卻有 key、value 兩個(gè)入?yún)⒙＃鄬?yīng)上 Map 的 key 就是我們 add 的入?yún)⒄八蹋瑅alue 就是第二個(gè)屬性 PRESENT，此處設(shè)計(jì)非常巧妙贡这，用一個(gè)默認(rèn)值 PRESENT 來代替 Map 的 value茬末；
- 如果 HashSet 是被共享的，當(dāng)多個(gè)線程訪問的時(shí)候盖矫，就會(huì)有線程安全問題，因?yàn)樵诤罄m(xù)的所有操作中责掏，并沒有加鎖。
HashSet 在以 HashMap 為基礎(chǔ)進(jìn)行實(shí)現(xiàn)的時(shí)候湃望，首先選擇組合的方式换衬，接著使用默認(rèn)值來替代 Map 的 value 值痰驱，設(shè)計(jì)的非常巧妙瞳浦，給使用者的體驗(yàn)很好，使用起來簡單方便另萤，我們在工作中也可以借鑒這種思想诅挑，可以把底層復(fù)雜實(shí)現(xiàn)包裝一下泛源，一些默認(rèn)實(shí)現(xiàn)可以自己吃掉拔妥，使吐出去的接口盡量簡單好用达箍。
1.2.1 初始化
HashSet 的初始化比較簡單缎玫，直接 new HashMap 即可，比較有意思的是赃磨，當(dāng)有原始集合數(shù)據(jù)進(jìn)行初始化的情況下，會(huì)對 HashMap 的初始容量進(jìn)行計(jì)算溪王，源碼如下：
public HashSet(Collection<? extends E> c) {
// 對 HashMap 的容量重新進(jìn)行了計(jì)算
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
源碼中 Math.max((int) (c.size()/.75f) + 1, 16)值骇，就是對 HashMap 的容量進(jìn)行了計(jì)算，從計(jì)算中道伟，我們可以看到 HashSet 的實(shí)現(xiàn)者對 HashMap 的底層實(shí)現(xiàn)是非常清楚的使碾，主要體現(xiàn)在兩個(gè)方面：
- 和 16 比較大小的意思是說，如果給定 HashMap 的初始容量小于 16部逮，就按照 HashMap 的默認(rèn)值 16 初始化，反之則按照給定值初始化掐禁。
- HashMap 擴(kuò)容的閾值
threshold的計(jì)算公式是：capacity * loadFactor，一旦達(dá)到閾值就會(huì)擴(kuò)容傅事，此處用(int)(c.size()/.75f) + 1來表示初始化的值，這樣使我們期望的大小值正好比擴(kuò)容的閾值還大 1蹭越，就不會(huì)擴(kuò)容障本，符合 HashMap 擴(kuò)容的公式响鹃。
從簡單的構(gòu)造器中，我們可以看出要很好的組合 api 接口粪糙，并沒有那么簡單忿项，我們可能需要去了解一下被組合的 api 底層的實(shí)現(xiàn)，這樣才能用好 api寞酿。
同時(shí)這種寫法脱柱，也提供了一種思路給我們，如果有人問你褐捻，往 HashMap 拷貝大集合時(shí)，如何給 HashMap 初始化大忻潦ā板壮？完全可以借鑒這種寫法：取最大值（期望的值 / 0.75 + 1, 默認(rèn)值 16）。
至于 HashSet 的其它方法就比較簡單了撒璧，就是對 Map 的 api 進(jìn)行了一些包裝笨使，如下的 add 方法實(shí)現(xiàn)：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
從 add 方法中，我們可以看到組合的好處繁调，方法的入?yún)ⅰ⒚Q岳遥、返回值都可以自定義裕寨，如果是繼承的話就不行了。
1.2.2 小結(jié)
HashSet 具體實(shí)現(xiàn)值得我們借鑒的地方主要有以下這些捻艳，我們平時(shí)寫代碼的時(shí)候试和，完全可以參考參考：
- 對組合還是繼承的分析和把握；
- 對復(fù)雜邏輯進(jìn)行一些包裝，使暴露出去的接口盡量簡單好用昨稼；
- 組合其它 api 時(shí)，盡量多對組合的 api 多些了解寻行，這樣才能更好的使用 api匾荆；
- HashMap 初始化大小值的模板公式：
取括號(hào)內(nèi)兩者的最大者（期望的大小 / 0.75 + 1, 默認(rèn)的值 16）。
2 TreeSet
TreeSet 大致的結(jié)構(gòu)和 HashSet 相似简卧，底層組合的是 TreeMap烤芦，所以繼承了 TreeMap key 能夠排序的功能，迭代的時(shí)候铜涉，也可以按照 key 的順序進(jìn)行迭代遂唧，我們主要來看看復(fù)用 TreeMap 時(shí)，復(fù)用的兩種思路：
2.1 復(fù)用 TreeMap 的思路一
場景一：TreeSet 的 add 方法纹烹，源碼：
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
可以看到，底層直接使用的是 TreeMap 的能力逻谦，直接拿來用就好了陪蜻。
2.2 復(fù)用 TreeMap 的思路二
場景二：需要迭代 TreeSet 中的元素，那應(yīng)該也是像 add 那樣滋将，直接使用 HashMap 已有的迭代能力症昏，比如像下面這樣：
// 模仿思路一的實(shí)現(xiàn)
public Iterator<E> iterator() {
// 直接使用 TreeMap.keySet 的能力
return m.keySet().iterator();
}
這種是思路一的實(shí)現(xiàn)方式，TreeSet 組合 TreeMap掘宪，直接選擇 TreeMap 的底層能力進(jìn)行包裝攘烛，但 TreeSet 實(shí)際執(zhí)行的思路卻完全相反，源碼：
// NavigableSet 接口鼠次，定義了迭代的一些規(guī)范芋齿，和一些取值的特殊方法
public interface NavigableSet<E> extends SortedSet<E> {
Iterator<E> iterator();
E lower(E e);
}
// m.navigableKeySet() 是 TreeMap 寫的一個(gè)子類實(shí)現(xiàn)了 NavigableSet 接口，實(shí)現(xiàn)了 TreeSet 定義的迭代規(guī)范
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
TreeMap 中對于 NavigableSet 接口實(shí)現(xiàn)的源碼如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
.....
static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
private final NavigableMap<E, ?> m;
KeySet(NavigableMap<E,?> map) { m = map; }
public Iterator<E> iterator() {
if (m instanceof TreeMap)
return ((TreeMap<E,?>)m).keyIterator();
else
return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
}
public Iterator<E> descendingIterator() {
if (m instanceof TreeMap)
return ((TreeMap<E,?>)m).descendingKeyIterator();
else
return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
}
.....
}
}
可以看出 TreeMap 實(shí)現(xiàn)了 TreeSet 定義的各種特殊方法赦役。
我們可以看到扩劝，這種思路是 TreeSet 定義了接口的規(guī)范职辅，TreeMap 負(fù)責(zé)去實(shí)現(xiàn)，實(shí)現(xiàn)思路和思路一是相反的域携。
總結(jié) TreeSet 組合 TreeMap 實(shí)現(xiàn)的兩種思路：
- TreeSet 直接使用 TreeMap 的某些功能秀鞭，自己包裝成新的 api扛禽。
- TreeSet 定義了自己想要的 api皱坛，自己定義接口規(guī)范，讓 TreeMap 去實(shí)現(xiàn)掐场。
方案 1 和方案 2 的調(diào)用關(guān)系贩猎，都是 TreeSet 調(diào) TreeMap，但功能的實(shí)現(xiàn)關(guān)系完全相反嚷堡，第一種是功能的定義和實(shí)現(xiàn)都在 TreeMap艇棕，TreeSet 只是簡單的調(diào)用而已，第二種 TreeSet 把接口定義出來后瓶颠，讓 TreeMap 去實(shí)現(xiàn)內(nèi)部邏輯刺桃，TreeSet 負(fù)責(zé)接口定義吸祟，TreeMap 負(fù)責(zé)具體實(shí)現(xiàn)，這樣子的話因?yàn)榻涌谑?TreeSet 定義的葛碧，所以實(shí)現(xiàn)一定是 TreeSet 最想要的过吻，TreeSet 甚至都不用包裝，可以直接把返回值直接返回都行乳绕。
我們思考下這兩種復(fù)用思路的原因：
- 像 add 這些簡單的方法逼纸，我們直接使用的是思路 1，主要是因?yàn)?add 這些方法實(shí)現(xiàn)比較簡單菠发，沒有復(fù)雜邏輯，所以 TreeSet 自己實(shí)現(xiàn)起來比較簡單滓鸠；
- 思路 2 主要適用于復(fù)雜場景糜俗，比如說迭代場景踱稍，TreeSet 的場景復(fù)雜吩跋，比如要能從頭開始迭代，比如要能取第一個(gè)值桥温，比如要能取最后一個(gè)值梁丘，再加上 TreeMap 底層數(shù)據(jù)結(jié)構(gòu)復(fù)雜，TreeSet 可能并不清楚 TreeMap 底層的復(fù)雜邏輯掏觉，這時(shí)候讓 TreeSet 來實(shí)現(xiàn)如此復(fù)雜的場景邏輯值漫，TreeSet 就搞不定了杨何，不如接口讓 TreeSet 來定義，讓 TreeMap 去負(fù)責(zé)實(shí)現(xiàn)危虱，TreeMap 對自己底層的數(shù)據(jù)結(jié)構(gòu)非常清楚，實(shí)現(xiàn)起來既準(zhǔn)確又簡單蕊玷。
2.3 小結(jié)
TreeSet 對 TreeMap 的兩種不同復(fù)用思路弥雹，很重要缅糟，在工作中經(jīng)常會(huì)遇到，特別是思路二。
3 面試題
HashSet 和 TreeSet 的面試概率比不上 List 和 Map二鳄，但只要有機(jī)會(huì)媒怯，并把本文的內(nèi)容表達(dá)出來，絕對是加分項(xiàng)欺殿，因?yàn)楝F(xiàn)在 List 和 Map 面試題太多鳖敷，面試官認(rèn)為你能答出來是應(yīng)該的，但只要你有機(jī)會(huì)對 HashSet 和 TreeSet 說出本文的見解定踱，并且說自己是看源碼時(shí)領(lǐng)悟的，絕對肯定是加分項(xiàng)亦歉，這些就是你超過面試官預(yù)期的驚喜畅哑。
3.1 TreeSet 有用過么，平時(shí)都是在什么場景下使用的赛蔫？
答：有沒有用過如實(shí)回答就好泥张，我們一般都是在需要把元素進(jìn)行排序的時(shí)候使用 TreeSet，使用時(shí)需要注意元素最好實(shí)現(xiàn) Comparable 接口圾结，這樣方便底層 TreeMap 根據(jù) key 進(jìn)行排序齿诉。
3.2 追問粤剧，如果我想實(shí)現(xiàn)根據(jù) key 的新增順序進(jìn)行遍歷怎么辦？
答：要按照 key 的新增順序進(jìn)行遍歷焕议，首先想到的就應(yīng)該是 LinkedHashMap弧关，而 LinkedHashSet 正好是基于 LinkedHashMap 實(shí)現(xiàn)的唤锉，所以我們可以選擇使用 LinkedHashSet别瞭。
3.3 追問，如果我想對 key 進(jìn)行去重晒衩，有什么好的辦法墙歪？
答：首先想到的是 TreeSet虹菲，TreeSet 底層使用的是 TreeMap，TreeMap 在 put 的時(shí)候届惋，如果發(fā)現(xiàn) key 是相同的脑豹，會(huì)把 value 值進(jìn)行覆蓋，所以不會(huì)產(chǎn)生重復(fù)的 key瘩欺，利用這一特性俱饿，使用 TreeSet 正好可以去重。
3.4 說說 TreeSet 和 HashSet 兩個(gè) Set 的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)原理失驶？
答：HashSet 底層對 HashMap 的能力進(jìn)行了封裝枣购，比如 add 方法就是直接使用 HashMap 的 put 方法，比較簡答涩堤。說一下 HashSet 的四個(gè)小結(jié)點(diǎn)分瘾。
TreeSet 主要是對 TreeMap 底層能力進(jìn)行封裝復(fù)用，發(fā)現(xiàn)兩種非常有意思的復(fù)用思路白魂，重復(fù) TreeSet 兩種復(fù)用思路。
總結(jié)
- HashSet 對組合的 HashMap 類擴(kuò)容的閾值的深入了解和設(shè)計(jì)冒版，值得我們借鑒逞姿；
- TreeSet 對 TreeMap 兩種復(fù)用思路，值得我們學(xué)習(xí)滞造，特別是第二種，TreeSet 定義接口規(guī)范挺狰，由 TreeMap 去實(shí)現(xiàn)买窟。
HashSet 和 TreeSet 不會(huì)是面試的重點(diǎn)始绍，但通過以上兩點(diǎn)，可以讓我們給面試官一種精益求精的感覺亏推，成為加分項(xiàng)吞杭。
疑問：
- HashSet 底層使用 HashMap，如果 hash 算法準(zhǔn)確也可以實(shí)現(xiàn) key 去重吧绢掰；
- HashSet 帶集合數(shù)據(jù)初始化時(shí)童擎，初始化 HashMap 時(shí)對擴(kuò)容閾值的計(jì)算
Math.max((int) (c.size()/.75) + 1, 16)，這里為何不使用 HashMap 的tableSizeFor(c.size)計(jì)算呢？例如我拷貝 1000 長度的集合捕透，我知道我最終的目標(biāo)長度就是 1000，那我使用 tableSizeFor(1000) 的到大于 1000 并且最接近 1000 的 2 的冪次方的值作為 HashMap 的容量大小不就行了么末购？
答案：
- ...
- 因?yàn)?HashMap 擴(kuò)容的條件是
size > threshold(負(fù)載因子)虎谢，這里我們拷貝的最大 size 為 1000，如果考慮每次都不必?cái)U(kuò)容擎场，那么 threshold 最小值應(yīng)該為 1000几莽，而負(fù)載因子的計(jì)算公式為：threshold = capacity * loadFactor，帶入?yún)?shù)為：1000 = capacity * 0.75站欺，所以capacity = 1000 / 0.75纤垂，也就是：我們期望的容量值 = c.size()/0.75，源碼中(int) (c.size()/.75) + 1來表示初始化的值贾虽，這樣使我們期望的大小值正好比擴(kuò)容的閾值大 1榄鉴，就不會(huì)擴(kuò)容蛉抓，符合 HashMap 擴(kuò)容的公式。
------------------------------------- END -------------------------------------
