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怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！