1. Overview
1.概述
In this article, we are going to explore TreeMap implementation of Map interface from Java Collections Framework(JCF).
在这篇文章中，我们将探讨Java集合框架（JCF）中Map接口的TreeMap实现。
TreeMap is a map implementation that keeps its entries sorted according to the natural ordering of its keys or better still using a comparator if provided by the user at construction time.
TreeMap是一个地图实现，它根据其键的自然排序来保持其条目的排序，如果用户在构建时提供了一个比较器，则更好。
Previously, we have covered HashMap and LinkedHashMap implementations and we will realize that there is quite a bit of information about how these classes work that is similar.
之前，我们已经介绍了HashMap和LinkedHashMap的实现，我们会发现这些类的工作方式有相当多的信息是相似的。
The mentioned articles are highly recommended reading before going forth with this one.
在进行这项工作之前，强烈建议阅读上述文章。
2. Default Sorting in TreeMap
2.在TreeMap中的默认排序
By default, TreeMap sorts all its entries according to their natural ordering. For an integer, this would mean ascending order and for strings, alphabetical order.
默认情况下，TreeMap根据其自然排序对其所有条目进行排序。对于整数来说，这意味着升序，对于字符串来说，则是按字母顺序。
Let’s see the natural ordering in a test:
让我们来看看测试中的自然排序。
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}Notice that we placed the integer keys in a non-orderly manner but on retrieving the key set, we confirm that they are indeed maintained in ascending order. This is the natural ordering of integers.
请注意，我们以非有序的方式放置了整数键，但在检索键集时，我们确认它们确实是以升序的方式保持。这就是整数的自然排序。
Likewise, when we use strings, they will be sorted in their natural order, i.e. alphabetically:
同样地，当我们使用字符串时，它们将按自然顺序排序，即按字母顺序排序。
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
TreeMap<String, String> map = new TreeMap<>();
map.put("c", "val");
map.put("b", "val");
map.put("a", "val");
map.put("e", "val");
map.put("d", "val");
assertEquals("[a, b, c, d, e]", map.keySet().toString());
}TreeMap, unlike a hash map and linked hash map, does not employ the hashing principle anywhere since it does not use an array to store its entries.
TreeMap与哈希图和链接哈希图不同，它没有在任何地方采用哈希原理，因为它没有使用数组来存储其条目。
3. Custom Sorting in TreeMap
3.在TreeMap中自定义排序
If we’re not satisfied with the natural ordering of TreeMap, we can also define our own rule for ordering by means of a comparator during construction of a tree map.
如果我们对TreeMap的自然排序不满意，我们也可以在构建树状图的过程中通过比较器来定义我们自己的排序规则。
In the example below, we want the integer keys to be ordered in descending order:
在下面的例子中，我们希望整数键按降序排列。
@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
TreeMap<Integer, String> map =
new TreeMap<>(Comparator.reverseOrder());
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString());
}A hash map does not guarantee the order of keys stored and specifically does not guarantee that this order will remain the same over time, but a tree map guarantees that the keys will always be sorted according to the specified order.
哈希图不保证存储的键的顺序，特别是不保证这个顺序会随着时间的推移而保持不变，但树形图保证键总是按照指定的顺序进行排序。
4. Importance of TreeMap Sorting
4、TreeMap排序的重要性
We now know that TreeMap stores all its entries in sorted order. Because of this attribute of tree maps, we can perform queries like; find “largest”, find “smallest”, find all keys less than or greater than a certain value, etc.
我们现在知道，TreeMap以排序的方式存储其所有条目。由于树形图的这一属性，我们可以执行这样的查询；找到 “最大的”，找到 “最小的”，找到所有小于或大于某个值的键，等等。
The code below only covers a small percentage of these cases:
下面的代码只涵盖了这些情况中的一小部分。
@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
Integer highestKey = map.lastKey();
Integer lowestKey = map.firstKey();
Set<Integer> keysLessThan3 = map.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet();
assertEquals(new Integer(5), highestKey);
assertEquals(new Integer(1), lowestKey);
assertEquals("[1, 2]", keysLessThan3.toString());
assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}5. Internal Implementation of TreeMap
5.TreeMap的内部实现
TreeMap implements NavigableMap interface and bases its internal working on the principles of red-black trees:
TreeMap实现了NavigableMap接口，并以红黑树的原则作为其内部工作基础。
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.SerializableThe principle of red-black trees is beyond the scope of this article, however, there are key things to remember in order to understand how they fit into TreeMap.
红黑树的原理超出了本文的范围，然而，为了理解它们如何融入TreeMap，有一些关键事项需要记住。
First of all, a red-black tree is a data structure that consists of nodes; picture an inverted mango tree with its root in the sky and the branches growing downward. The root will contain the first element added to the tree.
首先，红黑树是一个由节点组成的数据结构；想象一下一棵倒置的芒果树，它的根在天上，树枝向下生长。根部将包含添加到树上的第一个元素。
The rule is that starting from the root, any element in the left branch of any node is always less than the element in the node itself. Those on the right are always greater. What defines greater or less than is determined by the natural ordering of the elements or the defined comparator at construction as we saw earlier.
规则是，从根部开始，任何节点的左边分支的任何元素总是小于节点本身的元素。右边的则总是大于。什么定义大于或小于是由元素的自然排序或如我们前面看到的构造时定义的比较器决定的。
This rule guarantees that the entries of a treemap will always be in sorted and predictable order.
这条规则保证了树状图的条目总是以分类和可预测的顺序出现。
Secondly, a red-black tree is a self-balancing binary search tree. This attribute and the above guarantee that basic operations like search, get, put and remove take logarithmic time O(log n).
其次，红黑树是一种自平衡的二进制搜索树。这一属性和上述情况保证了搜索、获取、放置和删除等基本操作需要对数时间O（log n）。
Being self-balancing is key here. As we keep inserting and deleting entries, picture the tree growing longer on one edge or shorter on the other.
自我平衡是这里的关键。当我们不断插入和删除条目时，想象一下这棵树在一条边上变长或在另一条边上变短。
This would mean that an operation would take a shorter time on the shorter branch and longer time on the branch which is furthest from the root, something we would not want to happen.
这意味着一个操作在较短的分支上花费的时间较短，而在离根部最远的分支上花费的时间较长，这是我们不希望发生的。
Therefore, this is taken care of in the design of red-black trees. For every insertion and deletion, the maximum height of the tree on any edge is maintained at O(log n) i.e. the tree balances itself continuously.
因此，这一点在红黑树的设计中得到了照顾。对于每一次插入和删除，任何边缘上的树的最大高度都保持在O(log n)，即树不断地自我平衡。
Just like hash map and linked hash map, a tree map is not synchronized and therefore the rules for using it in a multi-threaded environment are similar to those in the other two map implementations.
就像哈希图和链接哈希图一样，树形图不是同步的，因此在多线程环境中使用它的规则与其他两种图的实现类似。
6. Choosing the Right Map
6.选择正确的地图
Having looked at HashMap and LinkedHashMap implementations previously and now TreeMap, it is important to make a brief comparison between the three to guide us on which one fits where.
在看过HashMap和LinkedHashMap的实现，以及现在的TreeMap之后，有必要对这三者做一个简单的比较，以指导我们哪一个适合哪里。
A hash map is good as a general-purpose map implementation that provides rapid storage and retrieval operations. However, it falls short because of its chaotic and unorderly arrangement of entries.
哈希图作为一种通用的地图实现，提供快速的存储和检索操作，是很好的。然而，由于它的条目排列混乱无序，所以它的功能不足。
This causes it to perform poorly in scenarios where there is a lot of iteration as the entire capacity of the underlying array affects traversal other than just the number of entries.
这导致它在有大量迭代的情况下表现不佳，因为底层数组的整个容量会影响到遍历，而不仅仅是条目的数量。
A linked hash map possesses the good attributes of hash maps and adds order to the entries. It performs better where there is a lot of iteration because only the number of entries is taken into account regardless of capacity.
链接哈希图拥有哈希图的良好属性，并为条目添加了顺序。在有大量迭代的情况下，它的表现更好，因为只考虑条目的数量而不考虑容量。
A tree map takes ordering to the next level by providing complete control over how the keys should be sorted. On the flip side, it offers worse general performance than the other two alternatives.
树形图通过提供对键的排序方式的完全控制，将排序提升到一个新的水平。反过来说，它的总体性能比其他两个方案更差。
We could say a linked hash map reduces the chaos in the ordering of a hash map without incurring the performance penalty of a tree map.
我们可以说，一个链接的哈希图减少了哈希图的混乱排序，而不会产生树状图的性能损失。
7. Conclusion
7.结论
In this article, we have explored Java TreeMap class and its internal implementation. Since it is the last in a series of common Map interface implementations, we also went ahead to briefly discuss where it fits best in relation to the other two.
在这篇文章中，我们探讨了Java TreeMap类及其内部实现。由于它是一系列常见的Map接口实现中的最后一个，我们也继续简要讨论了它与其他两个接口的最佳位置。
The full source code for all the examples used in this article can be found in the GitHub project.
本文使用的所有示例的完整源代码可以在GitHub项目中找到。