The list is sorted, but then you put it in a "sorted" map. However, HashMap is not sorted, and it will never be sorted. There is currently only one map that is sorted, and that is TreeMap.
The problem is that any comparator for a TreeMap needs a reference to the TreeMap to be able to sort it. However, it needs to provide the comparator to the TreeMap constructor, so you can't put a reference to the TreeMap right away.
The following may work (I haven't tested it):
The TreeMapComparator should be a static nested class in your current class; its definition is not needed outside of it, only the fact that it is a Comparator.
Edit: of course you can use a LinkedHashMap; that keeps the insertion order. It won't stay ordered if you put new items though, but I'm not quite sure my above solution will handle that well.