资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/【java源码一带一路系列】之TreeMap

【java源码一带一路系列】之TreeMap

Bamboy / 803人阅读

摘要：基于红黑树实现，在之前篇章中有所涉及，所以本篇重点不在此。费解顺带一提，如果你还记得之前文章中的也用到了红黑树，而它先比较的再比值，这比较的是值。在这的作用类似中的，修复红黑树性质。

</>复制代码 
  1. TreeMap基于红黑树实现，在之前HashMap篇章中有所涉及，所以本篇重点不在此。上路~
containsKey() --> getEntry() --> getEntryUsingComparator() 
</>复制代码 
  1. /**
  2.  * Returns {@code true} if this map contains a mapping for the specified
  3.  * key.
  4.  *
  5.  * @param key key whose presence in this map is to be tested
  6.  * @return {@code true} if this map contains a mapping for the
  7.  *         specified key
  8.  * @throws ClassCastException if the specified key cannot be compared
  9.  *         with the keys currently in the map
  10.  * @throws NullPointerException if the specified key is null
  11.  *         and this map uses natural ordering, or its comparator
  12.  *         does not permit null keys
  13.  */
  14. public boolean containsKey(Object key) {
  15.     return getEntry(key) != null; // Key不能为null 
  16. }
  17. /**
  18.  * Returns this map"s entry for the given key, or {@code null} if the map
  19.  * does not contain an entry for the key.
  20.  *
  21.  * @return this map"s entry for the given key, or {@code null} if the map
  22.  *         does not contain an entry for the key
  23.  * @throws ClassCastException if the specified key cannot be compared
  24.  *         with the keys currently in the map
  25.  * @throws NullPointerException if the specified key is null
  26.  *         and this map uses natural ordering, or its comparator
  27.  *         does not permit null keys
  28.  */
  29. final Entry getEntry(Object key) {
  30.     // Offload comparator-based version for sake of performance
  31.     if (comparator != null)
  32.         return getEntryUsingComparator(key);
  33.     if (key == null)
  34.         throw new NullPointerException();
  35.     @SuppressWarnings("unchecked")
  36.         Comparable k = (Comparable) key;
  37.     Entry p = root;
  38.     while (p != null) {
  39.         int cmp = k.compareTo(p.key);
  40.         if (cmp < 0)
  41.             p = p.left;
  42.         else if (cmp > 0)
  43.             p = p.right;
  44.         else
  45.             return p;
  46.     }
  47.     return null;
  48. }
  49. /**
  50.  * Version of getEntry using comparator. Split off from getEntry
  51.  * for performance. (This is not worth doing for most methods,
  52.  * that are less dependent on comparator performance, but is
  53.  * worthwhile here.)
  54.  */
  55. final Entry getEntryUsingComparator(Object key) {
  56.     @SuppressWarnings("unchecked")
  57.         K k = (K) key;
  58.     Comparator cpr = comparator;
  59.     if (cpr != null) {
  60.         Entry p = root;
  61.         while (p != null) {
  62.             int cmp = cpr.compare(k, p.key);
  63.             if (cmp < 0)
  64.                 p = p.left;
  65.             else if (cmp > 0)
  66.                 p = p.right;
  67.             else
  68.                 return p;
  69.         }
  70.     }
  71.     return null;
  72. }

虽然明面上是获取值的方法，本质却是比出个高低等。这里将Java的java.util.Comparator（比较器排序）、java.lang.Comparable（自然排序）都用到了。顺便补了两者知识点(见文末①)。当然这里好奇的是源码中将使用comparator比较独立提成方法，说是能提高性能。why?反向思考下，假使将getEntryUsingComparator()方法内代码放回getEntry()似乎也就多了一对“{}”。费解- -

顺带一提，如果你还记得之前文章中的HashMap也用到了红黑树，而它先比较的hash再比key值，这比较的是key值。

put() --> compare() --> fixAfterInsertion() 
</>复制代码 
  1. /**
  2.  * Associates the specified value with the specified key in this map.
  3.  * If the map previously contained a mapping for the key, the old
  4.  * value is replaced.
  5.  *
  6.  * @param key key with which the specified value is to be associated
  7.  * @param value value to be associated with the specified key
  8.  *
  9.  * @return the previous value associated with {@code key}, or
  10.  *         {@code null} if there was no mapping for {@code key}.
  11.  *         (A {@code null} return can also indicate that the map
  12.  *         previously associated {@code null} with {@code key}.)
  13.  * @throws ClassCastException if the specified key cannot be compared
  14.  *         with the keys currently in the map
  15.  * @throws NullPointerException if the specified key is null
  16.  *         and this map uses natural ordering, or its comparator
  17.  *         does not permit null keys
  18.  */
  19. public V put(K key, V value) {
  20.     Entry t = root;
  21.     if (t == null) {
  22.         compare(key, key); // type (and possibly null) check
  23.         root = new Entry<>(key, value, null);
  24.         size = 1;
  25.         modCount++;
  26.         return null;
  27.     }
  28.     int cmp;
  29.     Entry parent;
  30.     // split comparator and comparable paths
  31.     Comparator cpr = comparator;
  32.     if (cpr != null) {
  33.         do {
  34.             parent = t;
  35.             cmp = cpr.compare(key, t.key);
  36.             if (cmp < 0)
  37.                 t = t.left;
  38.             else if (cmp > 0)
  39.                 t = t.right;
  40.             else
  41.                 return t.setValue(value);
  42.         } while (t != null);
  43.     }
  44.     else {
  45.         if (key == null)
  46.             throw new NullPointerException();
  47.         @SuppressWarnings("unchecked")
  48.             Comparable k = (Comparable) key;
  49.         do {
  50.             parent = t;
  51.             cmp = k.compareTo(t.key);
  52.             if (cmp < 0)
  53.                 t = t.left;
  54.             else if (cmp > 0)
  55.                 t = t.right;
  56.             else
  57.                 return t.setValue(value);
  58.         } while (t != null);
  59.     }
  60.     Entry e = new Entry<>(key, value, parent);
  61.     if (cmp < 0)
  62.         parent.left = e;
  63.     else
  64.         parent.right = e;
  65.     fixAfterInsertion(e);
  66.     size++;
  67.     modCount++;
  68.     return null;
  69. }
  70. /**
  71.  * Compares two keys using the correct comparison method for this TreeMap.
  72.  */
  73. @SuppressWarnings("unchecked")
  74. final int compare(Object k1, Object k2) {
  75.     return comparator==null ? ((Comparable)k1).compareTo((K)k2)
  76.         : comparator.compare((K)k1, (K)k2);
  77. }
  78. /** From CLR */
  79. private void fixAfterInsertion(Entry x) {
  80.     x.color = RED;
  81.     while (x != null && x != root && x.parent.color == RED) {
  82.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  83.             Entry y = rightOf(parentOf(parentOf(x)));
  84.             if (colorOf(y) == RED) {
  85.                 setColor(parentOf(x), BLACK);
  86.                 setColor(y, BLACK);
  87.                 setColor(parentOf(parentOf(x)), RED);
  88.                 x = parentOf(parentOf(x));
  89.             } else {
  90.                 if (x == rightOf(parentOf(x))) {
  91.                     x = parentOf(x);
  92.                     rotateLeft(x);
  93.                 }
  94.                 setColor(parentOf(x), BLACK);
  95.                 setColor(parentOf(parentOf(x)), RED);
  96.                 rotateRight(parentOf(parentOf(x)));
  97.             }
  98.         } else {
  99.             Entry y = leftOf(parentOf(parentOf(x)));
  100.             if (colorOf(y) == RED) {
  101.                 setColor(parentOf(x), BLACK);
  102.                 setColor(y, BLACK);
  103.                 setColor(parentOf(parentOf(x)), RED);
  104.                 x = parentOf(parentOf(x));
  105.             } else {
  106.                 if (x == leftOf(parentOf(x))) {
  107.                     x = parentOf(x);
  108.                     rotateRight(x);
  109.                 }
  110.                 setColor(parentOf(x), BLACK);
  111.                 setColor(parentOf(parentOf(x)), RED);
  112.                 rotateLeft(parentOf(parentOf(x)));
  113.             }
  114.         }
  115.     }
  116.     root.color = BLACK;
  117. }

"compare(key, key);"是一个有意思写法。从注释直译就是类型（为null可能性）检查。为空检查很好理解，因为null.xx()肯定跑异常，至于类型检查笔者理解是要求键值实现Comparable接口。

</>复制代码 
  1. "from CLR"是指Cormen, Leiserson, Rivest，他们是算法导论的作者，也就是说TreeMap里面算法都是参照算法导论的伪代码。

由于TreeMap的有序性，使其增删查都是先进行比较，找到合适的位置。fixAfterInsertion()在这的作用类似HashMap中的balanceInsertion()，修复红黑树性质。

deleteEntry() --> successor() --> fixAfterDeletion() 
</>复制代码 
  1. /**
  2.  * Delete node p, and then rebalance the tree.
  3.  */
  4. private void deleteEntry(Entry p) {
  5.     modCount++;
  6.     size--;
  7.     // If strictly internal, copy successor"s element to p and then make p
  8.     // point to successor.
  9.     if (p.left != null && p.right != null) {
  10.         Entry s = successor(p);
  11.         p.key = s.key;
  12.         p.value = s.value;
  13.         p = s;
  14.     } // p has 2 children
  15.     // Start fixup at replacement node, if it exists.
  16.     Entry replacement = (p.left != null ? p.left : p.right);
  17.     if (replacement != null) {
  18.         // Link replacement to parent
  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.         // Null out links so they are OK to use by fixAfterDeletion.
  27.         p.left = p.right = p.parent = null;
  28.         // Fix replacement
  29.         if (p.color == BLACK)
  30.             fixAfterDeletion(replacement);
  31.     } else if (p.parent == null) { // return if we are the only node.
  32.         root = null;
  33.     } else { //  No children. Use self as phantom replacement and unlink.
  34.         if (p.color == BLACK)
  35.             fixAfterDeletion(p);
  36.         if (p.parent != null) {
  37.             if (p == p.parent.left)
  38.                 p.parent.left = null;
  39.             else if (p == p.parent.right)
  40.                 p.parent.right = null;
  41.             p.parent = null;
  42.         }
  43.     }
  44. }
  45. /**
  46.  * Returns the successor of the specified Entry, or null if no such.
  47.  */
  48. static  TreeMap.Entry successor(Entry t) {
  49.     if (t == null)
  50.         return null;
  51.     else if (t.right != null) { // ① ②
  52.         Entry p = t.right;
  53.         while (p.left != null)
  54.             p = p.left;
  55.         return p;
  56.     } else { //③ ④ ⑤
  57.         Entry p = t.parent;
  58.         Entry ch = t;
  59.         while (p != null && ch == p.right) {
  60.             ch = p;
  61.             p = p.parent;
  62.         }
  63.         return p;
  64.     }
  65. }

successor()可以简单的理解为“一个升序数组a[index],successor即为a[index+1]”。相对的还有prodecessor()。源码中可能出现的情况抽象如下图（while只举一次循环为例）。

deleteEntry调用successor时，由于right != null，所以不会出现③ ④ ⑤的情况。基本思路就是找到“a[index+1]”（p）替换待删节点，然后使“a[index+1]”的子节点（replacement）指向其父节点（Link replacement to parent）,最后清p、fixAfterDeletion修复红黑树性。

如果觉得这个看懂了，可以挑战下HashMap.TreeNode.removeTreeNode()。

说点什么：

TreeMap 有序；非线程安全；key值不支持null...;

实现了NavigableMap接口(见文末②)，NavigableMap具有了针对给定搜索目标返回最接近匹配项的导航方法。

</>复制代码 
  1. 如： lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、大于给定键的 Map.Entry对象，如果不存在这样的键，则返回 null。

实现了SortedMap接口：它用来保持键的有序顺序,也提供了范围检索的一些方法;

</>复制代码 
  1. 如： headMap、subMap、tailMap分别返回小于结束键、大于或等于开始和小于结束键、大于或等于开始键的Map.Entry对象。
  2. 添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现。TreeMap类是它的唯一一份实现。

更多有意思的内容，欢迎访问笔者小站： rebey.cn

知识点：

①Java中自然排序和比较器排序详解:Comparable与Comparator；

②计算机程序的思维逻辑 (43) - 剖析TreeMap：方法应用举例;

云服务器 GPU云服务器 一带一路 系列之 系列之二 架构之坑系列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67159.html

相关文章

  • 【java源码一带一路系列】之LinkedHashMap.afterNodeAccess()

    摘要：如今行至于此，当观赏一方。由于所返回的无执行意义。源码阅读总体门槛相对而言比，毕竟大多数底层都由实现了。比心可通过这篇文章理解创建一个实例过程图工作原理往期线路回顾源码一带一路系列之源码一带一路系列之源码一带一路系列之 本文以jdk1.8中LinkedHashMap.afterNodeAccess()方法为切入点，分析其中难理解、有价值的源码片段（类似源码查看是ctrl+鼠标左键的过程...

    levy9527 评论0 收藏0

  • 【java源码一带一路系列】之ArrayList

    摘要：一路至此，风景过半。与虽然名字各异，源码实现基本相同，除了增加了线程安全。同时注意溢出情况处理。同时增加了考虑并发问题。此外，源码中出现了大量泛型如。允许为非线程安全有序。 一路至此，风景过半。ArrayList与Vector虽然名字各异，源码实现基本相同，除了Vector增加了线程安全。所以作者建议我们在不需要线程安全的情况下尽量使用ArrayList。下面看看在ArrayList源...

    RebeccaZhong 评论0 收藏0

  • 【java源码一带一路系列】之HashSet、LinkedHashSet、TreeSet

    摘要：同样在源码的与分别见看到老朋友和。这样做可以降低性能消耗的同时，还可以减少序列化字节流的大小，从而减少网络开销框架中。使用了反射来寻找是否声明了这两个方法。十进制和，通过返回值能反应当前状态。 Map篇暂告段落，却并非离我们而去。这不在本篇中你就能经常见到她。HashSet、LinkedHashSet、TreeSet各自基于对应Map实现，各自源码内容较少，因此归纳为一篇。 HashS...

    UCloud 评论0 收藏0

  • 【java源码一带一路系列】之HashMap.compute()

    摘要：本篇涉及少许以下简称新特性，请驴友们系好安全带，准备开车。观光线路图是在中新增的一个方法，相对而言较为陌生。其作用是把的计算结果关联到上即返回值作为新。实际上，乃缩写，即二元函数之意类似。 本文以jdk1.8中HashMap.compute()方法为切入点，分析其中难理解、有价值的源码片段（类似源码查看是ctrl+鼠标左键的过程）。本篇涉及少许Java8（以下简称J8）新特性，请驴友们...

    wapeyang 评论0 收藏0

  • 【java源码一带一路系列】之HashMap.putAll()

    摘要：观光线路图将涉及到的源码全局变量哈希表初始化长度默认值是负载因子默认表示的填满程度。根据是否为零将原链表拆分成个链表，一部分仍保留在原链表中不需要移动，一部分移动到原索引的新链表中。 前言 本文以jdk1.8中HashMap.putAll()方法为切入点，分析其中难理解、有价值的源码片段（类似ctrl+鼠标左键查看的源码过程）。✈观光线路图：putAll() --> putMapEnt...

    chanjarster 评论0 收藏0

发表评论

登陆后可评论

0条评论

Bamboy

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<