Dictionary supporting duplicate, multidimensional keys?

Question

I have a List<Thing> things, where a number of Things need to be frequently retrieved by looking up a combination of two variables T1 f1 and T2 f2, which are value types. They way I do that now is simply things.Where(t => t.Field1 == f1 && t.Field2 == f2). However, I do extremely many of those lookups frequently, and need a more effective method.

Fortunately, things does not need to have elements removed or added, so I thought of parsing the list on construction and add to a Dictionary<T1, Lookup<T2, Thing>>. However, this feels messy, especially with the added parsing. And it gets really hairy if I need to lookup even more fields. Three fields would look like Dictionary<T1, Dictionary<T2, Lookup<T3, Thing>>>.

My next thought was to make a Lookup<Tuple<T1,T2,T3,...>,Thing>. But in this case, I am not sure whether the keys will actually work because Tuple is a reference type.

Even if I make a Lookup<ValueType<T1,T2,T3,...>,Thing> things, the lookup statement will be something like things[new ValueType<T1,T2,T3,...>(f1, f2, f3, ...)] which is pretty ugly (and I am still not sure whether I could trust those keys).

Is there a more elegant solution to this which keeps the performance benefits of a hashtable and where I could simply type something like IEnumerable<Thing> found = things[f1, f2, f3, ...];?

Answer 1

Lookup<Tuple<T1,T2,T3,...>,Thing> will work, since Tuple overrides Equals and GetHashCode.

To make the lookup syntax less ugly, you can use Tuple.Create which supports type inference. Your code becomes things[Tuple.Create(f1, f2, f3, ...)]. If that's still too ugly, it's trivial to add a helper method that takes the individual values as parameters.

I'd also consider creating my own immutable class(or value type) for the key, so you get clean field names instead of ItemX. You just need to override Equals and GetHashCode consistently.

Answer 2

You can create multiple lookups, and then intersect them to do your searches. Here is a somewhat oversimplified example, but it should illustrate the idea:

class Test {
    public string A { get; set; }
    public string B { get; set; }
    public string C { get; set; }
}

var list = new List<Test> {
    new Test {A = "quick", B = "brown", C = "fox"}
,   new Test {A = "jumps", B = "over", C = "the"}
,   new Test {A = "lazy", B = "dog", C = "quick"}
,   new Test {A = "brown", B = "fox", C = "jumps"}
,   new Test {A = "over", B = "the", C = "lazy"}
,   new Test {A = "dog", B = "quick", C = "brown"}
,   new Test {A = "fox", B = "jumps", C = "over"}
,   new Test {A = "the", B = "lazy", C = "dog"}
,   new Test {A = "fox", B = "brown", C = "quick"}
,   new Test {A = "the", B = "over", C = "jumps"}
,   new Test {A = "quick", B = "dog", C = "lazy"}
,   new Test {A = "jums", B = "fox", C = "brown"}
,   new Test {A = "lazy", B = "the", C = "over"}
,   new Test {A = "brown", B = "quick", C = "dog"}
,   new Test {A = "over", B = "jumps", C = "fox"}
,   new Test {A = "dog", B = "lazy", C = "the"}
};
var byA = list.ToLookup(v => v.A);
var byB = list.ToLookup(v => v.B);
var byC = list.ToLookup(v => v.C);
var all = byA["quick"].Intersect(byB["dog"]);
foreach (var test in all) {
    Console.WriteLine("{0} {1} {2}", test.A, test.B, test.C);
}
all = byA["fox"].Intersect(byC["over"]);
foreach (var test in all) {
    Console.WriteLine("{0} {1} {2}", test.A, test.B, test.C);
}

This prints

quick dog lazy
fox jumps over