JDK的TreeMap怎么實現

這篇文章主要講解了“JDK的TreeMap怎么實現”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“JDK的TreeMap怎么實現”吧！

TreeMap的實現也是利用的紅黑樹，我們來看代碼：

在TreeMap中包含著一個根結點：

1. private transient Entry<K,V> root = null;

這個Entry代碼如下：

1. static final class Entry<K,V> implements Map.Entry<K,V> {

2.         K key;

3.         V value;

4.         //指向小兒子

5.         Entry<K,V> left = null;

6.         //指向大兒子

7.         Entry<K,V> right = null;

8.          //指向父親

9.         Entry<K,V> parent;

10.         //顏色默認為黑色

11.         boolean color = BLACK;

12. 
    

13.         Entry(K key, V value, Entry<K,V> parent) {

14.             this.key = key;

15.             this.value = value;

16.             this.parent = parent;

17.         }

18. 
    

19.         public K getKey() {

20.             return key;

21.         }

22. 
    

23. 
    

24.         public V getValue() {

25.             return value;

26.         }

27. 
    

28. 
    

29.         public V setValue(V value) {

30.             V oldValue = this.value;

31.             this.value = value;

32.             return oldValue;

33.         }

34. 
    

35.         public boolean equals(Object o) {

36.             if (!(o instanceof Map.Entry))

37.                 return false;

38.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;

39. 
    

40.             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());

41.         }

42. 
    

43.         public int hashCode() {

44.             int keyHash = (key==null ? 0 : key.hashCode());

45.             int valueHash = (value==null ? 0 : value.hashCode());

46.             return keyHash ^ valueHash;

47.         }

48. 
    

49.         public String toString() {

50.             return key + "=" + value;

51.         }

52.     }

廢話不多說，我們來看一下他的插入實現：

1.  public V put(K key, V value) {

2.         Entry<K,V> t = root;

3.         //如果樹是空樹

4.         if (t == null) {

5.             //那么樹根節點就是節點

6.             root = new Entry<K,V>(key, value, null);

7.             size = 1;

8.             modCount++;

9.             return null;

10.         }

11.         int cmp;

12.         Entry<K,V> parent;

13.         //否則利用提供的比較器進行比較

14.         Comparator<? super K> cpr = comparator;

15.         if (cpr != null) {

16.             do {

17.                 parent = t; 

18. 
    

19.                 cmp = cpr.compare(key, t.key);

20.                 //如果比當前節點小，

21.                 if (cmp < 0)

22.                     //往小兒子遞歸

23.                     t = t.left;

24.                 else if (cmp > 0)

25.                     //往大兒子遞歸

26.                     t = t.right;

27.                 else

28.                     //如果已經有這個key，那么修改key，并且什么都可以 不修改了

29.                     return t.setValue(value);

30.             } while (t != null); //知道找到葉子節點；

31.         }

32.         else {

33.             if (key == null)

34.                 throw new NullPointerException();

35.             //如果沒有提供外部的比較器，那么就利用內置的比較器

36.             Comparable<? super K> k = (Comparable<? super K>) key;

37.             do {

38.                 parent = t;

39.                 cmp = k.compareTo(t.key);

40.                 if (cmp < 0)

41.                     t = t.left;

42.                 else if (cmp > 0)

43.                     t = t.right;

44.                 else

45.                     return t.setValue(value);

46.             } while (t != null);

47.         }

48.         //生成一個葉子節點，準備進行加入

49.         Entry<K,V> e = new Entry<K,V>(key, value, parent);

50.         //利用最后的判斷，將這個節點變成該葉子節點的兒子；

51.         if (cmp < 0)

52.             parent.left = e;

53.         else

54.             parent.right = e;

55.         //由于有可能破壞了紅黑樹的規則，現在進行調整；

56.         fixAfterInsertion(e);

57.         size++;

58.         modCount++;

59.         return null;

60.     }

61. 
    

62. 
    

1. private void fixAfterInsertion(Entry<K,V> x) {

2.         //首先將該新增節點染紅，葉子節點(null)是黑色的;

3.         x.color = RED;

4.         //如果他的父親是紅色的，那么沖突開始；

5.         while (x != null && x != root && x.parent.color == RED) {

6.             //如果是左子數；

7.             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {

8.                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));

9.                 //如果其兄弟是紅色的，那么根據上一節的分析，將兩兄弟都變成黑色，其父節點變紅，這樣黑色節點的數目沒有發生變化，而我們距離跟更近一步；

10.                 if (colorOf(y) == RED) {

11.                     setColor(parentOf(x), BLACK);

12.                     setColor(y, BLACK);

13.                     setColor(parentOf(parentOf(x)), RED);

14.                     x = parentOf(parentOf(x));

15.                 } else {

16.                  //兄弟為黑色

17. 
    

18.                     if (x == rightOf(parentOf(x))) {

19.                         x = parentOf(x);

20.                         rotateLeft(x);

21.                     }

22.                     setColor(parentOf(x), BLACK);

23.                     setColor(parentOf(parentOf(x)), RED);

24.                     rotateRight(parentOf(parentOf(x)));

25.                 }

26.                //如果是右子數，正好與上面相反；

27.             } else {

28.                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));

29.                 if (colorOf(y) == RED) {

30.                     setColor(parentOf(x), BLACK);

31.                     setColor(y, BLACK);

32.                     setColor(parentOf(parentOf(x)), RED);

33.                     x = parentOf(parentOf(x));

34.                 } else {

35.                     if (x == leftOf(parentOf(x))) {

36.                         x = parentOf(x);

37.                         rotateRight(x);

38.                     }

39.                     setColor(parentOf(x), BLACK);

40.                     setColor(parentOf(parentOf(x)), RED);

41.                     rotateLeft(parentOf(parentOf(x)));

42.                 }

43.             }

44.         }

45.         //沖突會一直追溯到跟，把跟染黑，不違背根節點是黑色的特性，并且使得所有的樹枝的黑色節點因此加1，沖突解決；

46.         root.color = BLACK;

47.     }

48. 
    

看完了增加，我們再來看看刪除

1.   public V remove(Object key) {

2.         //查找到該節點

3.         Entry<K,V> p = getEntry(key);

4.         //不存在則結束

5.         if (p == null)

6.             return null;

7. 
   

8.         V oldValue = p.value;

9.         //刪除

10.         deleteEntry(p);

11.         //返回原值

12.         return oldValue;

13.     }

查找該節點：

1. final Entry<K,V> getEntry(Object key) {

2.         if (comparator != null)

3.             //利用外部比較器

4.             return getEntryUsingComparator(key);

5.         if (key == null)

6.             throw new NullPointerException();

7.         //內置比較器

8.     Comparable<? super K> k = (Comparable<? super K>) key;

9.         Entry<K,V> p = root;

10.         while (p != null) {

11.             int cmp = k.compareTo(p.key);

12.             if (cmp < 0)

13.                 p = p.left;

14.             else if (cmp > 0)

15.                 p = p.right;

16.             else

17.                 return p;

18.         }

19.         return null;

20.     }

外部比較器查找節點：

1.     final Entry<K,V> getEntryUsingComparator(Object key) {

2.     K k = (K) key;

3.         Comparator<? super K> cpr = comparator;

4.         if (cpr != null) {

5.             Entry<K,V> p = root;

6.             while (p != null) {

7.                 int cmp = cpr.compare(k, p.key);

8.                 if (cmp < 0)

9.                     p = p.left;

10.                 else if (cmp > 0)

11.                     p = p.right;

12.                 else

13.                     return p;

14.             }

15.         }

16.         return null;

17.     }

刪除操作：

1.   private void deleteEntry(Entry<K,V> p) {

2.         modCount++;

3.         size--;

4.         //如果刪除的節點有兩個子節點；

5.         if (p.left != null && p.right != null) {

6.             Entry<K,V> s = successor (p);

7.             p.key = s.key;

8.             p.value = s.value;

9.             p = s;

10.         } 

11. 
    

12.         //兩個子節點的刪除轉化為了一個子節點的刪除

13.        //進行一個子節點的刪除操作；

14.         Entry<K,V> replacement = (p.left != null ? p.left : p.right);

15. 
    

16.        //如果有一個以上的節點；重新接上樹枝； 

17.         if (replacement != null) {

18. 
    

19.             replacement.parent = p.parent;

20.             if (p.parent == null)

21.                 root = replacement;

22.             else if (p == p.parent.left)

23.                 p.parent.left  = replacement;

24.             else

25.                 p.parent.right = replacement;

26. 
    

27.             p.left = p.right = p.parent = null;

28.             //如果刪除位置的新節點是黑色的，那么會少一個黑節點，調整

29.             if (p.color == BLACK)

30.             //調整新的節點，即刪除節點的子節點；

31.                 fixAfterDeletion(replacement);

32.         } else if (p.parent == null) { // return if we are the only node.

33.             root = null;

34.         } else {  

35.             //如果沒有子節點

36.             //紅色的節點要可以直接刪除，黑色的話，必須要經過調整；
    

37.             if (p.color == BLACK)

38.                 fixAfterDeletion(p);

39.            //刪除操作；

40.             if (p.parent != null) {

41.                 if (p == p.parent.left)

42.                     p.parent.left = null;

43.                 else if (p == p.parent.right)

44.                     p.parent.right = null;

45.                 p.parent = null;

46.             }

47.         }

48.     }

刪除后的調整：

1. private void fixAfterDeletion(Entry<K,V> x) {

2.         // 如果節點是黑色的；那么要經過調整，如果是紅色的，可以直接修改成為黑色的，結束循環；
   

3.         while (x != root && colorOf(x) == BLACK)

4.             // 判斷被刪除節點是左子樹；
   

5.             if (x == leftOf(parentOf(x))) {

6.                 // 獲得兄弟節點；

7.                 Entry<K,V> sib = rightOf(parentOf(x));

8.                 //兄弟節點是紅色的
   

9. 
   

10.                 if (colorOf(sib) == RED) {

11.                     setColor(sib, BLACK);

12.                     setColor(parentOf(x), RED);

13.                     //開始旋轉
    

14.                     rotateLeft(parentOf(x));

15.                     // 得到旋轉后的新的兄弟節點；這個時候是黑色的
    

16.                     sib = rightOf(parentOf(x));

17.                 }

18.                 //判斷侄子的顏色；如果兩個都是黑色的
    

19. 
    

20.                 if (colorOf(leftOf(sib))  == BLACK &&

21.                     colorOf(rightOf(sib)) == BLACK) {

22.                     setColor(sib, RED);

23.                     x = parentOf(x);

24.                 } else {

25.                     // 只有一個是黑色的

26.                    // 如果是黑色的那個侄子位置不對，那么經過一次轉換；
    

27.                     if (colorOf(rightOf(sib)) == BLACK) {

28.                         setColor(leftOf(sib), BLACK);

29.                         setColor(sib, RED);

30.                         rotateRight(sib);

31.                         sib = rightOf(parentOf(x));

32.                     }

33.                     setColor(sib, colorOf(parentOf(x)));

34.                     setColor(parentOf(x), BLACK);

35.                     setColor(rightOf(sib), BLACK);

36.                     rotateLeft(parentOf(x));

37.                     x = root;

38.                 }

39.             } else {

40.                 Entry<K,V> sib = leftOf(parentOf(x));

41. 
    

42.                 if (colorOf(sib) == RED) {

43.                     setColor(sib, BLACK);

44.                     setColor(parentOf(x), RED);

45.                     rotateRight(parentOf(x));

46.                     sib = leftOf(parentOf(x));

47.                 }

48. 
    

49.                 if (colorOf(rightOf(sib)) == BLACK &&

50.                     colorOf(leftOf(sib)) == BLACK) {

51.                     setColor(sib, RED);

52.                     x = parentOf(x);

53.                 } else {

54.                     if (colorOf(leftOf(sib)) == BLACK) {

55.                         setColor(rightOf(sib), BLACK);

56.                         setColor(sib, RED);

57.                         rotateLeft(sib);

58.                         sib = leftOf(parentOf(x));

59.                     }

60.                     setColor(sib, colorOf(parentOf(x)));

61.                     setColor(parentOf(x), BLACK);

62.                     setColor(leftOf(sib), BLACK);

63.                     rotateRight(parentOf(x));

64.                     x = root;

65.                 }

66.             }

67.         }

68.         //如果該節點不是黑色的，或者是根節點，那么把他染黑；

69.         setColor(x, BLACK);

70.     }

1.  static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {

2.         //如果為null，則返回

3.         if (t == null)

4.             return null;

5.         //如果大兒子存在，那么沿著這條路下去，找到其這個枝條中最小的節點

6.         else if (t.right != null) {

7.             Entry<K,V> p = t.right;

8.             while (p.left != null)

9.                 p = p.left;

10.             return p;

11.         } else {

12.         //如果右邊子樹是空的，那么找到其長輩節點中間第一個大于他的

13.             Entry<K,V> p = t.parent;

14.             Entry<K,V> ch = t;

15.             while (p != null && ch == p.right) {

16.                 ch = p;

17.                 p = p.parent;

18.             }

19.             return p;

20.         }

21.     }

我們再來看一下我們在獲取其集合的時候的順序：

1.    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {

2.         private final NavigableMap<E, Object> m;

3.         KeySet(NavigableMap<E,Object> map) { m = map; }

4. 
   

5.         public Iterator<E> iterator() {

6.             if (m instanceof TreeMap)

7.                 return ((TreeMap<E,Object>)m).keyIterator();

8.             else

9.                 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());

10.         }

11. 
    

12.         public Iterator<E> descendingIterator() {

13.             if (m instanceof TreeMap)

14.                 return ((TreeMap<E,Object>)m).descendingKeyIterator();

15.             else

16.                 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());

17.         }

18. 
    

19.         public int size() { return m.size(); }

20.         public boolean isEmpty() { return m.isEmpty(); }

21.         public boolean contains(Object o) { return m.containsKey(o); }

22.         public void clear() { m.clear(); }

23.         public E lower(E e) { return m.lowerKey(e); }

24.         public E floor(E e) { return m.floorKey(e); }

25.         public E ceiling(E e) { return m.ceilingKey(e); }

26.         public E higher(E e) { return m.higherKey(e); }

27.         public E first() { return m.firstKey(); }

28.         public E last() { return m.lastKey(); }

29.         public Comparator<? super E> comparator() { return m.comparator(); }

30.         public E pollFirst() {

31.             Map.Entry<E,Object> e = m.pollFirstEntry();

32.             return e == null? null : e.getKey();

33.         }

34.         public E pollLast() {

35.             Map.Entry<E,Object> e = m.pollLastEntry();

36.             return e == null? null : e.getKey();

37.         }

38.         public boolean remove(Object o) {

39.             int oldSize = size();

40.             m.remove(o);

41.             return size() != oldSize;

42.         }

43.         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,

44.                                       E toElement,   boolean toInclusive) {

45.             return new TreeSet<E>(m.subMap(fromElement, fromInclusive,

46.                                            toElement,   toInclusive));

47.         }

48.         public NavigableSet<E> headSet(E toElement, boolean inclusive) {

49.             return new TreeSet<E>(m.headMap(toElement, inclusive));

50.         }

51.         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {

52.             return new TreeSet<E>(m.tailMap(fromElement, inclusive));

53.         }

54.         public SortedSet<E> subSet(E fromElement, E toElement) {

55.             return subSet(fromElement, true, toElement, false);

56.         }

57.         public SortedSet<E> headSet(E toElement) {

58.             return headSet(toElement, false);

59.         }

60.         public SortedSet<E> tailSet(E fromElement) {

61.             return tailSet(fromElement, true);

62.         }

63.         public NavigableSet<E> descendingSet() {

64.             return new TreeSet(m.descendingMap());

65.         }

66.     }

這個是返回的set，他的查找排序是利用的迭代模式委托給了迭代器，我們看看他的迭代器實現：

1.  final class KeyIterator extends PrivateEntryIterator<K> {

2.         KeyIterator(Entry<K,V> first) {

3.             super(first);

4.         }

5.         public K next() {

6.             return nextEntry().key;

7.         }

8.     }

其中獲取下一個nextEntry是：

1. final Entry<K,V> nextEntry() {

2.             Entry<K,V> e = next;

3.             if (e == null)

4.                 throw new NoSuchElementException();

5.             if (modCount != expectedModCount)

6.                 throw new ConcurrentModificationException();

7.             next = successor(e);

8.             lastReturned = e;

9.             return e;

10.         }

利用的successvor（），在開始的分析中我們知道，successor的查找，是通過了樹的中序遍歷的

感謝各位的閱讀，以上就是“JDK的TreeMap怎么實現”的內容了，經過本文的學習后，相信大家對JDK的TreeMap怎么實現這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！