Home > Software design >  Does a TreeMap change ordering dynamically?
Does a TreeMap change ordering dynamically?

Time:04-15

Let's say I put in an entry in to my map which holds an object as a key:

treeNode.put(someObject,someValue); 

then some time later I get that entry, and change the object so that now if resorted it lands somewhere else in the map.

treeNode.get(someObject); 
someObject.change();

Do I have to remove the old entry in the map, and put again for the map to remain consistent with the new key?

CodePudding user response:

Elements within a TreeMap are stored according to their natural ordering or to the Comparator provided at construction time. This rule is only applied when an element is added to the data structure.

The TreeMap does not perform any observation of its keys to rearrange itself. If one of your keys' internal state changes, you would have to update your TreeMap manually in order to respect its proper structure.

Here's an example:

public class Test {
    public static void main(String[] args) {
        TreeMap<StringBuilder, Integer> treeMap = new TreeMap<>();

        StringBuilder str1 = new StringBuilder("a");
        treeMap.put(str1, 32);

        StringBuilder str2 = new StringBuilder("b");
        treeMap.put(str2, 15);

        StringBuilder str3 = new StringBuilder("c");
        treeMap.put(str3, 78);

        System.out.println("Original");
        for (Map.Entry entry : treeMap.entrySet()) {
            System.out.printf("%s => %d%n", entry.getKey(), entry.getValue());
        }

        System.out.println("\nUpdated");
        str2.replace(0, str2.length(), "z");
        for (Map.Entry entry : treeMap.entrySet()) {
            System.out.printf("%s => %d%n", entry.getKey(), entry.getValue());
        }

        treeMap.remove(str2);
        treeMap.put(str2, 15);
        System.out.println("\nRearranged");
        for (Map.Entry entry : treeMap.entrySet()) {
            System.out.printf("%s => %d%n", entry.getKey(), entry.getValue());
        }
    }
}

CodePudding user response:

Yes, you do. There is no possible way for TreeMap to know that a value's position in the map should have changed.

TreeMap doesn't say this in so many words, but Map specifies that

The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.

and TreeMap documents that it uses the specified comparator instead of equals.

  • Related