• 面試官：你說說對HashSet的理解？
• 面試官：LinkedHashSet呢？
• 面試官：TreeSet和它們比有什么特性？
• 面試官：那TreeSet要怎么定制排序？

大家好，我是南哥。

一個Java學(xué)習(xí)與進階的領(lǐng)路人，相信對你通關(guān)面試進入心心念念的公司有所幫助。

文章目錄

1. Set集合
   1. HashSet
   2. LinkedHashSet
   3. TreeSet
   4. TreeSet自定義排序

1. Set集合

1.1 HashSet

面試官：你說說對HashSet的理解？

Set集合區(qū)別于其他三大集合的重要特性就是元素具有唯一性，南友們記不住這個特性的話，有個易記的方法。Set集合為什么要叫Set呢？因為Set集合的命名取自于我們小學(xué)數(shù)學(xué)里的集合論（Set Theory），數(shù)學(xué)集合一個很重要的概念就是每個元素的值都互不相同。

Set集合常見的有實例有：HashSet、LinkedHashSet、TreeSet，南哥先縷一縷HashSet。

// HashSet類源碼
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {...}

HashSet底層實現(xiàn)其實是基于HashMap，HashMap的特點就是Key具有唯一性，這一點被HashSet利用了起來，每一個HashMap的Key對應(yīng)的就是HashSet的元素值。來看看官方源碼的解釋。

此類實現(xiàn)Set接口，由哈希表（實際上是HashMap實例）支持。它不保證集合的迭代順序；特別是，它不保證順序隨時間保持不變。此類允許null元素。

我們創(chuàng)建一個HashSet對象，實際上底層創(chuàng)建了一個HashMap對象。

    // HashSet構(gòu)造方法源碼
    public HashSet() {
        map = new HashMap<>();
    }

HashSet一共提供了以下常用方法，不得不說HahSet在業(yè)務(wù)開發(fā)中還是用的沒那么多的，南哥在框架源碼上看HashSet用的就比較多，比如由Java語言實現(xiàn)的zookeeper框架源碼。

（1）添加元素

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

我們看上面add方法的源碼，是不是調(diào)用了HashMap的put方法呢？而put方法添加的Key是HashSet的值，Val則是一個空的Object對象。PRESENT是這么定義的。

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

（2）判斷元素是否存在

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

HashSet的contains方法同樣是調(diào)用HashMap判斷Key是否存在的方法：containsKey。

（3）移除元素

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

1.2 LinkedHashSet

面試官：LinkedHashSet呢？

接著輪到LinkedHashSet，同為Set集合之一，它和上文的HashSet有什么區(qū)別？南哥賣個關(guān)子。

源碼對LinkedHashSet的解釋。

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

源碼的大概意思就是：Set接口的哈希表和鏈表實現(xiàn)，具有可預(yù)測的迭代順序。此實現(xiàn)與HashSet的不同之處在于，它維護一個貫穿其所有條目的雙向鏈表。此鏈表定義迭代順序，即**元素插入集合的順序 (**插入順序)。

底層數(shù)據(jù)結(jié)構(gòu)是一條雙向鏈表，每個元素通過指針進行相連，也就有了按插入順序排序的功能。

知道了LinkedHashSet的特性，看看他的構(gòu)造方法。

    /**
     * 構(gòu)造一個新的、空的鏈接哈希集，具有默認(rèn)初始容量（16）和負(fù)載因子（0.75）。
     */
    public LinkedHashSet() {
        super(16, .75f, true);
    }

這個方法向上調(diào)用了底層C語言源碼實現(xiàn)的LinedHashMap