8

As we know, there is the concept of BiMap and MultiMap but is there a MultiBiMap ? so what do I mean by this. In MultiMap you have one-to-many relationship between K and V, a single key can be associated to multiple value, hence the name. In BiMap you have K,V pair which is bi-directional mean you can get V,K relationship as well. Like having a two regular maps but synchronized. I need a bi directional multi map where you combine these two concepts.

AR5HAM
  • 1,220
  • 11
  • 19
  • if you don't need to preserve the actual pairs, you can get the same affect (or implement your own) using two multimaps (one going each way) – Thayne Dec 05 '13 at 03:41
  • well the issue is I wanted something simple like this: multiBiMap where if you have a key you get all the values associated to with that key and if you have the value you can get the key. But as you said it would be possible to implement it. I just didn't want to reinvent the wheel if it already exists out there. – AR5HAM Dec 05 '13 at 03:43
  • Are the values guaranteed to be unique? – Thayne Dec 05 '13 at 03:51
  • "If you have a key you get all the values associated to with that key and if you have the value you can get the key." By _the_ value, do you mean one of the values associated with a specific key? – gdejohn Dec 05 '13 at 03:51
  • Yes by "values" here I mean values associated with a specific key. so basically we have a one-to-many relationship. One Key to many values. – AR5HAM Dec 05 '13 at 03:58
  • No, I mean when you say "get the key if you have the value," are you talking about one of the values associated with the key? Like, `"a"->[1, 2, 3]`, `getKeyForValue(2) == "a"`? – gdejohn Dec 05 '13 at 04:04
  • Can the same value be associated with multiple keys? In other words, do you need a many-to-many relationship? – gdejohn Dec 05 '13 at 04:42
  • The OP said he needs a one-to-many relationship. – Thayne Dec 05 '13 at 05:00
  • 1
    The question is ambiguous. The overall relationship is one-to-many if the values are unique. But if a value can be associated with multiple keys, then the relationship should be many-to-many, where he'd presumably want a one-key-to-many-values view in one direction and a one-value-to-many-keys view in the other direction. If it's one-to-many and you can have both `"a"->[1, 2]` and `"b"->[2, 3]`, then what key is associated with the value `2`? – gdejohn Dec 05 '13 at 05:24
  • @gdejohn yes your description / example is correct. getKeyForValue(2) should return "a". Also as you mentioned yes a value can potentially be associated with multiple keys. There is an API that I found by google that implements both BiMap and MultiMap not both combined. Here is the link [link] (https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained) – AR5HAM Dec 05 '13 at 05:30
  • So, if you have both `"a"->[1, 2]` and `"b"->[2, 3]`, then you want `getInverse(2) == ["a", "b"]`? And do you need it to be mutable? – gdejohn Dec 05 '13 at 05:37
  • yes in-case a value is mapped to more than one key you will get back set of keys it maps to. In this case "a" and "b". The google API for the biMap returns only the inverse view, Which maps each of the bimap's values to its associated key. But again in their implementation a BiMap is not a multiMap. – AR5HAM Dec 05 '13 at 05:40
  • Do you need it to be mutable? – gdejohn Dec 05 '13 at 05:43
  • yes that would be really nice if it would be mutable. – AR5HAM Dec 05 '13 at 05:47
  • Then I'm not aware of anything that suits your needs out of the box. Guava's ImmutableMultimap provides an inverse view, but that won't do. Shouldn't be too hard to come up with a simple implementation, though. Would you like me to take a crack at it and post an answer? – gdejohn Dec 05 '13 at 06:25
  • Sure, but I would also like to start a gitHub project for this. Another issues that I can see in Guava (and I haven't looked at their implementations yet but I assume is the case) all their implementation is using java collection libraries that is not efficient to begin with since it is all array based. I am sure I can find few more people who would like to take a crack at this problem. – AR5HAM Dec 05 '13 at 06:56

1 Answers1

16
public class ManyToMany<K, V> {
    private final Map<K, Set<V>> values = new HashMap<>();

    private final Map<V, Set<K>> keys = new HashMap<>();

    public Set<V> getValues(K key) {
        return values.get(key);
    }

    public Set<K> getKeys(V value) {
        return keys.get(value);
    }

    public boolean put(K key, V value) {
        return values.computeIfAbsent(key, k -> new HashSet<>()).add(value)
            && keys.computeIfAbsent(value, v -> new HashSet<>()).add(key);
    }
}
gdejohn
  • 7,451
  • 1
  • 33
  • 49
  • I wrote something similar a little while a go but I do not like the fact that I had two lists but this should work too. – AR5HAM Dec 05 '13 at 07:29
  • yes I agree but it would be nice to have it implemented and abstracted for you. Instead of writing a it yourself. :-) – AR5HAM Sep 24 '20 at 19:39