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

/**
 * 模擬 HashSet 數(shù)組+鏈表的結(jié)構(gòu)
 */
public class HashSetStructureMain {
    public static void main(String[] args) {
        // 模擬一個(gè) HashSet(HashMap) 的底層結(jié)構(gòu)
        // 1. 創(chuàng)建一個(gè)數(shù)組，數(shù)組的類型為 Node[]
        // 2. 有些地方直接把 Node[] 數(shù)組稱為 表
        Node[] table = new Node[16];
        System.out.println(table);
        // 3. 創(chuàng)建節(jié)點(diǎn)
        Node john = new Node("john", null);
        table[2] = jhon; // 把節(jié)點(diǎn) john 放在數(shù)組索引為 2 的位置
        Node jack = new Node("jack", null);
        jhon.next = jack; // 將 jack 掛載到 jhon 的后面
        Node rose = new Node("rose", null);
        jack.next = rose; // 將 rose 掛載到 jack 的后面
        Node lucy = new Node("lucy", null);
        table[3] = lucy; // 將 lucy 放在數(shù)組索引為 3 的位置
        System.out.println(table);

    }
}

// 節(jié)點(diǎn)類 存儲(chǔ)數(shù)據(jù)，可以指向下一個(gè)節(jié)點(diǎn)，從而形成鏈表
class Node{
    Object item; // 存放數(shù)據(jù)
    Node next; // 指向下一個(gè)節(jié)點(diǎn)
    public Node(Object item, Node next){
        this.item = item;
        this.next = next;
    }
}

/**
 * HashSet 源碼分析
 */
public class HashSetSourceMain {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println("set = " + hashSet);

        // 源碼分析
        // 1. 執(zhí)行 HashSet()
        /**
         * public HashSet() { // HashSet 底層是 HashMap
         *         map = new HashMap<>();
         *     }
         */

        // 2. 執(zhí)行 add()
        /**
         * public boolean add(E e) { // e == "java"
         *         // HashSet 的 add() 方法其實(shí)是調(diào)用 HashMap 的 put()方法
         *         return map.put(e, PRESENT)==null; // (static) PRESENT = new Object(); 用于占位
         *     }
         */

        // 3. 執(zhí)行 put()
        // hash(key) 得到 key(待存元素) 對(duì)應(yīng)的hash值，并不等于 hashcode()
        // 算法是 h = key.hashCode()) ^ (h >>> 16
        /**
         * public V put(K key, V value) {
         *         return putVal(hash(key), key, value, false, true);
         *     }
         */

        // 4. 執(zhí)行 putVal()
        // 定義的輔助變量：Node<K,V>[] tab; Node<K,V> p; int n, i;
        // table 是 HashMap 的一個(gè)屬性，初始化為 null；transient Node<K,V>[] table;
        // resize() 方法，為 table 數(shù)組指定容量
        // p = tab[i = (n - 1) & hash] 計(jì)算 key的hash值所對(duì)應(yīng)的 table 中的索引位置，將索引位置對(duì)應(yīng)的 Node 賦給 p
        /**
         * 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 就是 HashMap 的一個(gè)屬性，類型是 Node[]
         *         // if 語(yǔ)句表示如果當(dāng)前 table 是 null，或者 table.length == 0
         *         // 就是 table 第一次擴(kuò)容，容量為 16
         *         if ((tab = table) == null || (n = tab.length) == 0)
         *             n = (tab = resize()).length;
         *         // 1. 根據(jù) key，得到 hash 去計(jì)算key應(yīng)該存放到 table 的哪個(gè)索引位置
         *         // 2. 并且把這個(gè)位置的索引值賦給 i；索引值對(duì)應(yīng)的元素，賦給 p
         *         // 3. 判斷 p 是否為 null
         *         // 3.1 如果 p 為 null，表示還沒(méi)有存放過(guò)元素，就創(chuàng)建一個(gè)Node(key="java",value=PRESENT)，并把這個(gè)元素放到 i 的索引位置
         *         // tab[i] = newNode(hash, key, value, null);
         *         if ((p = tab[i = (n - 1) & hash]) == null)
         *             tab[i] = newNode(hash, key, value, null);
         *         else {
         *             Node<K,V> e; K k; // 輔助變量
         *             // 如果當(dāng)前索引位置對(duì)應(yīng)的鏈表的第一個(gè)元素和待添加的元素的 hash值一樣
         *             // 并且滿足下面兩個(gè)條件之一：
         *             // 1. 待添加的 key 與 p 所指向的 Node 節(jié)點(diǎn)的key 是同一個(gè)對(duì)象
         *             // 2. 待添加的 key.equals(p 指向的 Node 節(jié)點(diǎn)的 key) == true
         *             // 就認(rèn)為當(dāng)前待添加的元素是重復(fù)元素，添加失敗
         *             if (p.hash == hash &&
         *                 ((k = p.key) == key || (key != null && key.equals(k))))
         *                 e = p;
         *             // 判斷 當(dāng)前 p 是不是一顆紅黑樹
         *             // 如果是一顆紅黑樹，就調(diào)用 putTreeVal，來(lái)進(jìn)行添加
         *             else if (p instanceof TreeNode)
         *                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         *             else {
         *                  // 如果 當(dāng)前索引位置已經(jīng)形成一個(gè) 鏈表，就使用 for 循環(huán)比較
         *                  // 將待添加元素依次和鏈表上的每個(gè)元素進(jìn)行比較
         *                  // 1. 比較過(guò)程中如果出現(xiàn)待添加元素和鏈表中的元素有相同的，比較結(jié)束，出現(xiàn)重復(fù)元素，添加失敗
         *                  // 2. 如果比較到鏈表最后一個(gè)元素，鏈表中都沒(méi)出現(xiàn)與待添加元素相同的，就把當(dāng)前待添加元素放到該鏈表最后的位置
         *                  // 注意：在把待添加元素添加到鏈表后，立即判斷 該鏈表是否已經(jīng)到達(dá) 8 個(gè)節(jié)點(diǎn)
         *                  // 如果到達(dá)，就調(diào)用 treeifyBin() 對(duì)當(dāng)前這個(gè)鏈表進(jìn)行數(shù)化(轉(zhuǎn)成紅黑樹)
         *                  // 注意：在轉(zhuǎn)成紅黑樹前，還要進(jìn)行判斷
         *                  // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         *                  //        resize();
         *                  // 如果上面條件成立，先對(duì) table 進(jìn)行擴(kuò)容
         *                  // 如果上面條件不成立，才轉(zhuǎn)成紅黑樹
         *                 for (int binCount = 0; ; ++binCount) {
         *                     if ((e = p.next) == null) {
         *                         p.next = newNode(hash, key, value, null);
         *                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
         *                             treeifyBin(tab, hash);
         *                         break;
         *                     }
         *                     if (e.hash == hash &&
         *                         ((k = e.key) == key || (key != null && key.equals(k))))
         *                         break;
         *                     p = e;
         *                 }
         *             }
         *             // e 不為 null ，說(shuō)明添加失敗
         *             if (e != null) { // existing mapping for key
         *                 V oldValue = e.value;
         *                 if (!onlyIfAbsent || oldValue == null)
         *                     e.value = value;
         *                 afterNodeAccess(e);
         *                 return oldValue;
         *             }
         *         }
         *         ++modCount;
         *         // 擴(kuò)容：說(shuō)明判斷 table 是否擴(kuò)容不是看 table 的length
         *         // 而是看 整個(gè) HashMap 的 size(即已存元素個(gè)數(shù))
         *         if (++size > threshold)
         *             resize();
         *         afterNodeInsertion(evict);
         *         return null;
         *     }
         */
    }
}

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

public final Iterator<K> iterator()     { return new KeyIterator(); }

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

/**
*         Node<K,V> next;        // next entry to return
*         Node<K,V> current;     // current entry
*         int expectedModCount;  // for fast-fail
*         int index;             // current slot
* HashIterator() {
*             expectedModCount = modCount;
*             Node<K,V>[] t = table;
*             current = next = null;
*             index = 0;
*             if (t != null && size > 0) { // advance to first entry
*                 do {} while (index < t.length && (next = t[index++]) == null);
*             }
*         }
*/

public final boolean hasNext() {
    return next != null;
}

/**
 * HashSet 源碼分析
 */
public class HashSetSourceMain {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println("set = " + hashSet);
        // HashSet 迭代器實(shí)現(xiàn)原理
        // HashSet 底層是 HashMap，HashMap 底層是 數(shù)組 + 鏈表 + 紅黑樹
        // HashSet 本身沒(méi)有實(shí)現(xiàn)迭代器，而是借由 HashMap 來(lái)實(shí)現(xiàn)的
        // 1. hashSet.iterator() 實(shí)際上是去調(diào)用 HashMap 的 keySet().iterator()
        /**
         * public Iterator<E> iterator() {
         *         return map.keySet().iterator();
         *     }
         */
        // 2. KeySet() 方法返回一個(gè) KeySet 對(duì)象，而 KeySet 是 HashMap 的一個(gè)內(nèi)部類
        /**
         * public Set<K> keySet() {
         *         Set<K> ks = keySet;
         *         if (ks == null) {
         *             ks = new KeySet();
         *             keySet = ks;
         *         }
         *         return ks;
         *     }
         */
        // 3. KeySet().iterator() 方法返回一個(gè) KeyIterator 對(duì)象，KeyIterator 是 HashMap的一個(gè)內(nèi)部類
        /**
         * public final Iterator<K> iterator()     { return new KeyIterator(); }
         */
        // 4. KeyIterator 繼承了 HashIterator(HashMap的內(nèi)部類) 類，并實(shí)現(xiàn)了 Iterator 接口
        // 即 KeyIterator、HashIterator 才是真正實(shí)現(xiàn) 迭代器的類
        /**
         * final class KeyIterator extends HashIterator
         *         implements Iterator<K> {
         *         public final K next() { return nextNode().key; }
         *     }
         */
        // 5. 當(dāng)執(zhí)行完 Iterator iterator = hashSet.iterator(); 后
        // 此時(shí)的 iterator 對(duì)象中已經(jīng)存儲(chǔ)了一個(gè)元素節(jié)點(diǎn)
        // 怎么做到的？
        // 回到第 3 步，KeySet().iterator() 方法返回一個(gè) KeyIterator 對(duì)象
        // new KeyIterator() 調(diào)用 KeyIterator 的無(wú)參構(gòu)造器
        // 在這之前，會(huì)先調(diào)用 KeyIterator 父類 HashIterator 的無(wú)參構(gòu)造器
        // 因此分析 HashIterator 的無(wú)參構(gòu)造器就知道發(fā)生了什么
        /**
         *         Node<K,V> next;        // next entry to return
         *         Node<K,V> current;     // current entry
         *         int expectedModCount;  // for fast-fail
         *         int index;             // current slot
         * HashIterator() {
         *             expectedModCount = modCount;
         *             Node<K,V>[] t = table;
         *             current = next = null;
         *             index = 0;
         *             if (t != null && size > 0) { // advance to first entry
         *                 do {} while (index < t.length && (next = t[index++]) == null);
         *             }
         *         }
         */
        // 5.0 next, current, index 都是 HashIterator 的屬性
        // 5.1 Node<K,V>[] t = table; 先把 Node 數(shù)組 table 賦給 t
        // 5.2 current = next = null; 把 current 和 next 都置為 null
        // 5.3 index = 0; index 置為 0
        // 5.4 do {} while (index < t.length && (next = t[index++]) == null);
        // 這個(gè) do{} while 循環(huán)會(huì)在 table 中 遍歷 Node節(jié)點(diǎn)
        // 一旦 (next = t[index++]) == null 不成立時(shí)，就說(shuō)明找到了一個(gè) table 中的節(jié)點(diǎn)
        // 將這個(gè)節(jié)點(diǎn)賦給 next，并退出當(dāng)前 do while循環(huán)
        // 此時(shí) Iterator iterator = hashSet.iterator(); 就執(zhí)行完了
        // 當(dāng)前 iterator 的運(yùn)行類型其實(shí)是 HashIterator，而 HashIterator 的 next 中存儲(chǔ)著從 table 中遍歷出來(lái)的一個(gè) Node節(jié)點(diǎn)
        // 6. 執(zhí)行 iterator.hasNext()
        /**
         * public final boolean hasNext() {
         *             return next != null;
         *         }
         */
        // 6.1 此時(shí)的 next 存儲(chǔ)著一個(gè) Node，所以并不為 null，返回 true
        // 7. 執(zhí)行 iterator.next()，其實(shí)是去執(zhí)行 HashIterator 的 nextNode()
        /**
         * final Node<K,V> nextNode() {
         *             Node<K,V>[] t;
         *             Node<K,V> e = next;
         *             if (modCount != expectedModCount)
         *                 throw new ConcurrentModificationException();
         *             if (e == null)
         *                 throw new NoSuchElementException();
         *             if ((next = (current = e).next) == null && (t = table) != null) {
         *                 do {} while (index < t.length && (next = t[index++]) == null);
         *             }
         *             return e;
         *         }
         */
        // 7.1 Node<K,V> e = next; 把當(dāng)前存儲(chǔ)著 Node 節(jié)點(diǎn)的 next 賦值給了 e
        // 7.2 (next = (current = e).next) == null
        // 判斷當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是否為 null
        // a. 如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為 null
        // 就執(zhí)行 do {} while (index < t.length && (next = t[index++]) == null);
        // 再 table 數(shù)組中 遍歷，尋找 table 數(shù)組中的下一個(gè) Node 并賦值給 next
        // b. 如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為 null
        // 就將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)賦值給 next，并且此刻不會(huì)去 table 數(shù)組中遍歷下一個(gè) Node 節(jié)點(diǎn)
        // 7.3 將找到的節(jié)點(diǎn) e 返回
        // 7.4 之后每次執(zhí)行 iterator.next()，都像 a、b 那樣去判斷遍歷，直到遍歷完成
        Iterator iterator = hashSet.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }
    }
}