A dictionary that supports duplicate, multidimensional keys?

Question

I have List<Thing> things where the Thing number needs to be often extracted by looking at the combination of the two variables T1 f1 and T2 f2 , which are value types. They do so that now things.Where(t => t.Field1 == f1 && t.Field2 == f2) simple things.Where(t => t.Field1 == f1 && t.Field2 == f2) . However, I often do a lot of such searches and need a more efficient method.

Fortunately, things do not need to be deleted or added, so I thought about parsing the list by construction and adding it to Dictionary<T1, Lookup<T2, Thing>> . However, this seems messy, especially with added parsing. And it gets really hairy if I need to look for even more fields. The three fields will look like Dictionary<T1, Dictionary<T2, Lookup<T3, Thing>>> .

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

Even if I create Lookup<ValueType<T1,T2,T3,...>,Thing> things , the lookup operator will be similar to things[new ValueType<T1,T2,T3,...>(f1, f2, f3, ...)] which is pretty ugly (and I'm still not sure if I can trust these keys).

Is there a more elegant solution for this that retains the hash table performance advantages and where I can just type something like IEnumerable<Thing> found = things[f1, f2, f3, ...]; ?

Answer 1

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

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

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

Answer 2

You can create multiple searches and then cross them to perform a search. Here is a slightly simplified 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 => vA); var byB = list.ToLookup(v => vB); var byC = list.ToLookup(v => vC); 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); } 

Will print

 quick dog lazy fox jumps over 

Answer 3

Have you considered using a hash table with some combination of fields as a key? I don’t know enough about your dataset to say if it is viable or not. Because the keys must be unique. But since you are not adding or removing using a hash table to search in memory, it is about as fast as you can get.

Answer 4

If I understood correctly, you can use Hashtable with Tuple , an 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 are 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); } } 

Using

  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

Link Where or Dictionary Dictionaries are probably the most beautiful that you are going to get. But it may be more of a question about how you organize your data.

eg. This will never be a good way to access people's data:

 people["FirstName"]["LastName"] 

As a rule, it is better to try and come up with a simpler key.