Search code examples
javaminecraftbukkittreemap

Do TreeMaps automatically sort keys?

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 it would sort the map for me?

Solution

  • 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:
    https://en.wikipedia.org/wiki/Tree_traversal

    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.