Reply

Collections: Multivalue-per-key Maps

At 1:28 PM on Feb 1, 2005, Sebastian Ferreyra wrote:

The Java Collections API in java.util.* is a very powerful and fundamental toolkit for managing sets of objects and is used in practically all facets of software development, from low-level caches, to O/R mapping, to GUIs.

However, occasionally we have needs that extend beyond the basic functionality provided in the API. One very common need not handled by the collections framework is to provide maps that can hold many values for a particular key, much like databases feature non-unique key indexes. Having such a collection class would make this job very simple in Java.

Collections are like LEGOs(tm)

It turns out, thanks to the well thought out architecture of the Collections classes, that it is indeed very easy to add this functionality using the existing classes as building blocks. And the new generics language extensions makes this job a lot easier and more pleasant too.

The basic idea is quite simple actually. To hold many values per key, just hold these values in a List and store the lists in a Map > with the corresponding key. This is actually very simple to manage and can be done quite comfortably without abstracting the functionality in a class. but doing so comes in handy when we need reusability.

For the implementation I chose containment instead of inheritance. The class does not implement any of the Collections intefaces because none of them quite fit the functional model. The one that comes closest however is the Map interface and I modelled the API in my class to closely follow its usage guidelines.

Developer General's Warning

I will note however that by no means this class provides all the behaviour a developer might need from such a non-unique key map. This tip is mostly aimed at showing how to use collections and generics as basic building blocks for more sophisticated generic collections classes.

Furthermore, it probably would be a good idea for a complete implementation to abstract the functionality into a generic interface with different implementations. In this example I use a HashMap of ArrayLists, but versions using HashTables, ConcurrentHashTables, LinkedLists, Vectors, etc. might be desired too, and despite the different access strategies they would all share the same external interface.

Finally, the Code

public class Index<K,V> {
    HashMap<K,ArrayList<V>> map;
 
    public Index() {
        map = new HashMap<K,ArrayList<V>>();
    }
    public void put(K key, V value) {
        ArrayList<V> list = map.get(key);
        if ( list == null ) {
            list = new ArrayList<V>();
            map.put(key, list);
        }
        list.add(value);
    }
    public V get(K key, int index) {
        ArrayList<V> list = map.get(key);
        if ( list == null ) {
            return null;
        }
        if ( index >= list.size() || index < 0 ) {
            return null;
        }
        return list.get(index);
    }
    // other possible useful methods would be:
    // boolean remove(K key, V targetValue);
    public V remove(K key, int index) {
        ArrayList<V> list = map.get(key);
        if ( list == null ) {
            return null;
        }
        if ( index >= list.size() || index < 0 ) {
            return null;
        }
        V v = list.remove(index);
        if ( list.size() == 0 ) {
            map.remove(key);
        }
        return v;
    }
 
    // instead of using .size() I split the 
    // functionality into three different
    // methods returning the necessary
    // information. Remember, now the number
    // of keys could be less than the number
    // of values.
    public int getValueCount() {
        int size = 0;
        for ( ArrayList<V> list : map.values()) {
            size += list.size();
        }
        return size;
    }
    public int getValueCount(K key) {
        ArrayList<V> list = map.get(key);
        if ( list == null ) {
            return 0;
        }
        return list.size();
    }
    public int getKeyCount() {
        return map.size();
    }
 
    public boolean containsKey(K key) {
        return map.containsKey(key);
    }
    public boolean containsKey(K key, int index) {
        ArrayList<V> list = map.get(key);
        if ( list == null ) {
            return false;
        }
        if ( index >= list.size() || index < 0 ) {
            return false;
        }
        return true;
    }
    public boolean isEmpty() {
        return map.isEmpty();
    }
 
    // other possible useful methods would be:
    // boolean containsValue(K key, V targetValue);
    public boolean containsValue(V targetValue) {
        for ( ArrayList<V> list : map.values()) {
            for ( V value : list ) {
                if ( targetValue == value )
                    return true;
            }
        }
        return false;
    }
    
    public void clear() {
        map.clear();
    }
}

Sebastian Ferreyra