How to implement a multi-index dictionary?

Question

Basically I want something like Dictionary<Tkey1, TKey2, TValue>, but not (as I've seen here in other question) with the keys in AND, but in OR. To better explain: I want to be able to find an element in the dictionary providing just one of the keys, not both.

I also think we should consider thread-safety and the ability to easily scale to a Dictionary<Tkey1, TKey2, TKeyN, TValue> solution...

Answer 1

I'm going to go out on a limb here and appear stupid, but you could just roll your own Dictionary based on two dictionaries. It wouldn't be too terribly difficult to write (even with locking mechanisms to ensure thread safety). I mean, there's plenty of examples out there where you can use an index or a key to access a collection. (Such as Session)

Conversely, if your multiple indexes are of the same type, you could just add the same item multiple times.

Dictionary will support something with a GUID index, as well as a simple name index "Joe" - you have to remember to add the item twice.

Answer 2

Did you consider holding two dictionaries, one for each key? Adding an item would add it to both.

Removal means removing from both dictionaries too, and requires both keys. To remove with just one key, the item would have to store both keys. If it doesn't already hold both keys, you could wrap it in a container object that holds both keys and the item.

Answer 3

You could just use a regular dictionary for this and insert the value twice, once for each key. To delete you remove both keys.

Upsides:

• Can search for both keys with one lookup.
• No new code needed.
• Scales to any number of keys.

Downsides:

• Lose type safety if keys are of different types.
• Can't iterate over (key1, key2, value) tuples.
• Values appear twice so size() is doubled.

Answer 4

So you want a multi-index dictionary, supports lookups based on any key, and supports extensions to multiple keys?

Maybe you're thinking of the wrong data structure, try a KD-Tree instead. An immutable KD-tree would satisfy the thread-safety requirement.

KD-trees have some major advantages over the naive Dictionary{Key1, Dictionary{Key2, Value}} approach, namely that you can search for all fields based on Key2 without knowing Key1. Additionally, KD-trees allow you to search for keys which are near some other key. For example, dating sites classify people into dozens of groups (smoker/non-smoker, gender, religion, lifestyle, age, height), then return nearest neighbors based on your query.

Here's a C# and Java implementation:

http://www.cs.wlu.edu/~levy/software/kd/

Answer 5

I would implement a data structure with these two dictionaries

Dictionary<TKey1, KeyValuePair<TKey2, TValue>> dict1;
Dictionary<TKey2, KeyValuePair<TKey1, TValue>> dict2;

That way if you are given 1 key you have both the value and the other key as well for easy deletes and updates.

Answer 6

Two dictionaries, but don't duplicate the items in each.

You'll have a value dictionary, and a key dictionary.

When you call your add method, you'll generate a GUID and add it and the key to the keys dictionary.

Then, use the GUID as a key to the values dictionary.

If you want to add two keys, you'll add another item to the keys dictionary with the same GUID.

Of course this means every lookup requires two checks for the data, but never more, even if you have 50 keys for the same value.

Lookup the guid based on the key from the keys table, then lookup the data based on that guid in the values table.

Answer 7

Maybe an option:

Do as John Kugelman suggests, just add an item twice in the same dictionary. Then you keep a second dictionary that maps values to sets of keys.

When you add a key,value par, you just add it as normal to the first dictionary and then retrieve the key set belonging to that value from the second dictionary and add the key.

Dictionary<TKey, TValue> dict1;
Dictionary<TValue, ICollection<TKey>> dict2;

Removing a value is done by retrieving the key set from dict2 and removing them one by one from dict1.

The number of keys is dict1.Count and the number of values is dict2.Count

Answer 8

I have written such a dictionary and posted it on my blog. It will give you a nice API like this:

DoubleKeyDictionary<int, string, string> books = new DoubleKeyDictionary<string, string, string>();
bookListEx.Add(1, “21/12/2009″, “Lord of the Rings - Fellowship of the Ring”);

You can also do "Equals" on two dictionaries and for-each over it.

Please note that there are at least one bug in the code (as discovered in the comments) and no unit tests etc. When (yeah!) I get some time I'll update the code with unit tests...

Answer 9

What about a Multi Index Container inspired by boost??

Take a look at CodeProject.

Answer 10

Create simple class to store Tkey1, TKey2, TValue, make List of them and use LINQ to query such structure would be an option.