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想到，但它可能是這個特殊用例的矯枉過正。另一方面，它具有不變性，根據你對布賴恩的回答的評論，你對此似乎是可取的。