map - Clojure中的双向映射？

Question

在 clojure 中实现双向映射的最佳方法是什么？（通过双向映射，我的意思是一个关联映射，它可以提供 A->B 和 B->A 访问。因此，实际上，这些值本身将是相反方向的键。）

我想我可以设置两张地图，每个方向一张，但是有没有更惯用的方法呢？

我对我们想要双射的情况感兴趣，这意味着没有两个键可以映射到相同的值，以及不强加该条件的情况。

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")

但是有些东西不起作用，比如assocand 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

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

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

抱歉，我对 Java 平台不够熟悉，无法推荐一些具体的东西。当然会想到 Datomic，但对于这个特定的用例来说，它可能有点过分了。另一方面，它具有不变性，根据您对布赖恩的回答的评论，这对您来说似乎是可取的。