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);
    }
}