C#中元组（或数组）作为字典键

Question

我正在尝试在C＃中制作一个字典查找表。 我需要将3个值的元组解析为一个字符串。 我尝试使用数组作为键，但那行不通，我不知道该怎么办了。 现在我考虑制作一个字典的嵌套字典的字典，但那可能不太好看，尽管这是我在javascript中做的方式。

- AlexH

Answer 1

如果你使用的是.NET 4.0，请使用元组（Tuple）：

lookup = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();

如果不行，您可以定义一个Tuple并将其用作键。该元组需要重写GetHashCode、Equals和IEquatable：

struct Tuple<T, U, W> : IEquatable<Tuple<T,U,W>>
{
    readonly T first;
    readonly U second;
    readonly W third;

    public Tuple(T first, U second, W third)
    {
        this.first = first;
        this.second = second;
        this.third = third;
    }

    public T First { get { return first; } }
    public U Second { get { return second; } }
    public W Third { get { return third; } }

    public override int GetHashCode()
    {
        return first.GetHashCode() ^ second.GetHashCode() ^ third.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }
        return Equals((Tuple<T, U, W>)obj);
    }

    public bool Equals(Tuple<T, U, W> other)
    {
        return other.first.Equals(first) && other.second.Equals(second) && other.third.Equals(third);
    }
}

- Hallgrim

---

这个结构体还应该实现IEquatable<Tuple<T,U,W>>接口。这样，当哈希码发生冲突时，在Equals()被调用时可以避免装箱。 - Dustin Campbell

@jerryjvl和其他通过Google像我一样找到这篇文章的人，请注意，.NET 4的元组实现了equals方法（http://msdn.microsoft.com/en-us/library/dd270346.aspx），因此可以在字典中使用。 - Scott Chamberlain

你的 GetHashCode 实现不太好，因为它在字段排列置换下是不变的。 - CodesInChaos

元组不应该是一个结构体。在框架中，元组是一个引用类型。 - Michael Graczyk

@Thoraot - 当然，你的例子是错误的... 应该是这样的。为什么new object()会等于另一个new object()？它不只是使用直接引用比较... 试一下：bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower())); - Mike Marynowski

Answer 2

如果你在使用C# 7，考虑使用值元组作为复合键。通常情况下，值元组性能比传统的引用元组（Tuple<T1, …>）更好，因为值元组是值类型（结构体），而不是引用类型，所以它们避免了内存分配和垃圾收集成本。此外，它们提供更简洁和更直观的语法，如果需要，可以为它们的字段指定名称。它们还实现了字典所需的IEquatable<T>接口。

var dict = new Dictionary<(int PersonId, int LocationId, int SubjectId), string>();
dict.Add((3, 6, 9), "ABC");
dict.Add((PersonId: 4, LocationId: 9, SubjectId: 10), "XYZ");
var personIds = dict.Keys.Select(k => k.PersonId).Distinct().ToList();

- Douglas

---

实际上，在处理大量变量时，元组可能更快。在某些情况下，复制一个巨大的结构体会更慢。 - Felix K.

@FelixK：从值类型切换到引用类型的[一般推荐]截止点是16个字节。一个由三个int组成的3-tuple只占用12个字节，因此ValueTuple很好。然而，即使对于较大的n-tuple，我也会对Tuple持谨慎态度，因为字典查找键通常具有极短的生命周期，如果这些查找发生在热路径中，将导致垃圾收集方面承受很大压力。 - Douglas

根据使用情况而定，从我的经验来看，大多数情况下，使用对象不会出现垃圾回收问题。我曾经编写过一款商业3D引擎，因此必须尽可能进行优化。如果使用情况允许，您也可以选择可重用的键，但我从未这样做过。在90%的情况下，结构体就足够了，还有其他可以进行优化的地方。 - Felix K.

很遗憾，关于实际哈希算法的文档说明非常不透明。https://learn.microsoft.com/en-us/dotnet/api/system.valuetuple-1.gethashcode?view=net-5.0 - Marcos Pereira

Answer 3

在元组和嵌套字典的方法中，基于元组的方法几乎总是更好的选择。从可维护性角度来看，

• its much easier to implement a functionality that looks like:

  var myDict = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();
  

  than

  var myDict = new Dictionary<TypeA, Dictionary<TypeB, Dictionary<TypeC, string>>>();
  

  from the callee side. In the second case each addition, lookup, removal etc require action on more than one dictionary.

• Furthermore, if your composite key require one more (or less) field in future, you will need to change code a significant lot in the second case (nested dictionary) since you have to add further nested dictionaries and subsequent checks.

从性能角度考虑，您可以通过自己进行测量来得出最好的结论。但是在此之前，有一些理论上的限制需要考虑：

• 在嵌套字典的情况下，为每个键（外部和内部）添加一个额外的字典会产生一些内存开销（比创建元组更多）。

• 在嵌套字典的情况下，每个基本操作（如添加、更新、查找、删除等）都需要在两个字典中进行。现在有一种情况，嵌套字典方法可能更快，即当要查找的数据不存在时，因为中间字典可以绕过完整的哈希码计算和比较，但再次需要计时以确保。在存在数据的情况下，它应该更慢，因为需要执行两次查找（或者根据嵌套程度执行三次查找）。

• 关于元组方法，.NET元组在作为集合中的键使用时不是最高效的，因为其Equals和GetHashCode实现会对值类型进行装箱。

我会选择基于元组的字典，但如果我想要更好的性能，我会使用自己的元组并进行更好的实现。

---

顺便说一下，有些化妆品可以让字典变得很酷：

1. Indexer style calls can be a lot cleaner and intuitive. For eg,

   string foo = dict[a, b, c]; //lookup
   dict[a, b, c] = ""; //update/insertion
   

   So expose necessary indexers in your dictionary class which internally handles the insertions and lookups.

2. Also, implement a suitable IEnumerable interface and provide an Add(TypeA, TypeB, TypeC, string) method which would give you collection initializer syntax, like:

   new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
   { 
       { a, b, c, null }, 
       ...
   };
   

- nawfal

---

在嵌套字典的情况下，索引器语法不应该更像这样吗：string foo = dict[a][b][c]？ - Steven Rands

@nawfal 我能否在只有一个键而非全部键的情况下搜索元组字典？或者我可以这样做 dict[a,b] 然后 dict[a,c] 吗？ - Khan Engineer

如果“仅按一个键搜索”是指通过任何一个键获取值，则最好将字典重新设计为“任意键字典”。例如，如果您想要为键a和b获取值4，则可以将其设置为标准字典，并添加类似于dict[a] = 4和dict[b] = 4的值。如果从逻辑上讲，您的a和b应该是一个单元，则可能没有意义。在这种情况下，您可以定义一个自定义的IEqualityComparer，如果它们的任何属性相等，则将两个键实例视为相等。所有这些都可以通过反射来通用地完成。 - nawfal

@nawfal 感谢您的澄清。我使用字典嵌套字典，因为当我将键传递给字典时，它会返回一个字典，然后我再传递一个键到返回的字典中，它就会返回我所需的值，这样我就可以从字典中获取所需的值。但是，它的复杂度不保持恒定，我想一次传递两个键并返回结果，但有时我只需要针对一个键的值。 - Khan Engineer

@KhanEngineer 你所说的是当传递两个键时要获取值, 但有时只传递其中一个键也需要获取值吗？这种情况下，你的字典基本上是“任意键字典”。编写一个包含内部字典的集合类，编写一个IEqualityComparer进行"任意键比较"并将其传递给内部字典的构造函数。为该类编写2种类型的索引器，如 dict[a] 和 dict[a, b]，以便可以以两种方式查询。请提出一个新问题，以便人们能够更好地帮助您。评论区超出了您的问题范围。 - nawfal

Answer 4

简洁、干净、快速、易读的方法是：

• 为当前类型生成相等成员（Equals()和GetHashCode()） 方法。像ReSharper这样的工具不仅会创建这些方法，还会为相等性检查和/或计算哈希代码生成必要的代码。生成的代码将比元组实现更优。
• 只需创建一个从元组派生的简单键类。

添加类似于以下内容：

public sealed class myKey : Tuple<TypeA, TypeB, TypeC>
{
    public myKey(TypeA dataA, TypeB dataB, TypeC dataC) : base (dataA, dataB, dataC) { }

    public TypeA DataA => Item1; 

    public TypeB DataB => Item2;

    public TypeC DataC => Item3;
}

所以你可以和字典一起使用它:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};

• 你也可以在合同中使用它
• 作为Linq中的连接或分组的关键字
• 这样做，你永远不会错误地输入Item1、Item2、Item3的顺序...
• 你不需要记住或查看代码以了解去哪里获取某些东西
• 无需覆盖IStructuralEquatable、IStructuralComparable、IComparable、ITuple，它们已经在这里了

- gabba

---

现在你可以使用表达式体成员，它甚至更加简洁，例如 public TypeA DataA => Item1;。 - andrewtatham

Answer 5

如果出于某种原因，您真的想避免创建自己的元组类或使用内置在.NET 4.0中的元组类，则还有一种可能的方法；您可以将这三个关键值合并为一个单一的值。

例如，如果这三个值是整数类型，总共不超过64位，您可以将它们组合成一个ulong。

最坏的情况下，您始终可以使用字符串，只要确保其中的三个组件用某个字符或序列分隔开来，该字符或序列不会出现在密钥的组件中，例如，对于三个数字，您可以尝试：

string.Format("{0}#{1}#{2}", key1, key2, key3)

显然，这种方法存在一定的组合开销，但是根据您的使用情况，这可能微不足道，不需要太在意它。

- jerryjvl

---

我认为这很大程度上取决于上下文；如果我有三种整数类型要合并，而性能并不关键，那么这样做是完全可行的，几乎没有出错的可能性。当然，所有这些在 .NET 4 中都已经完全被淘汰了，因为 Microsoft 将为我们提供（大概是正确的！）元组类型。 - jerryjvl

你甚至可以将这种方法与 JavaScriptSerializer 结合使用，为你连接字符串和/或整数类型的 数组。这样，你就不需要自己想出分隔符字符了。 - binki

如果任何一个键(key1,key2,key3)中包含分隔符("#")的字符串，情况可能会变得非常混乱。 - Greg

Answer 6

这里是.NET元组的参考：

[Serializable] 
public class Tuple<T1, T2, T3> : IStructuralEquatable, IStructuralComparable, IComparable, ITuple {

    private readonly T1 m_Item1; 
    private readonly T2 m_Item2;
    private readonly T3 m_Item3; 

    public T1 Item1 { get { return m_Item1; } }
    public T2 Item2 { get { return m_Item2; } }
    public T3 Item3 { get { return m_Item3; } } 

    public Tuple(T1 item1, T2 item2, T3 item3) { 
        m_Item1 = item1; 
        m_Item2 = item2;
        m_Item3 = item3; 
    }

    public override Boolean Equals(Object obj) {
        return ((IStructuralEquatable) this).Equals(obj, EqualityComparer<Object>.Default);; 
    }

    Boolean IStructuralEquatable.Equals(Object other, IEqualityComparer comparer) { 
        if (other == null) return false;

        Tuple<T1, T2, T3> objTuple = other as Tuple<T1, T2, T3>;

        if (objTuple == null) {
            return false; 
        }

        return comparer.Equals(m_Item1, objTuple.m_Item1) && comparer.Equals(m_Item2, objTuple.m_Item2) && comparer.Equals(m_Item3, objTuple.m_Item3); 
    }

    Int32 IComparable.CompareTo(Object obj) {
        return ((IStructuralComparable) this).CompareTo(obj, Comparer<Object>.Default);
    }

    Int32 IStructuralComparable.CompareTo(Object other, IComparer comparer) {
        if (other == null) return 1; 

        Tuple<T1, T2, T3> objTuple = other as Tuple<T1, T2, T3>;

        if (objTuple == null) {
            throw new ArgumentException(Environment.GetResourceString("ArgumentException_TupleIncorrectType", this.GetType().ToString()), "other");
        }

        int c = 0;

        c = comparer.Compare(m_Item1, objTuple.m_Item1); 

        if (c != 0) return c; 

        c = comparer.Compare(m_Item2, objTuple.m_Item2);

        if (c != 0) return c; 

        return comparer.Compare(m_Item3, objTuple.m_Item3); 
    } 

    public override int GetHashCode() { 
        return ((IStructuralEquatable) this).GetHashCode(EqualityComparer<Object>.Default);
    }

    Int32 IStructuralEquatable.GetHashCode(IEqualityComparer comparer) { 
        return Tuple.CombineHashCodes(comparer.GetHashCode(m_Item1), comparer.GetHashCode(m_Item2), comparer.GetHashCode(m_Item3));
    } 

    Int32 ITuple.GetHashCode(IEqualityComparer comparer) {
        return ((IStructuralEquatable) this).GetHashCode(comparer); 
    }
    public override string ToString() {
        StringBuilder sb = new StringBuilder();
        sb.Append("("); 
        return ((ITuple)this).ToString(sb);
    } 

    string ITuple.ToString(StringBuilder sb) {
        sb.Append(m_Item1); 
        sb.Append(", ");
        sb.Append(m_Item2);
        sb.Append(", ");
        sb.Append(m_Item3); 
        sb.Append(")");
        return sb.ToString(); 
    } 

    int ITuple.Size { 
        get {
            return 3;
        }
    } 
}

- Michael Graczyk

---

获取哈希码的实现方式为 ((item1 ^ item2) * 33) ^ item3。 - Michael Graczyk

Answer 7

我会用适当的GetHashCode重写你的Tuple，并将其作为键使用。只要你重载了适当的方法，就应该能看到不错的性能表现。

- John Gietzen

---

IComparable对于在Dictionary<TKey,TValue>中存储或定位键没有影响。这一切都是通过GetHashCode()和IEqualityComparer<T>完成的。实现IEquatable<T>将会获得更好的性能，因为它减轻了默认EqualityComparer引起的装箱问题，后者会回退到Equals(object)函数。 - Dustin Campbell

我本来想提一下GetHashCode，但我认为如果HashCodes相同，Dictionary会在这种情况下使用IComparable... 我猜错了。 - John Gietzen

Answer 8

如果您的消费代码可以使用IDictionary<>接口而不是Dictionary，我的直觉是使用带有自定义数组比较器的SortedDictionary<>，例如：

class ArrayComparer<T> : IComparer<IList<T>>
    where T : IComparable<T>
{
    public int Compare(IList<T> x, IList<T> y)
    {
        int compare = 0;
        for (int n = 0; n < x.Count && n < y.Count; ++n)
        {
            compare = x[n].CompareTo(y[n]);
        }
        return compare;
    }
}

并且可以这样创建（使用int[]仅为具体示例）：

var dictionary = new SortedDictionary<int[], string>(new ArrayComparer<int>());

- mungflesh

Answer 9

所以最新的答案是使用数组。创建这个类：

        class StructuralEqualityComparer<T> : EqualityComparer<T[]>
        {
            public override bool Equals(T[] x, T[] y)
            {
                return StructuralComparisons.StructuralEqualityComparer
                    .Equals(x, y);
            }

            public override int GetHashCode(T[] obj)
            {
                return StructuralComparisons.StructuralEqualityComparer
                    .GetHashCode(obj);
            }
        }

然后像这样使用它：

var dict = new Dictionary<object[], SomeOtherObject>(new StructuralEqualityComparer<object>())

这个字典将正确调用数组的最后（我相信）8个元素的GetHashCode。这已经足够了，因为哈希码不是唯一的，但我们需要字典来获取它们。还需要一些代码来将它们组合起来。

- Arturo Hernandez

Answer 10

你可以像这样使用IDictionary

Dictionary<TypeSearch, (bool a, bool b)>  SearchConditions = new Dictionary<TypeSearch, (bool a, bool b)>
    {
        { TypeSearch.Neither, (false , false ) },
        { TypeSearch.OnlySearch, (true , false ) },
        { TypeSearch.OnlyPosition, (false , true ) },
        { TypeSearch.BothThem, (true , true ) }
    };

像这样的搜索

private TypeSearch GetTypeSearch(string _search, string _position) => SearchConditions
        .FirstOrDefault(t => t.Value == (string.IsNullOrEmpty(_search), string.IsNullOrEmpty(_position))).Key;

- Josue Alfaro

---

这并没有回答问题，问题是关于如何使用元组作为 键。 - Klaus Gütter