有没有办法以 O(1)~ 复杂性检索存储在 C#s 的 OrderedDictionary DS 中的项目的索引

Question

换句话说 - 如何在不迭代“GetEnumerator()”的值 (O(n)) 的情况下获取它？

例如，假设我创建了以下有序字典（名为 aOrdDict），其中包含以下对：

   INDEX      KEY                       VALUE
   0          testKey1                  testValue1
   1          testKey2                  testValue2
   2          keyToDelete               valueToDelete
   3          testKey3                  testValue3

如何在 aOrdDict.GetEnumerator() 中显示“testKey3”的索引为 3，而不执行以下某些过程：

int i = 0;
var ListedPairs = aOrdDict.GetEnumerator();
string wantedKey = "testKey3";

for(; i < aOrdDict.Keys.Count; i++)
{
    if (ListedPairs.key == wantedKey)
        break;
    listedPairs.MoveNext();
}

编辑 - 临时解决方案和一些背景

对导致我的问题的风景进行一些详细说明，并附上我实施的临时解决方案（与 Martin Liversage 在评论中建议的类似）：

我主要从事一些双向客户端<->服务器调解器的工作。服务器-->客户端消息进入调解器并处理后，将它转发给客户端后，它的主体和 DateTime.Now() 值（低至 ms）都是在那一刻应该相互关联地存储在调解器中，打包，然后发送给客户端。

稍后，客户端向服务器发送请求，每个请求都带有特定的时间戳。

它期望接收一些存储值的跨度，这些存储值是相邻的且按时间顺序排列在前到输入时间戳。在那个阶段，有序的字典应该派上用场通过允许我按键访问存储在 'timeStamp' 的值（因此 - 需要一个字典），然后迭代向后，逐个值，以与插入它们的顺序相反的顺序。（因此 - 需要一个列表）

最终 - 我使用了 :

ConcurrentDictionary<string, int> aIndicesDict

一对{timeStamp, index}夫妇，还有一对

List<Tuple<string, someObject>> aSomeObjectsList

对于一对（时间戳，消息正文），

每次收到新消息时都将传入值存储在两个集合中从服务器发送到客户端。

然后，根据客户端对服务器的传入请求，我们获得与输入时间戳相关的索引（来自 aIndicesDict - O(1)），允许我们从列表的相关索引开始向后迭代元组（在 aSomeObjectsList 内 - O(1) 以直接进入相关列表条目）。

正如我在评论中所写 - 我仍然想找到更有效的解决方案（内存方面）。

Answer 1

OrderedDictionary 没有提供您想要的功能。在内部，没有从键到索引的映射。相反，您可以从键或索引映射到实际值。

您可以构建自己的有序字典，其中您在内部保留一个列表和一个数组：列表从索引映射到键，字典从键映射到值。这将提供一种从 O(1) 中的键获取索引的方法，但由于额外的间接寻址，按索引读取值（并按顺序迭代）的成本更高。如果您构建自己的 collection，您还可以使用古老的 OrderedDictionary 所不具备的泛型。

但是，为什么需要从键中获取索引呢？如果您使用键来查找值并且索引确实是一个排序那么您也许可以在值中包含“索引”（实际上是顺序）？

有没有办法以 O(1)~ 复杂性检索存储在 C#s 的 OrderedDictionary DS 中的项目的索引

Is there a way to retrieve the index of an item stored within C#s' OrderedDictionary DS in O(1)~ complexity

c#

time-complexity

ordereddictionary

编辑 - 临时解决方案和一些背景