我正在尝试在 C# 中制作字典查找表。我需要将一个三元组的值解析为一个字符串。我尝试使用数组作为键,但这不起作用,我不知道还能做什么。在这一点上,我正在考虑制作一个词典词典,但这可能不是很漂亮,尽管我会在 javascript 中这样做。
9 回答
如果您使用的是 .NET 4.0,请使用元组:
lookup = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();
如果不是,您可以定义 aTuple
并将其用作键。元组需要覆盖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);
}
}
如果您使用的是 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();
在基于元组和嵌套字典的方法之间,基于元组的方法几乎总是更好。
从可维护性的角度来看,
它更容易实现如下所示的功能:
var myDict = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();
比
var myDict = new Dictionary<TypeA, Dictionary<TypeB, Dictionary<TypeC, string>>>();
从被叫方。在第二种情况下,每次添加、查找、删除等都需要对多个字典进行操作。
此外,如果您的复合键将来需要一个更多(或更少)字段,您将需要在第二种情况(嵌套字典)中大量更改代码,因为您必须添加更多嵌套字典和后续检查。
从性能的角度来看,您可以得出的最佳结论是自己衡量。但是您可以事先考虑一些理论上的限制:
在嵌套字典的情况下,为每个键(外部和内部)添加一个额外的字典将产生一些内存开销(比创建元组所需要的更多)。
在嵌套字典的情况下,添加、更新、查找、删除等每个基本操作都需要在两个字典中执行。现在有一种情况,嵌套字典方法可以更快,即,当正在查找的数据不存在时,因为中间字典可以绕过完整的哈希码计算和比较,但是应该再次确定它的时间。在存在数据的情况下,它应该更慢,因为查找应该执行两次(或三次,取决于嵌套)。
关于元组方法,.NET 元组在用作集合中的键时并不是性能最高的,因为它的
Equals
实现GetHashCode
会导致值类型的装箱。
我会使用基于元组的字典,但如果我想要更高的性能,我会使用我自己的元组来更好地实现。
附带说明一下,很少有化妆品可以让字典变得很酷:
索引器风格的调用可以更加简洁和直观。例如,
string foo = dict[a, b, c]; //lookup dict[a, b, c] = ""; //update/insertion
因此,在内部处理插入和查找的字典类中公开必要的索引器。
此外,实现一个合适的
IEnumerable
接口并提供一个Add(TypeA, TypeB, TypeC, string)
方法,该方法将为您提供集合初始化器语法,例如:new MultiKeyDictionary<TypeA, TypeB, TypeC, string> { { a, b, c, null }, ... };
好的、干净、快速、简单和易读的方法是:
- 为当前类型生成相等成员(Equals() 和 GetHashCode())方法。ReSharper之类的工具不仅可以创建方法,还可以生成必要的代码以进行相等性检查和/或计算哈希码。生成的代码将比 Tuple 实现更优化。
- 只需从 tuple 派生一个简单的键类。
添加类似这样的内容:
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 他们都已经在这里了
如果出于某种原因您真的想避免创建自己的 Tuple 类,或者使用内置于 .NET 4.0 中的 on,还有另一种方法可能;您可以将三个键值组合成一个值。
例如,如果这三个值是整数类型一起不超过 64 位,您可以将它们组合成一个ulong
.
在最坏的情况下,您始终可以使用字符串,只要您确保其中的三个组件由键的组件内不出现的某些字符或序列分隔,例如,您可以尝试使用三个数字:
string.Format("{0}#{1}#{2}", key1, key2, key3)
这种方法显然有一些组合开销,但取决于你使用它的目的,这可能是微不足道的,不需要关心它。
这是 .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;
}
}
}
我会用适当的 GetHashCode 覆盖您的元组,并将其用作键。
只要您重载正确的方法,您应该会看到不错的性能。
如果您的消费代码可以使用 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>());
所以最新的答案是改用数组。创建这个类:
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>())
该字典将正确调用 GetHashCode 以获取数组的最后(我相信)8 个元素。这已经足够了,因为哈希码不是唯一的,但我们需要字典来获取它们。以及一些将它们组合起来的代码。