1. Set介面基本介紹

1. Set是無序集合（添加和取出的順序不一致，但取出的順序是固定的），沒有索引
2. 不允許重覆元素，所以最多包含一個null
3. JDK API中Set介面的實現類有：
   Abstract, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet

1.1 Set介面的常用方法

Set介面和List介面一樣，都是Collection的子介面，因此常用方法和Collection介面一樣

1.2 Set介面的遍歷方法

同Collection的遍歷方式一樣，因為Set介面是Collection介面的子介面。

1. 可以使用迭代器
2. 增強for迴圈
3. 不能使用索引的方式來獲取

2 HashSet

2.1 HashSet的全面說明

1. HashSet實現了Set介面，類定義如下：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

2. HashSet實際上是HashMap，HashSet的無參構造函數如下：

public HashSet() {
    map = new HashMap<>();
}

3. 可以存放null值，但因為不能重覆，所以只能存放一個null
4. HashSet不保證元素是有序的，取決於hash之後，在確定索引的結果，也因此取出順序是固定的
5. 不能有重覆元素/對象。

2.2 有關重覆元素的經典問題

//定義一個類
class Dog{
    private String name;
    public Dog(String name){
        this.name = name;
    }
}
//定義一個HashSet
Set<Object> set = new HashSet<>();
set.add(new Dog("dog"));
set.add(new Dog("dog"));
System.out.println(set);

兩個dog都能添加成功！前面不是說不能有重覆元素嗎？事實上，HashSet判斷元素是否重覆依靠的是HashCode，而上面的代碼並沒有重寫HashCode和equals方法，導致HashSet在判斷兩個Dog對象是否重覆時，是以地址為依據判斷的，而兩個對象實例其在堆上的記憶體必然是不一樣的，因此他們兩個被認為是不同的實例。
相同的問題使用String再來驗證一下：

set.add("john");
set.add("john");
System.out.println(set);

毫無疑問地添加失敗了，這是因為"john"被放在了常量池中，地址不變了嗎？

set.add(new String("john"));
set.add(new String("john"));
System.out.println(set);

結果仍然添加失敗，這兩個String對象的記憶體地址不同，卻仍被準確識別為重覆元素，是因為String類重寫了HashCode和equals方法，HashSet在判斷過程中比較的是二者的內容是否一致，而不再是地址了

2.3 HashSet底層機制說明

HashSet底層是HashMap，HashMap底層是(數組+鏈表+紅黑樹)
HashSet添加元素的操作(hash()+equals()):

1. HashSet底層是HashMap
2. 添加一個元素是，先得到hash值，會轉成索引值
3. 找到存儲數據表table，看這個索引位置是否已經存放的有元素
4. 如果沒有，直接加入
5. 如果有，調用equals比較內容，如果相同，就放棄添加，如果不相同，則添加到最後，形成鏈表
6. 在Java8中，如果一條鏈表的元素個數超過TREEIFY_THRESHOLD(預設是8),並且table的大小 >= MIN_TRESHOLD_CAPACITY(預設是64)，就會進行樹化(紅黑樹)
7. HashSet底層的HashMap，第一次添加時，table數組擴容到16，臨界值(threshold)是16*0.75(載入因數, loadFactor) = 12;
8. 如果table數組使用到了臨界值12，或者某條單鏈長度超過8，就會擴容到16*2 = 32，新的臨界值就是32*0.75 = 24。以此類推
9. 在Java8中，如果一條鏈表的元素個數達到TREE_THRESHOLD(預設是8),並且table的大小>=MIN_TREEIFY_CAPACITY(預設是64)，就會進行樹化(紅黑樹)，否則仍然採用數組擴容機制
10. 臨界值比較的是table中的所有節點個數，不論這個節點是直接存儲在table中，還是附加在某一條鏈表後
11. 如果table沒有達到64，而單鏈長度超過8，會立即觸發擴容，並且每次檢測到超長都會觸發一次擴容，即使沒有達到threshold，直到table長度達到64後，觸發樹化

2.4 set.add()調用過程

    HashSet<Object> set = new HashSet<>();
    set.add("john");

以上代碼的調用過程如下圖：

2.4 set.add()調用過程

    HashSet<Object> set = new HashSet<>();
    set.add("john");

以上代碼的調用過程如下圖：

圖中標註了調用順序和返回順序
其中，最關鍵的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)詳細分解如下：

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        //定義了一些輔助變數，table就是HashMap的一個數組，類型是Node[]
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //if語句表示如果當前table是null，或者length==0，就第一次擴容到16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(1) 根據key得到Hash,去計算該key應該存放到table的那個索引位置，並把這個位置的對象賦給p
        //(2) 判斷p是否為null
        //(2.1) 如果p為null,表示該位置還沒有存放過元素,即沒有發生哈希衝突，就創建一個Node(key="java",value=PRESENT)，
        //      就放在該位置 tab[i] = new Node(hash,key,value,null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

            //(2.2) 如果p不為null,表示該位置已經存放過元素，即發生了哈希碰撞，
        else {
            //定義了一些輔助變數。一個開發技巧的提示：在需要的局部變數(輔助變數)時再創建
            Node<K,V> e; K k;
            //(2.2.1) 如果當前索引位置對應的鏈表的第一個元素和準備添加的key的hash值一樣，並且滿足下麵兩個條件之一，就認為傳入了重覆元素，不能加入
            // 條件一： 準備加入的key和 p指向的Node節點的key是同一個對象
            // 條件二： 調用equals()方法比較二者，結果為ture，即認為他們內容相同，註意，這裡的equals()方法是程式員定義的，不是單純的比較內容
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //再判斷p是不是一棵紅黑樹，如果是一顆紅黑樹，就調用putTreeVal()來添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            else {
                //如果table對應索引位置已經是一個鏈表，就用for迴圈比較
                for (int binCount = 0; ; ++binCount) {
                    //(1) 依次和鏈表的每一個元素比較後，都不相同，將該元素添加至該鏈表最後
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在把元素添加到鏈表後，立即判斷該鏈表長度是否超過8個節點，如果是，就嘗試將該鏈表轉化為紅黑樹
                        //在進行樹化時，還有一層判斷：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
                        //如果if條件成立，就會先對table擴容；如果不成立，在轉化成紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //(2) 如果比較過程中發現重覆元素，退出返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;  //每次比較後，指針後移
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);//該方法是HashMap留給子類實現的方法，對於HashMap來說，是一個空方法
        return null;//返回null代表成功，否則會在前面的return語句中返回當前索引指向的對象
    }