Denis Denis - 3 months ago 34
C# Question

How would you implement a fast lookup by multiple keys?

I am looking to create a fast lookup (dictionary?) with optional keys so for example, let's say I have 3 keys: "first_name", "last_name", "zipcode"

so I would like to be able to do the following (pseudocode):

GetValue(first_name) -- would return a list of everyone with that first name
GetValue(first_name, last_name) -- would return a list of everyone with that first name & last name
GetValue(zipcode, first_name) -- would return a list of everyone with that first_name in the specified zipcode


I should be able to query out all permutations of those keys. What data structure would you use for this? How would you implement this?

Answer

You could still use regular dictionaries where the key could be a custom type like this:

public class CompositeKey
{
     public CompositeKey(string firstName, string lastName, string zipCode)
     {
           FirstName = firstName;
           LastName = lastName;
           ZipCode = zipCode;
     }

     public string FirstName { get; }
     public string LastName { get; }
     public string ZipCode { get; }
}

Now I would override Equals and GetHashCode on CompositeKey to provide what makes a composite key unique so Dictionary<TKey, TValue> would be able to store unique composite keys.

Finally, I would be able to query the dictionary this way:

var value = dict[new CompositeKey { FirstName = "Matías", LastName = "Fidemraizer" }];

OP asked this question in some comment:

I thought about this approach but how would you query the dictionary for "FirstName = "Matias" only?

Since you're overriding both Equals and GetHashCode, you can add all combinations as keys in the whole dictionary and they can all co-exist there:

Person person = new Person { /* Set members here */ }

// Note that I'll add many keys that have the same value
dict.Add(new CompositeKey { Name = "Matías" }, person );
dict.Add(new CompositeKey { LastName = "Fidemraizer" }, person);
dict.Add(new CompositeKey { Name = "Matías", LastName = "Fidemraizer" }, person);

Each key will result in a different hash code so they can all co-exist in the same dictionary and they will provide a powerful tool to query by many criterias and criteria combinations.

Another approach

Other approach could be using multiple dictionaries where their keys are concatenations of the whole values using some convention and the values are instances of the whole class:

Dictionary<string, Person> names = new Dictionary<string, Person>();
names.Add("matias", new Person { /* Set members here */ });

Dictionary<string, Person> names = new Dictionary<string, Person>();
names.Add("matias:fidemraizer", new Person { /* Set members here */ });

// And so on, for every criteria you want to search...

Later you would implement a proxy to determine what dictionary to query based on the given criteria.

What about Redis

Actually you should take a look at Redis, which is a key-value store with complex data structures as values like hashes, sets, sorted sets and many more. That is, you could centralize your cache and distribute it using Redis, and you cache could be consumed by many applications.

It's extremely simple to use and install (it's an executable of less than 10MB...).

Comments