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

Answer 3

Have you considered using a hash table with some kind of combination of the Fields as the key? I don't know enough about your data set to say if this is viable or not. Since the keys would need to be unique. But since you're not doing additions or removals using a hash table for look ups in memory is about as fast as you can get.

Answer 4

If i got you right, you can use Hashtable with Tuple, example below:

        // populate Hastable
        var hash = new Hashtable();            
        var tuple = Tuple.Create("string", 1, 1.0);
        hash.Add(tuple,tuple);

        // search for item you want
        var anotherTuple = Tuple.Create("string", 1, 1.0);
        // result will be tuple declared above
        var result = hash[anotherTuple];

more complex solution (if duplicate keys needed):

public class Thing
{
    public int Value1 { get; set; }

    public double Value2 { get; set; }

    public string Value3 { get; set; }

    // preferable to create own Equals and GetHashCode methods
    public Tuple<int, double>  GetKey()
    {
       // create key on fields you want 
       return Tuple.Create(Value1, Value2);
    }
}

usage

 var t1 = new Thing() {Value1 = 1, Value2 = 1.0, Value3 = "something"};
 var t2 = new Thing() {Value1 = 1, Value2 = 2.0, Value3 = "something"};
 var hash = new [] { t1, t2 }.ToLookup(item => item.GetKey());

 var criteria = new Thing() { Value1 = 1, Value2 = 2.0, value3 = "bla-bla-bla" };
 var r = hash[criteria.GetKey()]; // will give you t1

Answer 5

The Linq Where or Dictionary of Dictionaries is probably the prettiest you are going to get. But it may be more of a question of how you are organising your data.

E.G. This never going to be a pretty way of accessing people data:

people["FirstName"]["LastName"] 

It is usually better so try and come up with a simpler key.