Java-HashSet

HashSet（​​參考文章​​）

HashSet 是一個 沒有重複元素 ，而且 無序 （存入和取出的順序不一定相同）的集合。

它是由 HashMap 實作的，不保證元素的順序，而且HashSet允許使用 null 元素。

HashSet 底層是 HashMap

添加 add 機制：

（1） 添加一個元素時，先得到 hash 值（會轉化為索引值）

擷取 hash 值的方法是：

<code>static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16); // ^ 異或，&gt;&gt;&gt; 無符号右移 }</code>

為什麼要異或和右移，參考文章：javascript:void(0)

（2） 找到存儲資料表 table ，看這個索引位置是否已經存放有元素：

若沒有，直接加入；

若有，調用 equals方法比較，如果相同，則放棄添加；如果不相同，則添加到最後。

擴容機制：

擴容實際調用的方法是： resize()

（1） 第一次添加時，table數組擴容到16，臨界值（threshold）是 16 * 加載因子（loadFactor）是 0.75 = 12；

（2） 如果table數組使用到了臨界值12，就會擴容到16 * 2 = 32，新的臨界值就是 32 * 0.75 = 24，以此類推；

<code>if (++size &gt; threshold) resize(); //這裡的 size 就是插入的結點數</code>

（3）在Java8中，如果一條連結清單的元素個數到達 TREEIFY_THRESHOLD（預設是8），并且table的大小 &gt;= MIN_TREEIFY_CAPACITY（預設64），就會進行樹化（紅黑樹）,否則仍然采用數組擴容機制。

例子：假如有 12 個對象，它們的 hash值相同（轉化的索引就相同），但是它們調用 equals方法顯示各不相同。在 table數組上，當添加到第八個對象時，就會進行數組擴容（此時它們的索引會發生相應的改變，但還是相同），添加第九個對象時，也會進行數組擴容，這些對象仍然在同一個索引點的連結清單上。

由于 HashSet 是無序的，周遊方式常用的兩種：

疊代器循環（快捷鍵 <code>itit</code>）

增強 for 循環 （快捷鍵 <code>集合名字.for</code>）

main方法執行的代碼：

debug進去：