c# - 多键数据结构

Question

我正在寻找可以使用多个键进行搜索的数据结构。用一个例子更容易解释:

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];

这样的事情是否可能，如果可能，是否已经存在可以做到这一点的东西？您将如何实现将所有内容都视为键并通过搜索其中任何键返回所有关联键的东西？

理想情况下，您还可以使用任何数量和/或类型的参数:

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

Answer 1

所以这里有一个正好适用于三个键。您可以按照列出的模式为 4、5、6 等键制作一个。这将是很多代码，但并不是一项特别困难的任务(只是乏味)。

请注意，由于键的每个部分都有一个字典，因此它会占用大量内存；这就是您为从任何 key 访问事实的灵 active 所付出的代价。

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

下面是一个完全不同的方法。它不是为每个键填充查找，而是将所有值存储在一个集合中，并执行线性搜索以查找给定键的项目。它将有 O(n) 搜索/删除时间，但 O(1) 添加。以前的实现具有 O(1) 添加、删除和搜索，但会占用更多内存。

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