Multi-key DataStructure

Question

I'm looking for a data structure that I can search with multiple keys. Easier to explain with an example:

var myDataStructure = new MultiKeyDataStructure<int, string, MyType>();
myDataStructure.Add(1, "some string 1", new MyType());
myDataStructure.Add(2, "some string 2", new MyType());

var myType = new MyType();
myDataStructure.Add(3, "some string 3", myType);

Tuple<string, MyType> t1 = myDataStructure[1];
Tuple<int, MyType> t2 = myDataStructure["some string 1"];
Tuple<int, string> t3 = myDataStructure[myType];

Is something like this possible, and if so, is there anything that already exists to do it? How would you implement something that treats everything like a key and returns all associated keys by searching for any of them?

Ideally you would also be allowed to use any number and/or type of parameters:

var myDataStructure = new MultiKeyDataStructure<int, string, Foo, Bar>();

Answer 1

So here's one that will work for exactly three keys. You could follow the listed pattern to make one for 4, 5, 6, etc. keys. It would be a lot of code, but not a particularly difficult task (just tedious).

Note that since there's a dictionary for each part of the key it will use up quite a lot of memory; that's the price you pay for the flexibility of very fact access from any key.

public class MultiKeyDictionary<T1, T2, T3>
{
    private Dictionary<T1, Tuple<T1, T2, T3>> firstLookup = new Dictionary<T1, Tuple<T1, T2, T3>>();
    private Dictionary<T2, Tuple<T1, T2, T3>> secondLookup = new Dictionary<T2, Tuple<T1, T2, T3>>();
    private Dictionary<T3, Tuple<T1, T2, T3>> thirdLookup = new Dictionary<T3, Tuple<T1, T2, T3>>();

    public void Add(Tuple<T1, T2, T3> values)
    {
        if (!firstLookup.ContainsKey(values.Item1) &&
            !secondLookup.ContainsKey(values.Item2) &&
            !thirdLookup.ContainsKey(values.Item3))
        {
            firstLookup.Add(values.Item1, values);
            secondLookup.Add(values.Item2, values);
            thirdLookup.Add(values.Item3, values);
        }
        else
        {
            //throw an exeption or something.
        }
    }

    public Tuple<T1, T2, T3> GetFirst(T1 key)
    {
        return firstLookup[key];
    }

    public Tuple<T1, T2, T3> GetSecond(T2 key)
    {
        return secondLookup[key];
    }

    public Tuple<T1, T2, T3> GetThird(T3 key)
    {
        return thirdLookup[key];
    }

    public void RemoveFirst(T1 key)
    {
        var values = GetFirst(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }

    public void RemoveSecond(T2 key)
    {
        var values = GetSecond(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }

    public void RemoveThird(T3 key)
    {
        var values = GetThird(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }
}

Below is an entirely different approach. Instead of populating a lookup for each key it just stores all of the values in a single collection and performs a linear search to find an item for a given key. It will have O(n) Search/Remove time, but O(1) Add. The previous implementation has O(1) add, remove, and search, but takes up a lot more memory to do it.

public class MultiKeyDictionary2<T1, T2, T3>
{
    private HashSet<Tuple<T1, T2, T3>> lookup = new HashSet<Tuple<T1, T2, T3>>();
    private HashSet<T1> firstKeys = new HashSet<T1>();
    private HashSet<T2> secondKeys = new HashSet<T2>();
    private HashSet<T3> thirdKeys = new HashSet<T3>();

    public void Add(Tuple<T1, T2, T3> values)
    {
        if (lookup.Any(multiKey => object.Equals(multiKey.Item1, values.Item1) ||
            object.Equals(multiKey.Item2, values.Item2) ||
            object.Equals(multiKey.Item3, values.Item3)))
        {
            //throw an exception or something
        }
        else
        {
            lookup.Add(values);
        }
    }

    public Tuple<T1, T2, T3> GetFirst(T1 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item1, key));
    }

    public Tuple<T1, T2, T3> GetSecond(T2 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item2, key));
    }

    public Tuple<T1, T2, T3> GetThird(T3 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item3, key));
    }

    public void RemoveFirst(T1 key)
    {
        var values = GetFirst(key);
        if (values != null)
            lookup.Remove(values);
    }

    public void RemoveSecond(T2 key)
    {
        var values = GetSecond(key);
        if (values != null)
            lookup.Remove(values);
    }

    public void RemoveThird(T3 key)
    {
        var values = GetThird(key);
        if (values != null)
            lookup.Remove(values);
    }
}

Answer 2

Since you said you want compile-time type safety, there are a number of things you have to give up:

1. The ability to have any number of parameters (C# does not have variadic generics)
2. The ability to have multiple keys of the same type (the compiler will complain about ambiguous overloads)

These two limitations can be solved by using a reflection-based approach, but then you would lose the compile-time type safety.

So this is the solution you would use, according to your constraints (only works when all generic types are distinct!)

class TripleKeyDictionnary<TKey1, TKey2, TKey3>
{
    public Tuple<TKey2, TKey3> this[TKey1 key]
    {
        get
        {
            return _key1Lookup[key];
        }
    }

    public Tuple<TKey1, TKey3> this[TKey2 key]
    {
        get
        {
            return _key2Lookup[key];
        }
    }

    public Tuple<TKey1, TKey2> this[TKey3 key]
    {
        get
        {
            return _key3Lookup[key];
        }
    }

    private Dictionary<TKey1, Tuple<TKey2, TKey3>> _key1Lookup = new Dictionary<TKey1, Tuple<TKey2, TKey3>>();
    private Dictionary<TKey2, Tuple<TKey1, TKey3>> _key2Lookup = new Dictionary<TKey2, Tuple<TKey1, TKey3>>();
    private Dictionary<TKey3, Tuple<TKey1, TKey2>> _key3Lookup = new Dictionary<TKey3, Tuple<TKey1, TKey2>>();

    public void Add(TKey1 key1, TKey2 key2, TKey3 key3)
    {
        _key1Lookup.Add(key1, Tuple.Create(key2, key3));
        _key2Lookup.Add(key2, Tuple.Create(key1, key3));
        _key3Lookup.Add(key3, Tuple.Create(key1, key2));
    }
}