在clojure中的双向地图？

Question

在clojure中实现双向地图的最佳方法是什么？(通过双向映射,我的意思是一个关联映射,它可以提供A-> B和B-> A访问.所以实际上,值本身将是向相反方向前进的键.)

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

我对我们想要一个双射的情况感兴趣,暗示没有两个键可以映射到相同的值,以及没有强加该条件的情况.

Answer 1

您可以随时使用Java库,就像Apache公共中的一个集合一样.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不唯一，您应该避免这种实现。