How can I sort a treemap using its values rather than the key?
You cannot as the TreeMap's comparator is run against the keys only, e.g. see this constructor.
Anyway, you can use multiple Collections, use the TreeMap (or rather HashMap) for looking up elements by keys, and have a SortedSet to iterate on the values.