How to search a unknown composite key for dictionary in O(1) in c#

85 views Asked by At

My key is composite key

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

I want get key with max index by known1 and known2, my code as follows

 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 :Dictionary Getting or setting the value of this property approaches an O(1) operation

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

Is there possible approach O(1) to get max index for unknown composite key like MSDN sample?

1

There are 1 answers

0
Alexei Levenkov On

No if you want to do it on your existing dictionary.

As an option - build additional index (dictionary) by your "known" part of the key and store sorted list (or heap) of items for each key. It'll get search to be O(1), but add/remove will go up to O(log N) to support sort order.