我正在寻找具有例如功能的数据结构。在OrderedDictionary.NET 中，即维护元素顺序的关联集合（即，将键与值相关联的集合）（就像普通集合一样List）。
它必须通过索引和键快速查找。它还应该有一个快速的“追加”操作（在末尾插入一个新项目），以及快速删除具有任何索引的项目（基于索引或键）。
OrderedDictionary如果我没记错的话，.NET 中的内容同时使用哈希表和数组来存储其项目。因此，基于键检索索引（反之亦然）是O(n)，当然从数组中间删除一个项目是O(n)开始，再加上从如果通过键删除，则为键。
我的问题是是否存在满足我条件的更有效的数据结构，或者这确实是我最好的选择？
我认为您可以使用两棵红黑树来做到这一点：一个键查找树，用于存储由比较函数排序的键，以及一个索引查找树，键以任意顺序排列，如列表中。每个索引查找节点必须有一个“大小”字段——如果每个节点中都包含一个“大小”字段，红黑树可以按索引进行查找。例如，参见C5 Generic Collection Library中的 RedBlackTreeSet 实现。
键查找树中的每个条目都需要一个指向索引查找树中相应条目的指针。除了左节点和右节点指针，索引查找树还需要一个父指针字段以允许自底向上- 顶部导航以及从上到下。
总之，每个键都需要六个指针：两个节点中通常的左指针和右指针，加上从键查找节点到索引查找节点的指针，加上每个索引查找中的父指针-节点。您还需要在每个节点中都有一个指针来指向存储的值。
操作：
追加 - 追加操作会将键插入到两棵树中 - 一次在键查找树中，位于由比较函数确定的位置，然后再次位于索引查找树的最右侧位置。插入红黑树是一个对数时间操作。
按键查找 - 这是在键查找树上完成的，使用比较功能找到正确的位置 - O(log(n))
按索引查找 - 这可以在索引查找字段上完成，如上所述 - O(log(n))
从键获取索引 - 首先在键查找树 O(log(n)) 中查找键。按照指向索引查找树的指针。跟随父指针直到根节点，（平衡树的 O(log(n))）。使用向上的“大小”字段来确定键的索引。- O(log(n)) 总体。
按索引删除 - 在索引查找树中查找项目。从索引查找树中删除。在键查找树中查找找到的键。从键查找树中删除。所有操作都是 O(log(n)) ，所以 delete 总体上是 O(log(n)) 。
按键删除 - 使用“从键获取索引”来获取键的索引。从索引查找树中按索引删除。从键查找树中按键删除。O(log(n)) 总体。
该结构还支持在任意位置插入 O(log(n))，而不仅仅是在末尾。
存储开销显然是相当大的，但仍然是 O(n)。时间复杂度满足所有要求。
不幸的是，我不知道这种结构的任何实现。
更新：在我看来，您可以将树与哈希表结合起来进行 O(1) 按键查找。正如我上面建议的那样，不要使用两棵树，而是使用哈希表进行按键查找，使用平衡的顺序统计树进行位置查找，如上所述，但哈希表的槽包含指向的指针用于执行 get-list-position-by-key 查找的平衡树的节点。按键查找现在是 O(1)，其他所有内容平均保持 O(ln(n))。当然，你现在偶尔会得到 O(n) 的重新哈希惩罚，就像任何哈希表一样。
OrderedDictionary 实际上满足您的要求。
您对 OrderedDictionary 的分析不正确。它实际上是 O(1) 用于基于键的查找和 O(1) 用于根据this的索引。
即使是简单的分析也可以通过键或索引为您提供 O(1) 查找。数组提供 O(1) 访问，而哈希表提供有效的 O(1) 访问。
插入/删除稍微复杂一些，但考虑到摊销分析仍然是 O(1)
文章声称插入和删除是 O(n)。这至少不适用于插入，因为摊销分析允许您简单地将插入给定元素的“成本”从 1 提高到 2。当插入需要调整数组大小的元素时，成本的后半部分用于支付复制的成本。最后的插入将花费更长的时间，但它仍然是 O(1) 摊销的，并且只有在您导致不太可能调整数组大小时才会出现差异。
也许您会在The C5 Generic Collection Library for C#中找到一些有趣的东西（从第 233 页开始）
您可以像链接一样使用平衡二叉搜索树，只是为了在 TreeNode 的定义中添加键，但问题是通过键和索引查找元素不是 O(1)，而是 O(log(n))（实际上索引不是TreeNode的一部分，相对可以找到）但所有操作都是O（log（n））并且是基于比较方法的最快已知方式。