元组(或数组)作为C#中的字典键

我正在试图在C#中创build一个字典查找表。 我需要将一个三元组的值parsing为一个string。 我尝试使用数组作为键,但没有奏效,我不知道还有什么要做。 在这一点上,我正在考虑做一本字典词典,但是这可能不是很漂亮的看,虽然这是我如何在JavaScript中做到这一点。

如果您使用的是.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); } } 

在基于元组和嵌套字典的方法之间,基于元组的基本上总是更好。

从可维护性的angular度来看

  • 它更容易实现一个function,如下所示:

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

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

    从被叫方。 在第二种情况下,每个添加,查找,删除等都需要对多个字典进行操作。

  • 而且,如果你的组合键将来需要多一个(或更less)的字段,你将需要在第二种情况(嵌套字典)中改变很多代码,因为你必须添加更多的嵌套字典和后续的检查。

从性能的angular度来看 ,你可以得到的最好的结论是自己测量。 但是,您可以事先考虑一些理论上的限制:

  • 在嵌套字典的情况下,每个键(外部和内部)都有一个额外的字典会有一些内存开销(比创build元组要多)。

  • 在嵌套字典的情况下,每个基本动作如添加,更新,查找,删除等都需要在两个字典中进行。 现在有一种情况是嵌套的字典方法可以更快,也就是说,当查找的数据不存在时,由于中间字典可以绕过完整的哈希码计算和比较,但是应该再次确定时间。 在数据存在的情况下,查找应该执行两次(或者取决于嵌套)。

  • 关于元组的方法,.NET元组并不是性能最高的元素,因为它的EqualsGetHashCode实现会导致值types的装箱 。

我会用基于元组的字典,但如果我想要更多的性能,我会用更好的实现自己的元组。


在一个侧面说明,很less有化妆品可以使字典很酷:

  1. 索引器风格的调用可以更清洁和直观。 例如,

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

    因此,在您的字典类中公开内部处理插入和查找的必要索引器。

  2. 此外,实现一个合适的IEnumerable接口,并提供一个Add(TypeA, TypeB, TypeC, string)方法,它会给你集合初始值设定语法,如:

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

如果由于某种原因,您确实想要避免创build自己的Tuple类,或者使用.NET 4.0内置的方法,还有一种方法可行。 您可以将三个关键值组合到一个值中。

例如,如果这三个值是整数types,不超过64位,则可以将它们组合成一个ulong

最坏的情况下,你总是可以使用一个string,只要你确保其中的三个组件是用一些字符或顺序来分隔的,而这些字符或顺序不会出现在密钥的组件中,例如,你可以尝试使用三个数字:

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

在这种方法中显然有一些组合的开销,但取决于你使用的是什么,这可能是微不足道的,不关心它。

我会用适当的GetHashCode重载你的元组,并将它用作关键字。

只要你重载正确的方法,你应该看到体面的performance。

好,干净,快速,简单和可读的方式是:

只是做一个简单的从一个元组派生的关键类

添加类似这样的东西:

 public sealed class myKey : Tuple<TypeA, TypeB, TypeC> { public myKey(TypeA dataA, TypeB dataB, TypeC dataC) : base (dataA, dataB, dataC) { } public TypeA DataA { get { return Item1; } } public TypeB DataB { get { return Item2; } } public TypeC DataC { get { return 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中join或分组的关键
  • 这样,你永远不会输错Item1,Item2,Item3的顺序…
  • 你不需要记住或查看代码来理解去哪里得到的东西
  • 无需重写IStructuralEquatable,IStructuralComparable,IComparable,ITuple他们都在这里

这里是.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; } } } 

如果你的消费代码可以做一个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; } } 

这样创build(使用int []只是为了具体的例子):

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