正确使用多键词典的自定义数据结构

Question

在我的应用程序中，有一次我遇到了 class 的实例需要三个字符串键（我使用的是 C# 3.5，所以我不能使用元组）。通过在线查看，我遇到了这个答案，我使用了它的代码：

在根据我的需要修改它的点点滴滴之后，最后我的自定义 class 看起来像这样：

public class MultiKeyDictionary<K1, K2, K3, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, V>>
{
    public V this[K1 key1, K2 key2, K3 key3]
    {
        get
        {
            return ContainsKey(key1) ? this[key1][key2, key3] : default(V);
        }
        set
        {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, V>();
            this[key1][key2, key3] = value;
        }
    }

    public bool ContainsKey(K1 key1, K2 key2, K3 key3)
    {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3);
    }

    public void Add(K1 key1, K2 key2, K3 key3, V value)
    {
        if (!ContainsKey(key1))
            this[key1] = new MultiKeyDictionary<K2, K3, V>();
        if (!this[key1].ContainsKey(key2, key3))
            this[key1][key2] = new Dictionary<K3, V>();
        this[key1][key2][key3] = value;
    }
}

这非常适合我的需要，但我对这个数据结构有几个问题：

1) 因为我实际上是从 Dictionary(K1, Dictionary(K2, V)) 继承的，所以假设 GetHashCode 是为我实现的并且我不需要指定单独的实现是否正确？ Equals 也一样吗？

2) 我需要创建自己的自定义的前提 class 是否也是正确的？因为我不能使用字符串数组或字符串列表，因为那样会有 ReferenceEquals 比较而不是我需要的成员比较（key1 等于 key1，key2 等于 key2，key3 等于键 3)?

Answer 1

GetHashCode

GetHashCode 方法被用作一种“便宜”（快速）的方法来测试 class 的两个实例是否相等。为两个相等的实例调用 GetHashCode 应该总是产生相同的结果。因此，如果两个实例调用 GetHashCode 的结果不同，则它们不可能相等，因此没有必要进行更详细（和更“昂贵”）的比较。

[另一方面，如果两个实例具有相同的哈希码，则需要进行更详细的比较以确定它们实际上是否相等。]

因此，除非您重新定义“等于”对您的 class 意味着什么，否则您可能不需要担心 GetHashCode。 class 的“平等”概念似乎没什么用。

Class 设计

我不确定您实施的 class 是否理想。因为您是从 Dictionary 继承的，所以您继承了一些并不真正“适合”您的 class.

的方法

例如，您的 class 现在有一个 Keys 方法，该方法 returns 顶级键 (key1) 而不是 class 其实代表.

我想知道实现一个聚合字典而不是继承自[=59=的class会不会更好] 字典。

没有 Tuple 的另一种选择是定义您自己的 TriKey<K1, K2, K3> class（具有 3 个描述您的键值的属性），并且只需使用 Dictionary<TriKey<K1, K2, K3>, V>.在那种情况下，你绝对会想要为你的 TriKey class 定义平等，并且你需要保持 GetHashCode 与平等的定义一致，因为字典查找是使用它的地方之一。

其他

最后一点，有些人可能认为过早优化。代码：

this[key1][key2][key3] = value;

... 将对您已经获取的值执行 2 次查找（因为您已经访问了 this[key1] 和 this[key1][key2]）。您可能要考虑使用局部变量来存储这些中间结果。

例如：

MultiKeyDictionary<K2, K3, V> d1; if (!TryGetValue(key1, out d1)) { d1 = new MultiKeyDictionary<K2, K3, V>(); this[key1] = d1; } // now use d1 rather than "this[key1]"

...其他的依此类推。

Answer 2

好吧，创建自己的三重键结构来存储键是个好计划，但首先让我们看一下 source code 的 KeyValuePair 结构。

现在让我们定义我们自己的 TripleKey 结构：

[Serializable]
public struct TripleKey<TKeyA, TKeyB, TKeyC>
{
    public TKeyA KeyA { get; };
    public TKeyB KeyB { get; };
    public TKeyC KeyC { get; };

    public TripleKey(TKeyA keyA, TKeyB keyB, TKeyC keyC)
    {
        this.KeyA = keyA;
        this.KeyB = keyB;
        this.KeyC = keyC;
    }

    // this code is almost the same as it is in Microsoft implementation
    public override string ToString()
    {
        var sBuilder = new StringBuilder();
        sBuilder.Append('(');
        if (KeyA != null)
        {
            sBuilder.Append(KeyA.ToString());
        }
        sBuilder.Append(", ");
        if (KeyB != null)
        {
            sBuilder.Append(KeyB.ToString());
        }
        sBuilder.Append(", ");
        if (KeyC != null)
        {
            sBuilder.Append(KeyC.ToString());
        }
        sBuilder.Append(')');
        return sBuilder.ToString();
    }
}

public static class TripleKey
{
    public static TripleKey<TKeyA, TKeyB, TKeyC> Create<TKeyA, TKeyB, TKeyC>(TKeyA keyA, TKeyB keyB, TKeyC keyC)
    {
        return new TripleKey<TKeyA, TKeyB, TKeyC>(keyA, keyB, keyC);
    }
}

public class MultiKeyDictionary<TKeyA, TKeyB, TKeyC, TValue> : Dictionary<TripleKey<TKeyA, TKeyB, TKeyC>, TValue>
{
    public TValue this[TKeyA keyA, TKeyB keyB, TKeyC keyC]
    {
        get
        {
            var key = TripleKey.Create(keyA, keyB, keyC);
            return base.ContainsKey(key) ? base[key] : default(TValue);
        }
        set
        {
            var key = TripleKey.Create(keyA, keyB, keyC);
            if (!ContainsKey(key))
                base.Add(key, value);

            this[key] = value;
        }
    }

    public bool ContainsKey(TKeyA keyA, TKeyB keyB, TKeyC keyC)
    {
        var key = TripleKey.Create(keyA, keyB, keyC);

        return base.ContainsKey(key);
    }

    public void Add(TKeyA keyA, TKeyB keyB, TKeyC keyC, TValue value)
    {
        base.Add(TripleKey.Create(keyA, keyB, keyC), value);
    }
}

关于结构类型的最伟大的事情之一是，因为它们继承自 ValueType，所以它们也继承了 GetHashCode 方法的实现。此实现的工作方式是，对于任何两个具有相同值的结构，它们的哈希码将始终匹配（然而，反之并不总是正确的，如果两个哈希码匹配，则不能百分百保证所有值也相同）。

现在，当我们都安顿下来后，我们就可以使用 MultiKeyDictionary<TKeyA, TKeyB, TKeyC, TValue> 或简单的 Dictionary<TripleKey<TKeyA, TKeyB, TKeyC>, TValue>。

一个简单的例子：

var myDict = new MultiKeyDictionary<string, double, double, string>
{
    {"Goodbye", 0.55, 9.00, "yaya"} // collection initializer works fine
};

myDict.Add("Hello", 1.11, 2.99, "hi");

Console.WriteLine(myDict.ContainsKey("Hello", 1.11, 2.99));  // true
Console.WriteLine(myDict.ContainsKey("a", 1.11, 2.99));      // false
Console.WriteLine(myDict["Hello", 1.11, 2.99]);              // hi

myDict.Add(TripleKey.Create("Hello", 1.11, 2.99), "gh");     // bang! exception, 
                                                             // key already exists

P.S.

正如 ScottChamberlain 所指出的那样，ValueType 的 implementation of GetHashcode 方法各有利弊。它使用反射，这意味着它可能会导致性能问题，因此在某些情况下，最好不要依赖结构的 GetHashCode 实现，而是使用自定义实现来覆盖它。

Eric Lippert 的博客中有一篇名为“Guidelines and rules for GetHashCode”的优秀文章。

工作示例：https://dotnetfiddle.net/y1a30V

Answer 3

这可能是完成您所追求的最简单的方法：

public class MultiKeyDictionary<TKey, TValue> : Dictionary<Tuple<TKey, TKey, TKey>, TValue>
{
    public MultiKeyDictionary()
        : base()
    {
    }
    ...
}

class Program
{
    static void Main(string[] args)
    {
        // C# 6.0 syntax
        var multiKeyDictionary = new MultiKeyDictionary<string, int>();
        multiKeyDictionary.Add(Tuple.Create("key1", "key2", "key3"), 36);

        // C# 7.0 syntax (not yet released).
        var multiKeyDictionary1 = new MultiDictionary<string, int>();
        multiKeyDictionary1.Add(("key1", "key2", "key3"), 36);
    }
}

C# 7.0 发布后，您可以使用漂亮的新元组声明。

正确使用多键词典的自定义数据结构

Correct usage of custom data structure for Multi Key Dictionary

.net

c#

dictionary

hashcode

GetHashCode

Class 设计

其他