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...

Solution 1

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.

Solution 2

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://home.wlu.edu/~levys/software/kd/ (broken link, archived at https://web.archive.org/web/20190609084214/http://home.wlu.edu/~levys/software/kd/)

Solution 3

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.

Solution 4

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.

Solution 5

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 pair, 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

View more solutions