注:源碼系列文章主要是對某付費(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 -------------------------------------