HashSet、TreeSet、TreeMap实现原理
一、HashSet底層實現
HashSet實現了Set接口，不允許有重復元素，因為HashSet是基于HashMap實現的，HashSet中的元素都存放在HashMap的key上面，而value中的值都是統一的一個private static final Object PRESENT = new Object();。HashSet跟HashMap一樣，都是一個存放鏈表的數組。
二、HashSet構造
HashSet底層使用HashMap來保存所有元素，更確切的說，HashSet中的元素，只是存放在了底層HashMap的key上， 而value使用一個static final的Object對象標識。因此HashSet 的實現比較簡單，相關HashSet的操作，基本上都是直接調用底層HashMap的相關方法來完成。
部分源代碼：
主要方法：
三、HashSet和HashMap的區別在這里插入代碼片
四、TreeSet底層實現
TreeSet底層采用NavigableMap這個接口來保存TreeSet集合，而實際上NavigableMap只是一個接口，實際上TreeSet還是用TreeMap來保存set元素。
TreeSet初始化的時候會new 一個TreeMap進行初始化
部分代碼：
五、TreeSet和TreeMap
之所以把TreeSet和TreeMap放在一起講解，是因為二者在Java里有著相同的實現，前者僅僅是對后者做了一層包裝，也就是說TreeSet里面有一個TreeMap(適配器模式)**。因此本段將重點分析TreeMap。 Java TreeMap實現了SortedMap接口，也就是說會按照key的大小順序對Map中的元素進行排序，key大小的評判可以通過其本身的自然順序(natural ordering)，也可以通過構造時傳入的比較器(Comparator)。 TreeMap底層通過紅黑樹(Red-Black tree)實現，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時間復雜度。其具體算法實現參照了《算法導論》。
出于性能原因，TreeMap是非同步的(not synchronized)，如果需要在多線程環境使用，需要程序員手動同步；或者通過如下方式將TreeMap包裝成(wrapped)同步的:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));紅黑樹是一種近似平衡的二叉查找樹，它能夠確保任何一個節點的左右子樹的高度差不會超過二者中較低那個的一陪。具體來說，紅黑樹是滿足如下條件的二叉查找樹(binary search tree):
- 每個節點要么是紅色，要么是黑色。
- 根節點必須是黑色
- 紅色節點不能連續(也即是，紅色節點的孩子和父親都不能是紅色)。
- 對于每個節點，從該點至null(樹尾端)的任何路徑，都含有相同個數的黑色節點。
在樹的結構發生改變時(插入或者刪除操作)，往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的約束條件。
前文說到當查找樹的結構發生改變時，紅黑樹的約束條件可能被破壞，需要通過調整使得查找樹重新滿足紅黑樹的約束條件。調整可以分為兩類: 一類是顏色調整，即改變某個節點的顏色；另一類是結構調整，集改變檢索樹的結構關系。結構調整過程包含兩個基本操作** :
左旋(Rotate Left)，右旋(RotateRight)**。
- 左旋的過程是將x的右子樹繞x逆時針旋轉，使得x的右子樹成為x的父親，同時修改相關節點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。
TreeMap中左旋代碼如下:
//Rotate Left private void rotateLeft(Entry<K,V> p) {if (p != null) {Entry<K,V> r = p.right;p.right = r.left;if (r.left != null)r.left.parent = p;r.parent = p.parent;if (p.parent == null)root = r;else if (p.parent.left == p)p.parent.left = r;elsep.parent.right = r;r.left = p;p.parent = r;} }- 右旋的過程是將x的左子樹繞x順時針旋轉，使得x的左子樹成為x的父親，同時修改相關節點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。
- TreeMap中右旋代碼如下:
對于一棵二叉查找樹，給定節點t，其后繼(樹中比大于t的最小的那個元素)可以通過如下方式找到:
- t的右子樹不空，則t的后繼是其右子樹中最小的那個元素。
- t的右孩子為空，則t的后繼是其第一個向左走的祖先。
后繼節點在紅黑樹的刪除操作中將會用到。
TreeMap中尋找節點后繼的代碼如下:
// 尋找節點后繼函數successor() static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {if (t == null)return null;else if (t.right != null) {// 1. t的右子樹不空，則t的后繼是其右子樹中最小的那個元素Entry<K,V> p = t.right;while (p.left != null)p = p.left;return p;} else {// 2. t的右孩子為空，則t的后繼是其第一個向左走的祖先Entry<K,V> p = t.parent;Entry<K,V> ch = t;while (p != null && ch == p.right) {ch = p;p = p.parent;}return p;} }- get()
- get(Object key)方法根據指定的key值返回對應的value，該方法調用了getEntry(Object key)得到相應的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根據key的自然順序(或者比較器順序)對二叉查找樹進行查找，直到找到滿足k.compareTo(p.key) == 0的entry。
具體代碼如下:
//getEntry()方法 final Entry<K,V> getEntry(Object key) {......if (key == null)//不允許key值為nullthrow new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序Entry<K,V> p = root;while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)//向左找p = p.left;else if (cmp > 0)//向右找p = p.right;elsereturn p;}return null; }- put()
put(K key, V value)方法是將指定的key, value對添加到map里。該方法首先會對map做一次查找，看是否包含該元組，如果已經包含則直接返回，查找過程類似于getEntry()方法；如果沒有找到則會在紅黑樹中插入新的entry，如果插入之后破壞了紅黑樹的約束條件，還需要進行調整(旋轉，改變某些節點的顏色)。
上述代碼的插入部分并不難理解: 首先在紅黑樹上找到合適的位置，然后創建新的entry并插入(當然，新插入的節點一定是樹的葉子)。難點是調整函數fixAfterInsertion()，前面已經說過，調整往往需要1.改變某些節點的顏色，2.對某些節點進行旋轉。
調整函數fixAfterInsertion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數。通過代碼我們能夠看到，情況2其實是落在情況3內的。情況4～情況6跟前三種情況是對稱的，因此圖解中并沒有畫出后三種情況，讀者可以參考代碼自行理解。
//紅黑樹調整函數fixAfterInsertion() private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK); // 情況1setColor(y, BLACK); // 情況1setColor(parentOf(parentOf(x)), RED); // 情況1x = parentOf(parentOf(x)); // 情況1} else {if (x == rightOf(parentOf(x))) {x = parentOf(x); // 情況2rotateLeft(x); // 情況2}setColor(parentOf(x), BLACK); // 情況3setColor(parentOf(parentOf(x)), RED); // 情況3rotateRight(parentOf(parentOf(x))); // 情況3}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK); // 情況4setColor(y, BLACK); // 情況4setColor(parentOf(parentOf(x)), RED); // 情況4x = parentOf(parentOf(x)); // 情況4} else {if (x == leftOf(parentOf(x))) {x = parentOf(x); // 情況5rotateRight(x); // 情況5}setColor(parentOf(x), BLACK); // 情況6setColor(parentOf(parentOf(x)), RED); // 情況6rotateLeft(parentOf(parentOf(x))); // 情況6}}}root.color = BLACK; }- remove()
remove(Object key)的作用是刪除key值對應的entry，該方法首先通過上文中提到的getEntry(Object key)方法找到key值對應的entry，然后調用deleteEntry(Entry<K,V> entry)刪除對應的entry。由于刪除操作會改變紅黑樹的結構，有可能破壞紅黑樹的約束條件，因此有可能要進行調整。 getEntry()函數前面已經講解過，這里重點放deleteEntry()上，該函數刪除指定的entry并在紅黑樹的約束被破壞時進行調用fixAfterDeletion(Entry<K,V> x)進行調整。 由于紅黑樹是一棵增強版的二叉查找樹，紅黑樹的刪除操作跟普通二叉查找樹的刪除操作也就非常相似，唯一的區別是紅黑樹在節點刪除之后可能需要進行調整。現在考慮一棵普通二叉查找樹的刪除過程，可以簡單分為兩種情況:
- 刪除點p的左右子樹都為空，或者只有一棵子樹非空。
- 刪除點p的左右子樹都非空。
對于上述情況1，處理起來比較簡單，直接將p刪除(左右子樹都為空時)，或者用非空子樹替代p(只有一棵子樹非空時)；對于情況2，可以用p的后繼s(樹中大于x的最小的那個元素)代替p，然后使用情況1刪除s(此時s一定滿足情況1.可以畫畫看)。
基于以上邏輯，紅黑樹的節點刪除函數deleteEntry()代碼如下:
上述代碼中占據大量代碼行的，是用來修改父子節點間引用關系的代碼，其邏輯并不難理解。下面著重講解刪除后調整函數fixAfterDeletion()。首先請思考一下，刪除了哪些點才會導致調整？只有刪除點是BLACK的時候，才會觸發調整函數，因為刪除RED節點不會破壞紅黑樹的任何約束，而刪除BLACK節點會破壞規則4。 跟上文中講過的fixAfterInsertion()函數一樣，這里也要分成若干種情況。記住，無論有多少情況，具體的調整操作只有兩種: 1.改變某些節點的顏色，2.對某些節點進行旋轉。
上述圖解的總體思想是: 將情況1首先轉換成情況2，或者轉換成情況3和情況4。當然，該圖解并不意味著調整過程一定是從情況1開始。通過后續代碼我們還會發現幾個有趣的規則: a).如果是由情況1之后緊接著進入的情況2，那么情況2之后一定會退出循環(因為x為紅色)；b).一旦進入情況3和情況4，一定會退出循環(因為x為root)。 刪除后調整函數fixAfterDeletion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數。通過代碼我們能夠看到，情況3其實是落在情況4內的。情況5～情況8跟前四種情況是對稱的，因此圖解中并沒有畫出后四種情況，讀者可以參考代碼自行理解。
private void fixAfterDeletion(Entry<K,V> x) {while (x != root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {Entry<K,V> sib = rightOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK); // 情況1setColor(parentOf(x), RED); // 情況1rotateLeft(parentOf(x)); // 情況1sib = rightOf(parentOf(x)); // 情況1}if (colorOf(leftOf(sib)) == BLACK &&colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED); // 情況2x = parentOf(x); // 情況2} else {if (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK); // 情況3setColor(sib, RED); // 情況3rotateRight(sib); // 情況3sib = rightOf(parentOf(x)); // 情況3}setColor(sib, colorOf(parentOf(x))); // 情況4setColor(parentOf(x), BLACK); // 情況4setColor(rightOf(sib), BLACK); // 情況4rotateLeft(parentOf(x)); // 情況4x = root; // 情況4}} else { // 跟前四種情況對稱Entry<K,V> sib = leftOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK); // 情況5setColor(parentOf(x), RED); // 情況5rotateRight(parentOf(x)); // 情況5sib = leftOf(parentOf(x)); // 情況5}if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {setColor(sib, RED); // 情況6x = parentOf(x); // 情況6} else {if (colorOf(leftOf(sib)) == BLACK) {setColor(rightOf(sib), BLACK); // 情況7setColor(sib, RED); // 情況7rotateLeft(sib); // 情況7sib = leftOf(parentOf(x)); // 情況7}setColor(sib, colorOf(parentOf(x))); // 情況8setColor(parentOf(x), BLACK); // 情況8setColor(leftOf(sib), BLACK); // 情況8rotateRight(parentOf(x)); // 情況8x = root; // 情況8}}}setColor(x, BLACK); }前面已經說過TreeSet是對TreeMap的簡單包裝，對TreeSet的函數調用都會轉換成合適的TreeMap方法，因此TreeSet的實現非常簡單。這里不再贅述。
// TreeSet是對TreeMap的簡單包裝 public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable {......private transient NavigableMap<E,Object> m;// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();public TreeSet() {this.m = new TreeMap<E,Object>();// TreeSet里面有一個TreeMap}......public boolean add(E e) {return m.put(e, PRESENT)==null;}...... }TreeMap 是 Map 接口的常用實現類，TreeSet 是 Set 接口的常用實現類。
雖然 TreeMap 和TreeSet 實現的接口規范不同，但 TreeSet 底層是通過 TreeMap 來實現的（如同HashSet底層是是通過HashMap來實現的一樣），因此二者的實現方式完全一樣。與HashSet完全類似，TreeSet里面絕大部分方法都是直接調用TreeMap方法來實現的。而 TreeMap采用“紅黑樹”保存Map中的每個Entry——每個Entry都被當做紅黑樹的一個節點來對待；TreeMap的插入就是一個“排序二叉樹”算法：每當程序添加新節點時，總是從樹的根節點開始比較，即將根節點當成當前節點，如果新增節點大于當前節點且當前節點的右節點存在，則以右節點作為當前節點；如果新增節點小于當前節點且當前節點的左節點存在，則以左節點作為當前節點；如果新增節點等于當前節點，則新增節點覆蓋當前節點；直到某個節點的左右節點不存在，并結束循環；將新增的節點作為該節點的子節點，如果新增的節點大于該節點，則添加成該節點的右節點，如果新增的節點小于該節點，則添加成該節點的左節點。
相同點：
1、都是有序集合 2、TreeMap是TreeSet的底層結構 3、運行速度都比hash慢不同點：
1、TreeSet只存儲一個對象，而TreeMap存儲兩個對象Key和Value（僅僅key對象有序） 2、TreeSet中不能有重復對象，而TreeMap中可以存在 3、TreeMap的底層采用紅黑樹的實現，完成數據有序的插入，排序。總結
以上是生活随笔為你收集整理的HashSet、TreeSet、TreeMap实现原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 互联网晚报 | 11月11日 星期四 |
- 下一篇： concurrenthashmap 1.