說下 TreeSet 和 HashSet 什麼區別呢？
它們的區別點主要在他們的底層數據結構不同，HashSet 使用的是 HashMap 來實現，而 TreeSet 使用的是 TreeMap 來實現的。
哦？那你瞭解 HashMap 和 TreeMap 的區別嗎？
HashMap 是一個最常用的數據結構，它主要用於我們有通過固定值(key)獲取內容的場景，時間複雜度可以最快優化到 O(1) 哈，當然效果不好的時候時間複雜度是 O(logN) 或者O(n)。雖然固定值查找提高了速度，但是 HashMap 不能保證固定值，也就是 key 的順序，所以這個時候 TreeMap 就出現了，雖然它的查找、刪除、更新的時間複雜度都是 O(logN)，但是他可以保證 key 的有序性。
恩恩，掌握的還不錯，那你和我說一下 HashMap 和 TreeMap 的底層實現有什麼不同，才導致的他們有這麼大的差異？
這個原因主要是它們底層用的實現不同，HashMap 使用的是數組(桶)和哈希的方式實現，巧妙通過 key 的哈希路由到每一個數組用於存放內容，這時候通過 key 獲取 value 的時間複雜度就是 O(1)，當然因為 key 的哈希可能碰撞，所以就需要針對碰撞的時候做處理，HashMap 裡面每一個數組(桶)裡面存的其實是一個鏈表，key 的哈希衝突以後會追加到鏈表上面，這時候再通過 key 獲取 value 的時候時間複雜度就變成了 O(n)，那麼數據碰撞越來越多的時候豈不是查詢很慢？最後呢為了優化這個時間複雜度，HashMap 當一個 key 碰撞次數超過 TREEIFY THRESHOLD 的時候就會把鏈表轉換成紅黑樹，這樣雖然插入的時候也增加了時間複雜度，但是對於頻繁哈希碰撞的問題的查詢效率有很大的提高，使得查詢的時間複雜度變成了 O(logN)。
哈，說到紅黑樹就把 HashMap 和 TreeMap 聯繫到了一起，因為 TreeMap 的底層實現就是紅黑樹。
恩恩，既然你說到了紅黑樹，那麼我想問下為什麼採用的是紅黑樹，而不是二叉樹搜索樹呢？
恩，通常情況當我們聽到二叉搜索樹的時候以為它是平衡樹，其實不是。它只是左子樹的值小於根節點，右子樹的值大於根節點，如果構建根節點以後插入的數據是有序的，那麼構造出來的二叉搜索樹就不是平衡樹，而是一個鏈表，那麼它的時間複雜度就是 O(n)，如下圖。然而紅黑樹呢？就是通過每個節點標色的方式，每次更新數據以後再進行平衡，以此來保證其查找效率。
恩好的，那既然你說到了這裡，那麼你再展開說明一下它是怎麼做到的每次插入都平衡。
恩，紅黑樹因為它每個節點都有黑色或者紅色兩種顏色，當然它也有一些特性，比如
1、根節點是黑色的
2、紅色節點的子節點必須是黑色並且父節點也是黑色，
3、任何一條路徑的黑色節點個數相同。
它通過這些特性再重新插入的時候做著色處理，配合左旋，右旋來達到最終的平衡。所以可以理解黑色紅色其實是為了更好的輔助平衡。當有了這個著色以後配合紅黑樹的性質，就可以定義出來一個平衡的公式如下，首先插入的元素必須是紅色，因為黑色破壞他的性質的幾率更大。
假定 X 是新插入的節點，P是父節點，Y是叔父節點，G是祖父節點，P 為 G 的左孩子
當 Y 為紅色 -> P、Y 變黑，G 變紅，X 變 G
當 Y 為黑色，X 是右孩子 -> 左旋 P，X 變 P
當 Y 為黑色，X 為左孩子 -> G 變紅，P變黑，右旋 G
當 P 為 G 的右孩子的時候，直接做鏡像操作即可。
https://mmbiz.qpic.cn/mmbiz_g...
當然這樣還是非常的晦澀，如果還是沒直觀，可以直接看一下下面的視頻講解版本。
https://www.bilibili.com/vide...
提到了 Hash，那麼如果我想自定義一個 Class 作為 key，那麼應該注意什麼呢？
我覺得應該是注意重寫 hashCode 和 equals 方法。以 put 方法為例，因為在 HashMap 內部 hash 的時候需要用到 hashCode，以此來判斷兩個 Class 實例的 hash 是否一致。equals 是用來在 hash 碰撞以後追加鏈表的時候比對看是否相同以便更新。
恩，那既然你提到了 hash 用到了 hashCode 方法，你來解釋一下 HashMap 裡面的 hash 具體怎麼實現的呢？
好的，這個我還專門研究過，打開 HashMap源碼，從 put 說起吧。它最先調用的是 hash 函數，然後和當前的 n - 1 做與運算得到 bucket 的下標，關鍵代碼如下：
<code>(h = key.hashCode()) ^ (h >>> 16) // 338 行
tab[i = (n - 1) & hash] // 692 行/<code>
具體邏輯，先是獲取 key 的 hashCode，然後把 hashCode 低位位移 16 位後和之前的 hashCode 做亦或運算得到最終的 hash 值， bucket 數量是有限的，所以需要和 n -1 與運算得到最終的下標
這麼說可能比較晦澀，我簡單畫一個圖吧。以 key 是 “我是key” 為例，n 默認為 16，下圖是把十進制轉換為二進制進行計算。
<code>String value = "我是key";
int hashCode = value.hashCode(); //817810155
int lowBit = hashCode >>> 16; //12478
int hash = hashCode ^ lowBit; //817822293
int index = (n - 1) & hash; //5/<code>
如圖，可以清楚的瞭解到 hash 的全過程，最後一步 (n -1) & hash 很好理解，就是為了把計算好的 hash 映射到所有的 bucket 槽位。那麼 h ^ (h >>> 16) 是因為通常情況 bucket 的槽位很少，用於參與運算的只有 hashCode 低位，為了讓高位也可以參與運算，儘可能的在不影響性能的情況下避免衝突，所以做了一下高位右移 16 位然後亦或運算。
接下來的流程就相對比較好理解了，獲取到 index 以後沒有碰撞直接放入 bucket，如果碰撞了就追加到鏈表尾部，JDK8以前是頭部，JDK8是為了計算步長等於 8 的時候轉換為紅黑樹，所以每次都是遍歷鏈表插入到尾部。說到紅黑樹上次已經回答你 漫畫：HashSet 和 TreeSet 的實現與原理，最後如果 size 超過了 factor * capacity 就會 resize()。
那順便和我說說你理解的 resize 吧？
resize 就是自動擴容，當 size 達到閾值以後會擴容到原來的 2 倍，關鍵代碼 newCap = oldCap << 1。但是這裡有一個非常巧妙的解決方法，因為擴容是擴充的 2 倍，n-1 轉換為二進制也就是高位變成了1，那麼根據(n - 1) & hash 計算，如果 hash 高位是 1 那麼新的 index 位置就是 oldIndex + 16，如果hash 的高位 是 0 ，那麼 index 的位置就是原來的 oldIndex 的位置，這樣直接判斷高位就可以了，省去了重新計算hash。
通過 HashMap 源碼我們也可以清楚的看到，714-743 行：
關於HashMap擴容為什麼總是2的次冪推薦閱讀： https://blog.csdn.net/u010841...
恩恩，掌握的還不錯嘛，對了，說了這麼多 HashMap 終究不是線程安全的，那麼怎麼樣把它變成線程安全的你知道嗎？
有一個工具方法，java.util.Collections#synchronizedMap(Map
但是最好的還是使用ConcurrentHashMap
閱讀更多 Java技術前沿 的文章
