我想知道是否有一个地图的实现是：
- Immutable，这样我就可以在函数式编程中使用它，并且毫不费力地确保事务和并发性。
- 快。我检查了二叉搜索树（RB，AVL）和尝试，但它们似乎都没有哈希表那么快。是否有支持恒定时间进行更新和检索的地图实现？（或至少非常快的对数时间）
简而言之，有没有一种功能数据结构可以在性能上与 Hash Maps 相提并论？
问问题
3749 次
4 回答
4
Clojure 有不可变的映射。（链接）。不确定它使用的是什么底层数据结构。Clojure 源代码将为您提供更多信息！
于 2009-08-20T10:15:18.023 回答
3
Scala 也有不可变的映射，但它们比哈希表慢。我怀疑您的问题的答案是否定的，您将找不到具有 O(1) 预期时间插入/查询操作的不可变映射实现。
于 2009-08-20T13:44:55.377 回答
1
我还没有读过它，但我认为有些人认为纯函数式数据结构是这类事情的圣经。
于 2009-08-21T07:57:51.840 回答
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
对于这些数据结构，我已经将键作为整数进行了测试，但还没有作为字符串进行测试。因为我的实际应用程序将使用字符串作为键，所以我不确定实现是否会比哈希映射更有效。如果我使用 String 的 HashCode 作为键，然后使用 Persistent Vector 来支持映射呢？我将使用 32-way trie 来实现 Persistent Vector。我想碰撞会非常罕见，并且只会相应地花费内存。但我不确定更新时需要复制的实际数量。
我很快就会公布我的结果。
于 2009-08-20T15:24:45.790 回答