我需要用Java实现双向地图,因此我尝试使用Guava和Commons中的BiMap和BidiMap。但是,对元素进行修改后,无法保持反视图功能。这是BiMap的示例(与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 <=


当然,对于使用HashMaps的实现来说,这种行为是可以预期的,但是它说明了这个问题。

因此,问题是,是否存在一个双向数据结构可以处理这种情况,并且具有任意类型的元素,并且平均时间复杂度仍然比成对的数组好?

编辑:我不是要解决这个问题或避免它,这更多是一个学术问题。我只想知道是否存在这样的数据结构。也就是说,一种数据结构允许双向绑定,可变密钥并具有合理的时间复杂度。

最佳答案

您的麻烦不是双向映射,而是假设您被允许修改映射键。实际上,从根本上要求键至少在其equalshashCode方法(在哈希表支持的映射的情况下)或其比较方法(在二进制树支持的映射的情况下)的行为方面保持稳定。

也许您可以考虑删除一个元素,然后对其进行更改,然后再将其插入回去,这是满足实现约束的一种方法。

10-05 21:10
查看更多