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

本文关键字：字典 自定义 数据结构 | 更新日期: 2023-09-27 18:04:37

在我的应用程序中，我遇到需要为类的实例提供三个字符串键(我使用的是c# 3.5，所以我不能使用元组)。通过上网查找，我找到了这个答案，我使用了它的代码:https://stackoverflow.com/a/15804355/5090537

根据我的需要剪裁了它的点点滴滴之后，最后我的自定义类看起来是这样的:

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为我实现并且我不需要指定单独的实现是正确的吗?等号也一样?

2)我需要创建自己的自定义类的前提也是正确的吗?因为我不能使用字符串数组或字符串列表，例如，因为会有一个ReferenceEquals比较，而不是我需要的成员比较(key1等于key1, key2等于key2，和key3等于key3)?

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

好吧，这是一个很好的计划，创建自己的三键结构，将存储键，但首先让我们看看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方法的实现。这个实现的工作方式是，对于任何两个具有相同值的结构体，它们的哈希码总是匹配的(然而，相反的情况并不总是正确的，如果两个哈希码匹配，也不能100%保证所有的值都是相同的)。

现在，当我们都解决了，我们准备使用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

公立小学

正如ScottChamberlain正确指出的那样，ValueType对GetHashcode方法的实现有其自身的优缺点。它使用反射，这意味着它可能会导致性能问题，因此在某些情况下，最好不要依赖结构体对GetHashCode的实现，而是用自定义实现覆盖它。

Eric Lippert的博客上有一篇很棒的文章，叫做"GetHashCode的指导方针和规则"。

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

GetHashCode

GetHashCode方法被用作"廉价的";(快速)测试类的两个实例是否相等的方法。对两个相等的实例调用GetHashCode应该总是产生相同的结果。因此，如果两个实例调用GetHashCode的结果不相同，则它们不可能相等，因此没有必要进行更详细(并且更"昂贵")的比较。

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

所以，除非你要重新定义什么是"等于"意味着你的班级，你可能不需要担心GetHashCode。"平等"的概念因为你的课似乎没什么用。

<标题> 类设计

我不确定你实现的类是否理想。因为你是从Dictionary继承的，所以你继承了一些并不"适合"的方法。你们班。

例如，您的类现在有一个Keys方法，该方法返回顶级键(key1)，而不是您的类实际表示的三值键。

我想知道实现一个聚合字典的类是否比实现一个继承字典的类更好。

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

<标题> Misc h1> 后一点，有些人可能认为优化不成熟。代码:
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]"

…

这可能是实现目标最简单的方法:

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发布时，您可以使用漂亮的新Tuple声明

相关文章：