這篇文章主要講解了“JDK的TreeMap怎么實(shí)現(xiàn)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“JDK的TreeMap怎么實(shí)現(xiàn)”吧！

創(chuàng)新互聯(lián)專業(yè)提供成都主機(jī)托管四川主機(jī)托管成都服務(wù)器托管四川服務(wù)器托管，支持按月付款！我們的承諾：貴族品質(zhì)、平民價(jià)格，機(jī)房位于中國電信/網(wǎng)通/移動(dòng)機(jī)房，香港機(jī)房服務(wù)器托管服務(wù)有保障！

TreeMap的實(shí)現(xiàn)也是利用的紅黑樹，我們來看代碼：

在TreeMap中包含著一個(gè)根結(jié)點(diǎn)：

1. private transient Entry root = null;

這個(gè)Entry代碼如下：

1. static final class Entry implements Map.Entry {

2.         K key;

3.         V value;

4.         //指向小兒子

5.         Entry left = null;

6.         //指向大兒子

7.         Entry right = null;

8.          //指向父親

9.         Entry parent;

10.         //顏色默認(rèn)為黑色

11.         boolean color = BLACK;

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

14.             this.key = key;

15.             this.value = value;

16.             this.parent = parent;

17.         }

19.         public K getKey() {

20.             return key;

21.         }

24.         public V getValue() {

25.             return value;

26.         }

29.         public V setValue(V value) {

30.             V oldValue = this.value;

31.             this.value = value;

32.             return oldValue;

33.         }

35.         public boolean equals(Object o) {

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

37.                 return false;

38.             Map.Entry e = (Map.Entry)o;

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

41.         }

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.         }

49.         public String toString() {

50.             return key + "=" + value;

51.         }

52.     }

廢話不多說，我們來看一下他的插入實(shí)現(xiàn)：

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

2.         Entry t = root;

3.         //如果樹是空樹

4.         if (t == null) {

5.             //那么樹根節(jié)點(diǎn)就是節(jié)點(diǎn)

6.             root = new Entry(key, value, null);

7.             size = 1;

8.             modCount++;

9.             return null;

10.         }

11.         int cmp;

12.         Entry parent;

13.         //否則利用提供的比較器進(jìn)行比較

14.         Comparator cpr = comparator;

15.         if (cpr != null) {

16.             do {

17.                 parent = t; 

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

20.                 //如果比當(dāng)前節(jié)點(diǎn)小，

21.                 if (cmp < 0)

22.                     //往小兒子遞歸

23.                     t = t.left;

24.                 else if (cmp > 0)

25.                     //往大兒子遞歸

26.                     t = t.right;

27.                 else

28.                     //如果已經(jīng)有這個(gè)key，那么修改key，并且什么都可以 不修改了

29.                     return t.setValue(value);

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

31.         }

32.         else {

33.             if (key == null)

34.                 throw new NullPointerException();

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

36.             Comparable k = (Comparable) 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.         //生成一個(gè)葉子節(jié)點(diǎn)，準(zhǔn)備進(jìn)行加入

49.         Entry e = new Entry(key, value, parent);

50.         //利用最后的判斷，將這個(gè)節(jié)點(diǎn)變成該葉子節(jié)點(diǎn)的兒子；

51.         if (cmp < 0)

52.             parent.left = e;

53.         else

54.             parent.right = e;

55.         //由于有可能破壞了紅黑樹的規(guī)則，現(xiàn)在進(jìn)行調(diào)整；

56.         fixAfterInsertion(e);

57.         size++;

58.         modCount++;

59.         return null;

60.     }

1. private void fixAfterInsertion(Entry x) {

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

3.         x.color = RED;

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

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

6.             //如果是左子數(shù)；

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

8.                 Entry y = rightOf(parentOf(parentOf(x)));

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

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.                  //兄弟為黑色

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.                //如果是右子數(shù)，正好與上面相反；

27.             } else {

28.                 Entry 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.         //沖突會(huì)一直追溯到跟，把跟染黑，不違背根節(jié)點(diǎn)是黑色的特性，并且使得所有的樹枝的黑色節(jié)點(diǎn)因此加1，沖突解決；

46.         root.color = BLACK;

47.     }

看完了增加，我們?cè)賮砜纯磩h除

1.   public V remove(Object key) {

2.         //查找到該節(jié)點(diǎn)

3.         Entry p = getEntry(key);

4.         //不存在則結(jié)束

5.         if (p == null)

6.             return null;

8.         V oldValue = p.value;

9.         //刪除

10.         deleteEntry(p);

11.         //返回原值

12.         return oldValue;

13.     }

查找該節(jié)點(diǎn)：

1. final Entry getEntry(Object key) {

2.         if (comparator != null)

3.             //利用外部比較器

4.             return getEntryUsingComparator(key);

5.         if (key == null)

6.             throw new NullPointerException();

7.         //內(nèi)置比較器

8.     Comparable k = (Comparable) key;

9.         Entry 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.     }

外部比較器查找節(jié)點(diǎn)：

1.     final Entry getEntryUsingComparator(Object key) {

2.     K k = (K) key;

3.         Comparator cpr = comparator;

4.         if (cpr != null) {

5.             Entry 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 p) {

2.         modCount++;

3.         size--;

4.         //如果刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)；

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

6.             Entry s = successor (p);

7.             p.key = s.key;

8.             p.value = s.value;

9.             p = s;

10.         } 

12.         //兩個(gè)子節(jié)點(diǎn)的刪除轉(zhuǎn)化為了一個(gè)子節(jié)點(diǎn)的刪除

13.        //進(jìn)行一個(gè)子節(jié)點(diǎn)的刪除操作；

14.         Entry replacement = (p.left != null ? p.left : p.right);

16.        //如果有一個(gè)以上的節(jié)點(diǎn)；重新接上樹枝； 

17.         if (replacement != null) {

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;

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

28.             //如果刪除位置的新節(jié)點(diǎn)是黑色的，那么會(huì)少一個(gè)黑節(jié)點(diǎn)，調(diào)整

29.             if (p.color == BLACK)

30.             //調(diào)整新的節(jié)點(diǎn)，即刪除節(jié)點(diǎn)的子節(jié)點(diǎn)；

31.                 fixAfterDeletion(replacement);

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

33.             root = null;

34.         } else {  

35.             //如果沒有子節(jié)點(diǎn)

36.             //紅色的節(jié)點(diǎn)要可以直接刪除，黑色的話，必須要經(jīng)過調(diào)整；
    

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.     }

刪除后的調(diào)整：

1. private void fixAfterDeletion(Entry x) {

2.         // 如果節(jié)點(diǎn)是黑色的；那么要經(jīng)過調(diào)整，如果是紅色的，可以直接修改成為黑色的，結(jié)束循環(huán)；
   

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

4.             // 判斷被刪除節(jié)點(diǎn)是左子樹；
   

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

6.                 // 獲得兄弟節(jié)點(diǎn)；

7.                 Entry sib = rightOf(parentOf(x));

8.                 //兄弟節(jié)點(diǎn)是紅色的
   

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

11.                     setColor(sib, BLACK);

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

13.                     //開始旋轉(zhuǎn)
    

14.                     rotateLeft(parentOf(x));

15.                     // 得到旋轉(zhuǎn)后的新的兄弟節(jié)點(diǎn)；這個(gè)時(shí)候是黑色的
    

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

17.                 }

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

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

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

22.                     setColor(sib, RED);

23.                     x = parentOf(x);

24.                 } else {

25.                     // 只有一個(gè)是黑色的

26.                   // 如果是黑色的那個(gè)侄子位置不對(duì)，那么經(jīng)過一次轉(zhuǎn)換；
    

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 sib = leftOf(parentOf(x));

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

43.                     setColor(sib, BLACK);

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

45.                     rotateRight(parentOf(x));

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

47.                 }

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.         //如果該節(jié)點(diǎn)不是黑色的，或者是根節(jié)點(diǎn)，那么把他染黑；

69.         setColor(x, BLACK);

70.     }

1.  static  TreeMap.Entry successor(Entry t) {

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

3.         if (t == null)

4.             return null;

5.         //如果大兒子存在，那么沿著這條路下去，找到其這個(gè)枝條中最小的節(jié)點(diǎn)

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

7.             Entry p = t.right;

8.             while (p.left != null)

9.                 p = p.left;

10.             return p;

11.         } else {

12.         //如果右邊子樹是空的，那么找到其長輩節(jié)點(diǎn)中間第一個(gè)大于他的

13.             Entry p = t.parent;

14.             Entry ch = t;

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

16.                 ch = p;

17.                 p = p.parent;

18.             }

19.             return p;

20.         }

21.     }

我們?cè)賮砜匆幌挛覀冊(cè)讷@取其集合的時(shí)候的順序：

1.    static final class KeySet extends AbstractSet implements NavigableSet {

2.         private final NavigableMap m;

3.         KeySet(NavigableMap map) { m = map; }

5.         public Iterator iterator() {

6.             if (m instanceof TreeMap)

7.                 return ((TreeMap)m).keyIterator();

8.             else

9.                 return (Iterator)(((TreeMap.NavigableSubMap)m).keyIterator());

10.         }

12.         public Iterator descendingIterator() {

13.             if (m instanceof TreeMap)

14.                 return ((TreeMap)m).descendingKeyIterator();

15.             else

16.                 return (Iterator)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());

17.         }

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 comparator() { return m.comparator(); }

30.         public E pollFirst() {

31.             Map.Entry e = m.pollFirstEntry();

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

33.         }

34.         public E pollLast() {

35.             Map.Entry 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 subSet(E fromElement, boolean fromInclusive,

44.                                       E toElement,   boolean toInclusive) {

45.             return new TreeSet(m.subMap(fromElement, fromInclusive,

46.                                            toElement,   toInclusive));

47.         }

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

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

50.         }

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

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

53.         }

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

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

56.         }

57.         public SortedSet headSet(E toElement) {

58.             return headSet(toElement, false);

59.         }

60.         public SortedSet tailSet(E fromElement) {

61.             return tailSet(fromElement, true);

62.         }

63.         public NavigableSet descendingSet() {

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

65.         }

66.     }

這個(gè)是返回的set，他的查找排序是利用的迭代模式委托給了迭代器，我們看看他的迭代器實(shí)現(xiàn)：

1.  final class KeyIterator extends PrivateEntryIterator {

2.         KeyIterator(Entry first) {

3.             super(first);

4.         }

5.         public K next() {

6.             return nextEntry().key;

7.         }

8.     }

其中獲取下一個(gè)nextEntry是：

1. final Entry nextEntry() {

2.             Entry 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怎么實(shí)現(xiàn)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)JDK的TreeMap怎么實(shí)現(xiàn)這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！