clojure中的双向地图？

Question

在clojure中实现双向地图的最佳方式是什么？ （通过双向映射，我的意思是一个可以同时提供A-> B和B-> A访问的关联映射，所以实际上，这些值本身就是在相反方向走向的关键。）

I假设我可以设置两个地图，每个方向一个地图，但是有没有更习惯性的做法？

我在这里我们希望有一个双射，这意味着没有两个键可以映射到相同的值的情况下，并在该条件在未实施的情况下都感兴趣。

Answer 1

你总是可以使用Java库对于这一点，就像在Apache commons的收藏品之一。 TreeBidiMap实现了java.util.Map，所以它无需任何努力即可使用。

user> (def x (org.apache.commons.collections.bidimap.TreeBidiMap.)) 
#'user/x 
user> (.put x :foo :bar) 
nil 
user> (keys x) 
(:foo) 
user> (.getKey x :bar) 
:foo 
user> (:foo x) 
:bar 
user> (map (fn [[k v]] (str k ", " v)) x) 
(":foo, :bar") 

有些东西虽然不会工作，像assoc和dissoc，因为他们希望永久收藏和TreeBidiMap是可变的。

如果你真的想这样做，在本地Clojure中，你可以使用元数据来保持反方向的哈希值。这仍然会使你的内存需求增加一倍，并且每增加一次和删除时间就会增加一倍，但查找速度会很快，至少所有东西都会被捆绑在一起。

(defn make-bidi [] 
    (with-meta {} {})) 

(defn assoc-bidi [h k v] 
    (vary-meta (assoc h k v) 
      assoc v k)) 

(defn dissoc-bidi [h k] 
    (let [v (h k)] 
    (vary-meta (dissoc h k) 
       dissoc v))) 

(defn getkey [h v] 
    ((meta h) v)) 

您可能必须实现一堆其他功能才能获得完整的功能。不知道这种方法有多可行。

user> (def x (assoc-bidi (make-bidi) :foo :bar)) 
#'user/x 
user> (:foo x) 
:bar 
user> (getkey x :bar) 
:foo 

Answer 2

在大多数情况下，我发现了以下工作正常：

(defn- bimap 
    [a-map] 
    (merge a-map (clojure.set/map-invert a-map))) 

这将只是原来的地图倒地图合并成一个新的地图，那么你可以使用普通的地图操作结果。

它很快速和肮脏，但显然你应该避免这种实现，如果任何键可能与任何值相同或者a-map中的值不唯一。

Answer 3

我们可以按如下重构这个问题：
鉴于我们希望能够通过双方a和b快速查找元组的元组([a1 b1] [a2 b2] ...)列表。所以我们想要映射a -> [a b]和b -> [a b]。这意味着至少元组可以共享。如果我们考虑实现它，那么它很快就会变得明显，这是一个内存数据库表，列A和B由两列索引。

所以，你可以只使用一个轻量级的内存数据库。

对不起，我不熟悉Java平台足以建议一些具体的事情。因为Datomic想到，但它可能是这个特殊用例的矫枉过正。另一方面，它具有不变性，根据你对布赖恩的回答的评论，你对此似乎是可取的。