高效的不可变映射实现?

clojure有不可变的映射。( link )不确定它使用的是什么基础数据结构。clojure源代码将为您提供更多信息!

斯卡拉也有 immutable maps ,但它们比哈希表慢。我怀疑您的问题的答案是否定的,您不会找到具有o(1)预期时间插入/查询操作的不可变映射实现。

总之,为了与大家分享,下面是两篇有趣的博客文章,介绍了如何使用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

对于这些数据结构,我已经使用键作为整数进行了测试,但还没有使用字符串。因为我真正的应用程序将使用字符串作为键,所以我不确定实现是否比哈希映射更有效。如果我使用字符串的hashcode作为键,然后使用持久向量来支持映射呢?我将使用32路trie来实现持久向量。我想碰撞是非常罕见的,记忆只能相应地被消耗掉。但我不确定在更新时需要拷贝的实际数量。

我很快就会公布结果。

我没读过,但我想有些人认为 Purely Functional Data Structures 作为这类事情的圣经。