Можно передать на вход (в конструктор TreeMap) HashMap - и получим отсортированную версию последнего.
Если и ключ и значение являются строками, то объявить можно так:
Map< String, String > treeMap = new TreeMap< String, String >(Collections.reverseOrder());
добавление элементов:
treeMap.put("key", "value");
при добавлении TreeMap будет сам упорядочивать наши элементы по ключу.