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.