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 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 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/)