如何将有序的 Map 构造为持久化数据结构？

Question

我有一个基于散列数组映射特里树的持久数据结构 hamt，它是几个更具体的持久数据结构的基础，例如不可变数组。它提供了一个相当简单的 API:

const hamtDel = (hamt, props, k) => {/* implementation */}
const hamtGet = (hamt, k) => {/* implementation */}
const hamtSet = (hamt, props, k, v) => {/* implementation */}
const hamtEmpty = () => {/* implementation */} // creates an empty hamt

hamt、k、v 是不言自明的。 props 只是一种向新生成的 hamt 对象添加任意属性的方法。例如，不可变数组具有额外的 length 和 offset 属性以允许高效的 cons 和 snoc 操作。

hamt本身基本上就是一个无序的Map。由于有序地图在 Javascript 中很常见，因此我尝试实现一个基于 hamt 的地图。然而，事实证明这是相当困难的。为了跟踪插入顺序，我需要一个 hamt A 用于实际的 key/value 对，以及一个保存从插入数到相应键的映射的 hamt A =25=].

鉴于这两个结构，我可以像往常一样访问 A 的元素并通过检索 B 持有的插入顺序遍历 A。但是，当我想删除 A 中的元素时，我还需要删除 B 中的元素。 B 中的键是插入次数。这意味着在最坏的情况下，我将不得不遍历整个 B 结构来找到相应的键。

第三个 hamt 与 B 的 key/value 对倒置可以缓解这个问题，但最终得到三个 hamt 只是为了获得一个有序的地图似乎糟糕的设计选择。

我很确定这个问题是众所周知的，并且有可靠的解决方案来解决它。由于缺乏正确的术语，我还没有发现任何有用的东西。非常欢迎就此事提供帮助。

Answer 1

Scala 和 Kotlin 中有一些实现值得一看。

首先是 scala 的 VectorMap (https://github.com/scala/scala/blob/v2.13.3/src/library/scala/collection/immutable/VectorMap.scala)

它使用压缩哈希 Array-Mapped Trie 的组合，也称为 CHAMP（类似于 HAMT 的不可变哈希映射），以及作为基数平衡树的 Vector 按顺序存储密钥.

接下来是 scala 的 TreeSeqMap (https://github.com/scala/scala/blob/v2.13.3/src/library/scala/collection/immutable/TreeSeqMap.scala)

这使用与 VectorMap 相同的 CHAMP 散列图，但与专门的 Trie-Map 一起使用，其中键类似于整数索引，值是有序映射的实际键。

接下来是我几个月前写的这个提议 LinkedHashMap，它与可变 double-linked-list 支持的 LinkedHashMap 非常相似，但将链表拆分成段以允许为了更好的持续更新：https://github.com/scala/scala/pull/8644/files

最后是 Kotlin 的 OrderedMap：https://github.com/Kotlin/kotlinx.collections.immutable/blob/master/core/commonMain/src/implementations/persistentOrderedMap/PersistentOrderedMap.kt 除了 Link 段的长度均为 1（即每个 key-value 是它自己的段，或者换句话说，没有段，只有单个元素，它们通过键而不是指针向前和向后指向。

如何将有序的 Map 构造为持久化数据结构？

How to construct an ordered Map as a persistent data structure?

javascript

functional-programming

tree

trie