如何在c#中查找O(1)中的字典的未知组合键

Question

我的键是组合键

public struct Mykey{
    public int index;
    public string known1;
    public string known2;
}     

我想通过known1和known2获取带有最大索引的键，我的代码如下

 Dictionary<key, value> dict = new Dictionary<key, value>();
 // below O(n) operation
 dict.Where( k => (k.Key.known1 =="str1") && (k.Key.known2=="str2")).Max(k => k.Key.index);

MSDN :字典获取或设置此属性的值接近于O(1)运算

dict[key] = item ;// MSDN sample O(1) key known

有没有可能的方法O(1)来获得未知组合键的最大索引，如MSDN示例？

Answer 1

如果您想在现有的字典上执行此操作，则不需要。

作为一种选择-根据键的“已知”部分构建额外的索引(字典)，并为每个键存储排序的项目列表(或堆)。它会使搜索结果为O(1)，但添加/删除将上升到O(log )以支持排序顺序。