高效的不可变映射实现？

我想知道如果有一个地图的实现是：高效的不可变映射实现？

永恒，这样我就可以在函数式编程使用它，并毫不费力地确保交易和并发性。
快速。我已经检出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

高效的不可变映射实现？

回答

相关问题