高效的不可變映射實現？

我想知道如果有一個地圖的實現是：高效的不可變映射實現？

永恆，這樣我就可以在函數式編程使用它，並毫不費力地確保交易和併發性。
快速。我已經檢出Binary 搜索樹（RB，AVL）和嘗試，但是它們沒有一個像哈希表一樣快。是否有地圖實現支持更新和檢索的恆定時間？（或者至少非常快對數時間）

總之，是有功能的數據結構，其能夠在性能哈希映射比較？

來源

2009-08-20 Phil

Clojure擁有不可改變的地圖。（link）。不確定它使用的底層數據結構。 Clojure源代碼會給你更多的信息！

來源

2009-08-20 10:15:18

非常感謝您的有益迴應。我要儘快查看Clojure。 – Phil 2009-08-20 15:10:35

Clojure的不可變映射使用32位散列陣列映射嘗試（http://en.wikipedia.org/wiki/Hash_array_mapped_trie）。它們是一個很好的數據結構 - 幾乎與可變HashMap一樣快，但具有持久性和不可變性的所有優點。 – mikera 2012-05-29 04:16:12

斯卡拉也有immutable maps，但它們比散列表慢。我懷疑你的問題的答案是否定的，你不會找到一個具有O（1）預期時間插入/查詢操作的不可變映射實現。

來源

2009-08-20 13:44:55

是的，我目前正在試用Scala，並且一般對性能不滿意。 – Phil 2009-08-20 15:13:34

無論如何，只是爲了與人分享，這些是兩個有趣的關於使用Tries在Scala中實現持久性向量的博客條目。他們還提到了Clojure的實現，以及最近Scala版本中的新IntMap。

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

對於這些數據結構，我已經與主要作爲整數測試，但尚未字符串。因爲我真正的應用程序會使用字符串作爲鍵，所以我不確定實現是否比Hash Map更高效。如果我使用String的HashCode作爲關鍵字，那麼使用Persistent Vector來支持地圖呢？我將使用32路特里實現持久性向量。我猜碰撞是非常罕見的，記憶只會相應地消耗。但我不確定需要複製更新的實際金額。

我即將發佈我的結果。

來源

2009-08-20 15:24:45 Phil

我還沒有讀過它，但我認爲有些人認爲Purely Functional Data Structures作爲這種事情的聖經。

來源

2009-08-21 07:57:51 Brian

沒有關於地圖/哈希表的任何內容。 – 2009-08-21 13:30:10

高效的不可變映射實現？

回答

相關問題