What Collection to use when searching and sorting

There are many posts regarding searching a Collection on stackoverflow. There are also many posts regarding sorting a Collection here. I am looking for a solution (data structure) that handles both. Maps are great for searching (i.e. map.containsKey(key), map.get(key)). ArrayLists are great for sorting (using a simple Comparator). My program adds elements to a HashMap (checking for dupes with .containsKey(key)). Then the map values get assigned to an Arraylist. This is simple (one line of开发者_如何学C code), yet terribly inefficient. It uses twice as much memory.

The program calls for unique elements, but what about duplicate elements? I have scanned the Javadocs and see that there are many Collection types for whatever flavor you need (map, list, table, set, tree, vector, priorityqueue-whatever that is). Is there ONE Java Collection that handles searching and sorting, including duplicate elements?

Have you considered TreeMap?

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

Have you tried a TreeMap. They going to be great for searching(O(ln n)) and are going to be sorted around a comparator that you can get using the .values() method.