Here's a red-black tree:
Imagine that the integer values of the nodes are the keys of the map. When you ask TreeMap
to retrieve the entry for key '7
', it looks if the key is less than or greater than the key of the root node. Since it's less, it then moves to the left child of that node and compares the keys again. '7
' is greater than '2
', so it moves to the right child of that node and compares the keys again. It then finds that that node has the same key, so it returns that node.
Changing the way that keys compare to each other does not change the current structure of the tree. If the Comparator
you've passed in suddenly changes the order of its keys so that '7
' is considered greater than '11
', the search will try to find the entry to the right of the root node. It will report that the entry does not exist, even though you added it earlier.
This means that changing the way that keys compare to each other (because the average rating of a movie changed) possibly makes the map lose entries. Not only does it lose entries, but it may not longer add new entries correctly, because the tree is not in a valid state. It's complete behavior becomes undefined.
Allowing a Comparator
to change the way it orders elements is the same to a TreeMap
as allowing a key to return different hash codes is to a HashMap