11-HashSet顾腊、TreeSet 源碼解析和面試題(集合)

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

  1. 底層實(shí)現(xiàn)基于 HashMap,所以迭代時(shí)不能保證按照插入順序防泵,或者其它順序進(jìn)行迭代蚀之;
  2. add、remove捷泞、contanins足删、size 等方法的耗時(shí)性能,是不會(huì)隨著數(shù)據(jù)量的增加而增加的锁右,這個(gè)主要跟 HashMap 底層的數(shù)組結(jié)構(gòu)有關(guān)失受,不管數(shù)據(jù)量多大,不考慮 hash 沖突的情況下咏瑟,時(shí)間復(fù)雜度都是 O(1)拂到;
  3. 線程不安全的,如果需要請自行加鎖码泞,或者使用 Collections.synchronizedSet兄旬;
  4. 迭代過程中,如果數(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)如下:

  1. 繼承表示父子類是同一事物,而 Set 和 Map 本來就是想表達(dá)兩種事物党远,所以繼承不妥削解,而且 Java 語法限制,子類只能繼承一個(gè)父類沟娱,后續(xù)難以擴(kuò)展氛驮。
  2. 組合更加靈活,可以任意的組合現(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è)屬性可以看到:

  1. 我們在使用 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茬末;
  2. 如果 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è)方面:

  1. 和 16 比較大小的意思是說,如果給定 HashMap 的初始容量小于 16部逮,就按照 HashMap 的默認(rèn)值 16 初始化,反之則按照給定值初始化掐禁。
  2. 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í)候试和,完全可以參考參考:

  1. 對組合還是繼承的分析和把握;
  2. 對復(fù)雜邏輯進(jìn)行一些包裝,使暴露出去的接口盡量簡單好用昨稼;
  3. 組合其它 api 時(shí),盡量多對組合的 api 多些了解寻行,這樣才能更好的使用 api匾荆;
  4. 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)的兩種思路:

  1. TreeSet 直接使用 TreeMap 的某些功能秀鞭,自己包裝成新的 api扛禽。
  2. 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ù)用思路的原因:

  1. 像 add 這些簡單的方法逼纸,我們直接使用的是思路 1,主要是因?yàn)?add 這些方法實(shí)現(xiàn)比較簡單菠发,沒有復(fù)雜邏輯,所以 TreeSet 自己實(shí)現(xiàn)起來比較簡單滓鸠;
  2. 思路 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é)

  1. HashSet 對組合的 HashMap 類擴(kuò)容的閾值的深入了解和設(shè)計(jì)冒版,值得我們借鑒逞姿;
  2. TreeSet 對 TreeMap 兩種復(fù)用思路,值得我們學(xué)習(xí)滞造,特別是第二種,TreeSet 定義接口規(guī)范挺狰,由 TreeMap 去實(shí)現(xiàn)买窟。

HashSet 和 TreeSet 不會(huì)是面試的重點(diǎn)始绍,但通過以上兩點(diǎn),可以讓我們給面試官一種精益求精的感覺亏推,成為加分項(xiàng)吞杭。

疑問:

  1. HashSet 底層使用 HashMap,如果 hash 算法準(zhǔn)確也可以實(shí)現(xiàn) key 去重吧绢掰;
  2. 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 的容量大小不就行了么末购?

答案:

  1. ...
  2. 因?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 -------------------------------------

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末驶忌,一起剝皮案震驚了整個(gè)濱河市笑跛,隨后出現(xiàn)的幾起案子飞蹂,更是在濱河造成了極大的恐慌,老刑警劉巖妻坝,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件刽宪,死亡現(xiàn)場離奇詭異,居然都是意外死亡嘴秸,警方通過查閱死者的電腦和手機(jī)庇谆,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門族铆,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人哥攘,你說我怎么就攤上這事逝淹。” “怎么了茉兰?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵规脸,是天一觀的道長熊咽。 經(jīng)常有香客問我,道長被因,這世上最難降的妖魔是什么衫仑? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任文狱,我火速辦了婚禮,結(jié)果婚禮上陷虎,老公的妹妹穿的比我還像新娘。我一直安慰自己,他們只是感情好楣富,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布纹蝴。 她就那樣靜靜地躺著,像睡著了一般糠涛。 火紅的嫁衣襯著肌膚如雪兼犯。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天砸脊,我揣著相機(jī)與錄音凌埂,去河邊找鬼诗芜。 笑死,一個(gè)胖子當(dāng)著我的面吹牛孩哑,可吹牛的內(nèi)容都是我干的脐湾。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼愁铺,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了闻鉴?” 一聲冷哼從身側(cè)響起茵乱,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎孟岛,沒想到半個(gè)月后瓶竭,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體督勺,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年斤贰,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了智哀。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡瓷叫,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出送巡,到底是詐尸還是另有隱情摹菠,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布骗爆,位于F島的核電站次氨,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏摘投。R本人自食惡果不足惜煮寡,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望谷朝。 院中可真熱鬧洲押,春花似錦、人聲如沸圆凰。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽专钉。三九已至挑童,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間跃须,已是汗流浹背站叼。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留菇民,地道東北人尽楔。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像第练,于是被迫代替她去往敵國和親阔馋。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容