英文:
Do TreeMaps automatically sort keys?
问题
使用HashMap存储Player对象和整数时，我在对HashMap进行排序时遇到了困难，并且有人建议我使用TreeMap，在阅读了一些文档后，似乎它是基于放入的键对地图进行排序的。
因此从理论上讲，如果我将TreeMap制作为<Integer，Player>，它会自动为我对地图进行排序？
英文:
While using a HashMap to store a Player object and an Integer, I got stuck while sorting the HashMap and was recommended to use a TreeMap, after reading some of the documentation it seems that it sorts the map based off of the keys put in.
So theoretically, if I made the TreeMap as <Integer, Player> it would sort the map for me?
答案1
得分: 2
是的，如果您调用yourmap.keySet().iterator()，它会根据键的顺序以升序返回元素。这要么是它们的自然顺序，要么是您定义的比较器。
在内部，它可能会像这样使用中序遍历：
您可以看到，在每个节点的左子树上，值都较小，在右侧则较大。因此，如果您首先列出左侧的元素，然后是节点本身，然后是右侧的所有元素，您就会得到升序排列。如果您对每个节点递归应用此规则，您将获得所需的迭代器。
您可以在这里找到如何在Java中使用的示例这里。
请记住，HashMap 的查找复杂度为 O(1)，但 TreeMap 的为 O(log(n))。除非您依赖于键的顺序，否则应该优先使用 HashMap，因为它更快。
英文:
Yes, if you call yourmap.keySet().iterator(), it returns the elements in ascending order based on the keys. This is either their natural order or a comparator that you defined.
Internally, it will propably use Inorder-Traversal like this:
You see, that on the left subtree of each node the values are smaller and on the right side they are bigger. Therefore, if you first list the elements on the left, then the node itself, then all on the right, you have it in ascending order. If you apply this rule for every node recursively, you receive your wanted iterator.
You can find an example on how to use this in Java here.
Remember that a HashMap has a lookup of O(1), but a TreeMap has O(log(n)). Unless you rely on the ordering of keys, you should favor HashMap becase it's faster.
答案2
得分: 1
TreeMap会根据键进行排序。TreeMap在其键上执行自然顺序排序，还允许您使用Comparator进行自定义排序实现。我们可以在映射创建时提供Comparator，具体取决于使用哪个构造函数。
英文:
TreeMap are sorted by key. TreeMap performs sorting in natural order on its key, it also allows you to use Comparator for custom sorting implementation. We can provide Comparator at map creation time, depending on which constructor is used.
答案3
得分: 0
HashMap不对元素排序提供任何保证。然而，TreeMap被实现为树结构（红黑树），在其中元素存储和遍历是有序的。检索复杂度为O(log n)，相比之下，HashMap的复杂度为O(1)。
英文:
HashMap-s don't make any guarantee on element ordering. However a TreeMap is implemented as a tree structure. (a red-black tree, which would be near-balanced). Elements are stored and traversed in order. Retrieval complexity is O(log n), compared to the HashMap's O(1).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论