CODEWITHSUNDEEP
javadictionarydata-structuresbidirectional
Bastien
Bastien

Reputation: 658

Consistent and efficient bi-directional data structure implementation (Java)

I needed an implementation of a bi-directional map in Java so I tried to use BiMap and BidiMap from Guava and Commons. However, the inverse view capability is not maintained after a modification on an element. Here is an example with BiMap (same behavior with BidiMap) :

BiMap<Set<String>, Set<String>> map = HashBiMap.create();

Set<String> foo = new HashSet<>();
foo.add("foo");

Set<String> bar = new HashSet<>();
bar.add("bar");

map.put(foo, bar);

map.get(foo); // returns [bar], ok
map.inverse().get(map.get(foo)); // returns [foo], ok

map.get(foo).add("someString");

map.get(foo); // returns [bar, someString], ok
map.inverse().get(map.get(foo)); // returns null, not ok <=

Of course this behavior can be expected for an implementation using HashMaps but it illustrates the problem.

So the question is, is there a bi-directional data structure which can handle this kind of situation, with elements of arbitrary types, and still have a better average time complexity than an array of pairs?

EDIT : I'm not trying to solve this problem or avoid it, this is more of an academic question. I just want to know if such a data structure exists. That is, a data structure allowing bi-directional binding, mutable keys and with reasonable time complexity.

Upvotes: 0

Views: 644

Answers (1)

Marko Topolnik
Marko Topolnik

Reputation: 200148

Your trouble is not with bidirectional maps, but with the assumption that you are allowed to modify a map key. Keys are in fact fundamentally required to be stable at least regarding the behavior of their equals and hashCode methods (in case of a hashtable-backed map) or their comparison method (in case of a binary tree-backed map).

Perhaps you can consider removing an element, changing it, then inserting it back—that's one way to meet the constraints of implementation.

Upvotes: 3

Related Questions