一、Set 接口（P518）

1. Set 接口基本介紹

（1）無序（添加和取出的順序不一致），沒有索引。
（2）不允許重復元素，所以最多包含一個 null。

2. Set 接口的常用方法

和 List 接口一樣，Set 接口也是 Collection 的子接口，因此，常用方法和 Collection 接口一樣。

3. Set 接口的遍歷方式

同 Collection 的遍歷方式一樣，因為 Set 接口是 Collection 接口的子接口。
（1）可以使用選代器
（2）增強for
（3）不能使用 索引的方式來獲取

二、HashSet（P519）

1. Hashset 的說明

（1）HashSet 實現了 Set 接口。
（2）HashSet 實際上是 HashMap。
（3）可以存放 null 值，但是只能有一個 null。
（4）HashSet 不保證元素是有序的，取決于 hash 后，再確定索引的結果。
（5）不能有重復元素/對象。

2. Hashset底層機制源碼說明（P522）

分析 Hashset 底層是 HashMap，HashMap 底層是（數組+鏈表+紅黑樹）。

public class HashMap_<K, V> {transient Node<K, V>[] table;transient int modCount;transient int size;public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K, V>[] tab;Node<K, V> p;int n, i;// 屬性table為null或table的長度為0，就擴容if ((tab = table) == null || (n = tab.length) == 0) {n = (tab = resize()).length;}// 如果tab[i]為null，表示沒有存放元素，就創建節點并賦值給tab[i]if ((p = tab[i = (n - 1) & hash]) == null) {tab[i] = newNode(hash, key, value, null);} else {Node<K, V> e;K k;// p 和添加元素的hash值相同 并且 （key相同或equals相同），p賦值給eif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) {e = p;}// 鏈表循環比較else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {break;}p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null) {e.value = value;}return oldValue;}}++modCount;if (++size > threshold) {resize();}return null;}int threshold;final float loadFactor = DEFAULT_LOAD_FACTOR;static final int MAXIMUM_CAPACITY = 1 << 30;static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16// 加載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;final Node<K, V>[] resize() {Node<K, V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY) {newThr = oldThr << 1; // double threshold}} else if (oldThr > 0) {newCap = oldThr;} else {// 擴容newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float) newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?(int) ft : Integer.MAX_VALUE);}threshold = newThr;// 初始化數組，并賦值給屬性tableNode<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];table = newTab;return newTab;}Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {return new Node<>(hash, key, value, next);}static class Node<K, V> {final int hash;final K key;V value;Node<K, V> next;Node(int hash, K key, V value, Node<K, V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}}
}

（1）HashSet 底層是 HashMap。
（2）添加一個元素時，先得到 hash 值 --> 會轉成 --> 索引值。
（3）找到存儲數據表 table，看這個索引位置是否已經存放的有元素。
（4）如果沒有，直接加入。
（5）如果有，調用 equals 比較，如果相同，就放棄添加，如果不相同，則添加到最后。
（6）在 Java8 中，如果一條鏈表的元素個數達到 TREEIFY_THRESHOLD（默認是8），并且 table 的大小 >= MIN_TREEIFY_CAPACITY(默認64），就會進行樹化（紅黑樹）。

紅黑樹機制：
（1）HashSet 底層是 HashMap，第一次添加時，table 數組擴容到16，臨界值（threshold）是16，加載因子（loadFactor）是0.75=12。
（2）如果table數組使用到了臨界值12，就會擴容到162=32，新的臨界值就是320.75=24，依次類推。
（3）在Java8中，如果一條鏈表的元素個數到達TREEIFY_THRESHOLD（默認是8），并且table的大小>=MIN_TREEIFY_CAPACITY（默認64）就會進行樹化（紅黑樹），否則仍然采用數組擴容機制。

三、LinkedHashSet （P528）

1. LinkedHashSet 的說明

（1）LinkedHashSet 是 Hashset 的子類。
（2）LinkedHashSet 底層是一個 LinkedHashMap，底層維護了一個 數組+雙向鏈表。
（3）LinkedHashSet 根據元素的 hashCode 值來決定元素的存儲位置，同時使用鏈表維護元素的 次序（圖），這使得元素看起來是以插入順序保存的。
（4）LinkedHashset 不允許添重復元素。

（1）在 LinkedHashSet 中維護了一個 hash 表和雙向鏈表（LinkedHashSet 有 head 和 tail）。
（2）每一個節點有 pre 和 next 屬性，這樣可以形成雙向鏈表。
（3）在添加一個元素時，先求hash值，在求索引，確定該元素在 hashtable 的位置，然后將添加的元素加入到雙向鏈表（如果已經存在，不添加【原則和 hashset 一樣】）。
（4）遍歷 LinkedHashSet 也能確保插入順序和遍歷順序一致。