Bidirectional multi-valued map in Java

Question

I am looking for a way to store key-value pairs. I need the lookup to be bidirectional, but at the same time I need to store multiple values for the same key. In other words, something like a BidiMap, but for every key there can be multiple values. For example, it needs to be able to hold pairs like: "s1"->1, "s2"->1, "s3"->2, and I need to be able to get the value mapped to each key, and for each value, get all the keys associated with it.

Answer 1

So you need support for many-to-many relationships? Closest you can get is Guava's Multimap like @Mechkov wrote - but more specifically Multimap combination with Multimaps.invertFrom. "BiMultimap" isn't implemented yet, but there is an issue requesting this feature in Google Guava library.

At this point you have few options:

1. If your "BiMultimap" is going to immutable constant - use Multimaps.invertFrom and ImmutableMultimap / ImmutableListMultimap / ImmutableSetMultimap (each of theese three has different collection storing values). Some code (example taken from app I develop, uses Enums and Sets.immutableEnumSet):

   public class RolesAndServicesMapping {
       private static final ImmutableMultimap<Service, Authority> SERVICES_TO_ROLES_MAPPING = 
            ImmutableMultimap.<Service, Authority>builder()
               .put(Service.SFP1, Authority.ROLE_PREMIUM)
               .put(Service.SFP, Authority.ROLE_PREMIUM)
               .put(Service.SFE, Authority.ROLE_EXTRA)
               .put(Service.SF, Authority.ROLE_STANDARD)
               .put(Service.SK, Authority.ROLE_STANDARD)
               .put(Service.SFP1, Authority.ROLE_ADMIN)
               .put(Service.ADMIN, Authority.ROLE_ADMIN)
               .put(Service.NONE, Authority.ROLE_DENY)
               .build();
   
       // Whole magic is here:
       private static final ImmutableMultimap<Authority, Service> ROLES_TO_SERVICES_MAPPING =
               SERVICES_TO_ROLES_MAPPING.inverse();
       // before guava-11.0 it was: ImmutableMultimap.copyOf(Multimaps.invertFrom(SERVICES_TO_ROLES_MAPPING, HashMultimap.<Authority, Service>create()));
   
       public static ImmutableSet<Authority> getRoles(final Service service) {
           return Sets.immutableEnumSet(SERVICES_TO_ROLES_MAPPING.get(service));
       }
   
       public static ImmutableSet<Service> getServices(final Authority role) {
           return Sets.immutableEnumSet(ROLES_TO_SERVICES_MAPPING.get(role));
       }
   }
   

2. If you really want your Multimap to be modifiable, it will be hard to maintain both K->V and V->K variants unless you will be modifying only kToVMultimap and call invertFrom each time you want to have its inverted copy (and making that copy unmodifiable to make sure that you accidentally don't modify vToKMultimap what wouldn't update kToVMultimap). This is not optimal but should do in this case.

3. (Not your case probably, mentioned as bonus): BiMap interface and implementing classes has .inverse() method which gives BiMap<V, K> view from BiMap<K, V> and itself after biMap.inverse().inverse(). If this issue I mentioned before is done, it will probably have something similar.

4. (EDIT October 2016) You can also use new graph API which will be present in Guava 20:

   As a whole, common.graph supports graphs of the following varieties:

   • directed graphs
   • undirected graphs
   • nodes and/or edges with associated values (weights, labels, etc.)
   • graphs that do/don't allow self-loops
   • graphs that do/don't allow parallel edges (graphs with parallel edges are sometimes called multigraphs)
   • graphs whose nodes/edges are insertion-ordered, sorted, or unordered

Answer 2

I hope using MultivaluedMap solves the problem. Please find the documentation from oracle below link.

http://docs.oracle.com/javaee/6/api/javax/ws/rs/core/MultivaluedMap.html

Answer 3

Using Google Guava we can write a primitive BiMulitMap as below.

import java.util.Collection;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

public class BiMultiMap<K,V> {

    Multimap<K, V> keyToValue = ArrayListMultimap.create();
    Multimap<V, K> valueToKey = ArrayListMultimap.create();

    public void putForce(K key, V value) {
        keyToValue.put(key, value);
        valueToKey.put(value, key);
    }

    public void put(K key, V value) {
        Collection<V> oldValue = keyToValue.get(key);
        if ( oldValue.contains(value) == false ) {
            keyToValue.put(key, value);
            valueToKey.put(value, key);
        }
    }

    public Collection<V> getValue(K key) {
        return keyToValue.get(key);
    }

    public Collection<K> getKey(V value) {
        return valueToKey.get(value);
    }

    @Override
    public String toString() {
        return "BiMultiMap [keyToValue=" + keyToValue + ", valueToKey=" + valueToKey + "]";
    }

}

Hope this will help some basic needs of the Bi-Directional Multi Map. Note the K and V needs to implement the hascode and equals method properly

Answer 4

What's wrong with having two maps, key->values, values->keys?

Answer 5

Hope I got you right

class A {
    long id;
    List<B> bs;
}

class B {
    long id;
    List<A> as;
}

Answer 6

Google's Guava MultiMap implementation is what i am using for these purposes.

Map<Key Collection<Values>> 

where Collection can be an ArrayList for example. It allows multiple values stored in a collection to be mapped to a key. Hope this helps!