Which Java object type (collection/list/set/whatever) do I want for this?

Question

I want to store a collection of objects that are keyed based upon a value they represent. These keys can be repeated. e.g.:

 [4] => Bob
 [5] => Mary
 [5] => Sue
 [9] => Steve
[10] => Jason
[10] => Michelle

Essentially, I want to loop through this and look at each key and say, "is there another object (person in this case) whose key is within 1 from the current key? If so, match them up and remove them from the collection." I'm going to iterate the "1" value in the example above until the collection is empty (or has one object remaining for odd-numbered scenarios).

I'm not convinced the way I'm trying to go about this is the best way, so I'm open to feedback too.

Answer 1

You want a Multimap. Guava provides this interface and various subinterfaces such as ListMultimap, SetMultimap and SortedSetMultimap depending on what kind of collection you want values to be stored in. It then provides various implementations such as ArrayListMultimap and HashMultimap, plus various utlities for use with them in Multimaps.

The traditional way of doing this in Java is something like Map<K, List<V>>, Map<K, Set<V>> etc., but maintaining the values collections is tedious and various operations that should be simple (such as just putting a value for a key) are much more complicated than they need to be.

Multimap is intended as a data structure specifically designed to model multiple values mapped to a single key (unlike Map). Given that, it makes operations as simple as you'd expect:

ListMultimap<Integer, String> m = ArrayListMultimap.create();
m.put(4, "Bob");
m.put(5, "Mary");
m.put(5, "Sue");
...

for (String name : m.get(5)) { ... } // iterates ["Mary", "Sue"]

If you wanted to ensure the same value isn't mapped to a single key twice and don't care about the order the values are in, you can use a SetMultimap instead of a ListMultimap, etc.

I'm not sure what you mean as far as "is there another object whose key is within 1 from the current key? If so, match them up and remove them from the collection." But if I'm reading it right, you could do something like this:

for (Integer key : m.keySet()) {
  Collection<String> people = m.get(key);
  Collection<String> peopleOneLower = m.get(key - 1); // empty if there are none
  ...
}

Alternatively you could do something with a TreeMultimap<Integer, String> which will have both its key set and value sets sorted.

Answer 2

How about a Map<Integer, List<String>>, in a sort of collision-avoiding manner. It would change your data set to look like:

 [4] => [Bob]
 [5] => [Mary, Sue]
 [9] => [Steve]
[10] => [Jason, Michelle]

You would have to change your iterator code a bit. You would use the indexes of the List elements as their "keys", and of course you'd have to add logic to initialize your Map with empty lists or make sure to check your Map values for null. It will sort of depend on how you generate your Map.

Answer 3

What about something like:

IDictionary<int,IList<Person>> 

I have to admin, I don't 100% follow the business logic, but if you can have multiple values for a single key, something like this should support it.

-- Edit -- Ignore this - it was pointed out to me that this was tagged as a java question. Therefore, the response with:

Map<Integer, List<String>>

is much more appropriate.

Answer 4

Maybe just something like: List where the CustomObject has your key and value and you sort the list by the key.

Since it sounds like you are processing them in order, I think a Map might be overkill since you would want to iterate over the keys in order and be removing items in pairs.