Sorted Map with non-unique keys

Question

What structure to use when one needs

1. ordering of elements by key

2. ability to hold non-unique keys

   Structure<Integer, String> struct = new Structure<Integer, String>;
   struct.add(3,"...");
   struct.add(1,"John");
   struct.add(2,"Edwin");
   struct.add(1,"Mary");
   struct.toString() == {key-> value;} [1->"John",1->"Mary",2->"Edwin",3->"..."]
   

Answer 1

If you want use the standard Java API, I would choose a TreeMap<Integer, Set<String>>.

• The elements are ordered by the keys since it is a SortedMap. From the docs:

  The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods).

• The structure allows for non-unique keys as you can let one key map to multiple objects.

This type of structure is called a sorted multi-map and there are several implementations that hide the details of creating initial sets when inserting for the first time etc. Have a look at Guava or Apache Commons for instance.

Depending on your needs, you could also have a SortedSet<Pair<Integer, String>>, where the elements are sorted on the left element in the pair. (Note that you would have write the Pair class yourself, but it shouldn't be more than a few lines.)

Answer 2

It sounds like you need perhaps a Map<Integer, List<String>> so each key maps to a list (or other collection) of strings.

Apache Commons has a MultiMap, which does the above without the hassle of you coding it.

 MultiMap mhm = new MultiHashMap();
 mhm.put(key, "A");
 mhm.put(key, "B");
 mhm.put(key, "C");
 Collection coll = (Collection) mhm.get(key);

coll will be a collection containing "A", "B", "C".

Google Collections will provide something similar, I suspect.