Map of collections

Question

I wanted to make Map of Collections in Java, so I can make something like

public void add(K key, V value) {  
    if (containsKey(key)) {
        get(key).add(value);
    } else {
        Collection c = new Collection();
        c.add(value);
        put(key, value);
    }
}

I've tried to make it with something like

public class CollectionMap<K, C extends Collection<V>> extends HashMap<K, C>

but compiler complains about the <V> part, and there would still be an issue of making proper new collection.

At the moment, I've made two classes: SetMap that look like this

 1: public class SetMap<K, V> extends HashMap<K, Set<V>> {
 2: 
 3:    public void add(K key, V value) {
 4:        if (containsKey(key)) {
 5:            get(key).add(value);
 6:        } else {
 7:            Set<V> list = new HashSet<V>();
 8:            list.add(value);
 9:            put(key, list);
10:        }
11:    }
12:
13: }

and ListMap looks pretty much the same except the line 7 where I make new ArrayList. This sort of duplication is small enough to be tolerable, but question remains is this sort of "nested generics" possible in Java?

EDIT:

As erickson said, solution is in <A, B extends Something<A>> rather than just <B extends Something<A>>

so code can look something like

public abstract class CollelctionMap<K, V, C extends Collection<V>> extends HashMap<K, C> {

    protected abstract C newCollection();

    public void add(K key, V value) {
        if (containsKey(key)) {
            get(key).add(value);
        } else {
            C c = newCollection();
            c.add(value);
            put(key, c);
        }
    }
}

and ListMap and SetMap only provide proper collection

Answer 1

When I want to make a map of collections, I do this:

Map<K, Collection<V>> map = new HashMap<K, Collection<V>>();

As a quick-and-dirty way to support your special add method, I would suggest the following:

public abstract class CollectionHashMap<K, V>
  extends HashMap<K, Collection<V>>
{

  protected abstract Collection<V> createCollection();

  public void add(K key, V val)
  {
    Collection<V> c = get(key);
    if (c == null)
      put(key, c = createCollection());
    c.add(val);
  }

}

Concrete implementations will depend on the semantics you want for your Collection. The two most likely, as noted in the question, would be Set and List semantics. As an example Set implementation:

public class HashSetMap<K, V>
  extends CollectionHashMap<K, V>
{

  protected HashSet<V> createCollection()
  {
    return new HashSet<V>();
  }

}

This is a good example to show why inheritance has problems. If, later, you want a tree-based CollectionMap, you'll have to reimplement everything, proliferating new classes. As an alternative, consider using composition. Extend AbstractMap and delegate to another map implementation that you supply in the constructor.

Answer 2

If it's an option, you may want to just use the Google Collections API - http://code.google.com/p/google-collections/.

Even if you can't use it, maybe having a look at how they implemented their MultiMaps would help you with your implementation.

Answer 3

There is a problem with your code:

Collection c = new Collection();

Cannot be instantiated.

I think the next piece of code will solve your problem:

public class CollectionMap<K, V> extends HashMap<K, Collection<V>> {


    ...
    ...
    ...


    public void add(K key, V value) {
        if (containsKey(key)) {
            get(key).add(value);
        } else {
            Collection<V> c = new ArrayList<V>();
            c.add(value);
            super.put(key, c);
        }
    }
}

Answer 4

Apache Commons Collections also offers a MultiMap, but it's pre-JDK 1-.5, so you'll have no generics safety there. You can wrap it in a Collections.checkedMap(Key.class, Value.class, collection) for run-time safety. If you can use Google's Colelction API, it offers an even slicker MultiMap with all the generics, bells and whistles.

Answer 5

If possible use Google collections. Guys have done a wonderful job there.

Here is another solution.

abstract class MultiMap<K, V> {

    private Map<K, Collection<V>> entries = new LinkedHashMap<K, Collection<V>>();

    public void put(K key, V value) {
        Collection<V> values = entries.get(key);
        if (values == null) {
            entries.put(key, values = newValueCollection());
        }
        values.add(value);
    }

    // other methods
    // ..

    abstract Collection<V> newValueCollection();



    // Helper methods to create different flavors of MultiMaps

    public static <K, V> MultiMap<K, V> newArrayListMultiMap() {
        return new MultiMap<K, V>() {
            Collection<V> newValueCollection() {
                return new ArrayList<V>();
            }
        };
    }

    public static <K, V> MultiMap<K, V> newHashSetMultiMap() {
        return new MultiMap<K, V>() {
            Collection<V> newValueCollection() {
                return new HashSet<V>();
            }
        };
        }

 }

You can use it like

MultiMap<String, Integer> data = MultiMap.newArrayListMultiMap();
data.put("first", 1);
data.put("first", 2);
data.put("first", 3);