寻找一个数据结构，它在逻辑上表示由唯一ID键控的元素序列（为了简单起见，我们将它们视为字符串，或者至少是可哈希的对象）。每个元素只能出现一次，没有间隙，第一个位置为0。
应支持以下操作（使用单字母字符串演示）：
-
insert(id, position)- 将id键入的元素添加到偏移量position处的序列中。当然，序列中每个元素的位置现在都会递增 1。示例：[S E L F].insert(H, 1) -> [S H E L F] -
remove(position)- 删除偏移position处的元素。将序列中每个元素的位置递减 1。示例：[S H E L F].remove(2) -> [S H L F] -
lookup(id)- 查找由id键控的元素的位置。[S H L F].lookup(H) -> 1
朴素的实现要么是链表，要么是数组。两者都会给出 O（n） lookup、remove 和 insert。
在实践中，lookup可能是使用最多的，insert和remove发生的频率足够高，以至于最好不要线性（哈希图+数组/列表的简单组合会让你得到）。
在一个完美的世界中，它将是O（1）lookup，O（log n）insert/remove，但我实际上怀疑从纯粹的信息理论角度来看这是行不通的（尽管我没有尝试过），所以O（log n）lookup仍然很好。
trie 和哈希映射的组合允许 O（log n） 查找/插入/删除。
trie 的每个节点都包含有效元素的 id 和计数器，由此节点和最多两个子指针根。位字符串，由左 （0） 或右 （1） 匝数确定，同时从其根遍历 trie 到给定节点，是值的一部分，存储在相应 id 的哈希映射中。
删除操作将 trie 节点标记为无效，并将路径上有效元素的所有计数器从已删除节点更新到根。此外，它还删除相应的哈希映射条目。
插入操作应使用每个 trie 节点中有效元素的位置参数和计数器来搜索新节点的前置节点和后继节点。如果从前置节点到后继节点的按顺序遍历包含任何已删除的节点，请选择一个排名最低的节点并重复使用它。否则，请选择前置节点或后继节点，并向其添加新的子节点（前置节点为右子节点，后继节点为左子节点）。然后更新从此节点到根的路径上有效元素的所有计数器，并添加相应的哈希映射条目。
查找操作从哈希映射中获取一个位字符串，并使用它来从trie根转到相应的节点，同时对此路径左侧的有效元素的所有计数器求和。
所有这些都允许每个操作的 O（log n） 预期时间，如果插入/删除的顺序足够随机。否则，每个操作的最坏情况复杂度为 O（n）。要使其恢复到 O（log n） 摊销复杂性，请观察树的稀疏性和平衡因子，如果删除的节点太多，请重新创建一个新的完美平衡和密集的树;如果树太不平衡，请重建最不平衡的子树。
代替哈希映射，可以使用一些二叉搜索树或任何字典数据结构。哈希映射可以存储指向trie中相应节点的指针，而不是用于标识trie中的路径的位字符串。
在此数据结构中使用trie的其他替代方法是可索引的skiplist。
每个操作的 O（log N） 时间是可以接受的，但并不完美。正如 Kevin 所解释的那样，可以使用具有 O（1） 查找复杂度的算法来换取其他操作的更大复杂度：O（sqrt（N））。但这可以改进。
如果为每个查找操作选择一定数量的内存访问 （M），则其他操作可能会在 O（M*N1/M） 时间内完成。这种算法的思想在相关问题的回答中提出。此处描述的 Trie 结构允许轻松地将位置转换为数组索引并返回。此数组的每个非空元素都包含 id，哈希映射的每个元素将此 id 映射回数组索引。
为了能够将元素插入到此数据结构中，每个连续数组元素块都应交错放置一些空白空间。当其中一个块耗尽所有可用的空白空间时，我们应该重建最小的块组，与trie的某个元素相关，具有超过50%的空白空间。当空置空间总数小于50%或大于75%时，我们应该重建整个结构。
这种再平衡方案仅针对随机和均匀分布的插入/移除提供 O（M N1/M） 摊销复杂性。对于 M> 2，最坏情况的复杂性（例如，如果我们总是在最左侧的位置插入）要大得多。为了保证 O（M N1/M） 最坏情况，我们需要保留更多内存并更改再平衡方案，使其保持不变，如下所示：为整个结构保留至少 50% 的空白空间，为与顶级 trie 节点相关的所有数据保留至少 75% 的空白空间，对于下一级 trie 节点 - 87.5%， 等。
当 M=2 时，我们有 O（1） 时间用于查找，O（sqrt（N）） 时间用于其他操作。
使用 M=log（N），我们每个操作都有 O（log（N）） 时间。
但实际上，较小的 M 值（如 2 .. 5）更可取。这可以被视为 O（1） 查找时间，并允许此结构（在执行典型的插入/删除操作时）以缓存友好的方式处理多达 5 个相对较小的连续内存块，并具有良好的矢量化可能性。此外，如果我们需要良好的最坏情况复杂性，这将限制内存要求。
你可以在O（sqrt（n））时间内完成所有工作，但我要警告你，这需要一些工作。
首先看看我在ThriftyList上写的一篇博客文章。 ThriftyList 是我对最佳时间和空间中可调整大小的数组中描述的数据结构的实现，以及一些用于维护 O（sqrt（n）） 循环子列表的自定义，每个子列表的大小为 O（sqrt（n））。 使用循环子列表，可以通过在包含子列表中进行标准插入/删除然后移位，然后跨循环子列表本身进行一系列推送/弹出操作来实现 O（sqrt（n）） 时间插入/删除。
现在，若要获取查询值所在的索引，需要维护从值到子列表/绝对索引的映射。 也就是说，给定的值映射到包含该值的子列表，加上该值下降的绝对索引（该项目将落下的索引是非循环列表）。 根据这些数据，您可以通过从圆形子列表的头部取偏移量并与包含子列表后面的元素数求和来计算值的相对索引。 要维护此映射，每次插入/删除都需要 O（sqrt（n）） 操作。
听起来很像 Clojure 的持久向量 - 它们为查找和更新提供了 O（log32 n） 成本。对于 n O（log32 n） 的小值，与常数一样好。
基本上它们是数组映射的尝试。
不太确定删除和插入的时间复杂度 - 但我很确定您也可以使用 O（log n） 删除和插入获得此数据结构的变体。
请参阅此演示文稿/视频：http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
源代码（Java）：https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentVector.java