我试图用C#的词典实现简单的算法:
我的'外部'字典看起来像这样:Dictionary<paramID, Dictionary<string, object>>[其中paramID只是一个包含2个字符串的标识符]
如果键'x'已经在字典中,则将特定条目添加到该记录的字典中,如果它不存在则将其条目添加到外部字典中,然后将条目添加到内部字典中.
不知何故,当我使用TryGetValue时,它总是返回false,因此它总是在外部Dictionary中创建新条目 - 什么产生重复.
我的代码看起来或多或少像这样:
Dictionary<string, object> tempDict = new Dictionary<string, object>();
if(outerDict.TryGetValue(new paramID(xKey, xValue), out tempDict))
{
tempDict.Add(newKey, newValue);
}
if即使外部词典中存在此特定条目,也永远不会执行块内部.
我错过了什么吗？(如果你想我可以发布调试器的屏幕截图 - 或者你想要的其他东西)
如果你没有在paramID类型上覆盖equals和GetHashCode,并且它是一个类而不是一个struct,那么默认的相等含义将生效,并且每个paramID只会等于它自己.
你可能想要这样的东西:
public class ParamID : IEquatable<ParamID> // IEquatable makes this faster
{
private readonly string _first; //not necessary, but immutability of keys prevents other possible bugs
private readonly string _second;
public ParamID(string first, string second)
{
_first = first;
_second = second;
}
public bool Equals(ParamID other)
{
//change for case-insensitive, culture-aware, etc.
return other != null && _first == other._first && _second == other._second;
}
public override bool Equals(object other)
{
return Equals(other as ParamID);
}
public override int GetHashCode()
{
//change for case-insensitive, culture-aware, etc.
int fHash = _first.GetHashCode();
return ((fHash << 16) | (fHash >> 16)) ^ _second.GetHashCode();
}
}
对于要求的解释,我将做一个不同版本的ParamID,其中字符串比较是不区分大小写的而不是基于文化的(一种适用于某些计算机可读代码的形式(例如,在案例中匹配关键字) - 不敏感的计算机语言或不区分大小写的标识符,如语言标签),但不适用于人类可读的内容(例如,它不会意识到"SS"是对"ß"不区分大小写的匹配).此版本还考虑{"A" ,"B"}匹配{"B","A"} - 也就是说,它不关心字符串是什么方式.通过使用不同的规则做不同的版本,应该可以触及几个设计考虑因素发挥作用.
让我们从包含它的状态的两个字段的类开始:
public class ParamID
{
private readonly string _first; //not necessary, but immutability of keys prevents other possible bugs
private readonly string _second;
public ParamID(string first, string second)
{
_first = first;
_second = second;
}
}
此时如果我们执行以下操作:
ParamID x = new ParamID("a", "b");
ParamID y = new ParamID("a", "b");
ParamID z = x;
bool a = x == y;//a is false
bool b = z == x;//b is true
因为默认情况下,引用类型仅等于它自己.为什么？首先,有时这正是我们想要的,其次,如果没有程序员定义平等如何工作,我们可能还想要什么.
还要注意,如果ParamID是一个结构,那么它的定义就像你想要的那样.但是,如果它包含一个小数,那么实现效率会相当低,并且也会出错.所以无论哪种方式,明确地实现相等性总是一个好主意.
我们要做的第一件事就是覆盖不同的平等概念IEquatable<ParamID>.这不是绝对必要的(并且在.NET 2.0之前不存在)但是:
Dictionary<TKey, TValue>.现在,在实现平等概念时,我们必须遵循四条规则:
大多数情况下,你最终都会遵循所有这些规则而不考虑它,如果你在实现中特别陌生和聪明,你只需要检查它们.规则1也是我们可以利用的东西,在某些情况下为我们提供性能提升:
public class ParamID : IEquatable<ParamID>
{
private readonly string _first; //not necessary, but immutability of keys prevents other possible bugs
private readonly string _second;
public ParamID(string first, string second)
{
_first = first;
_second = second;
}
public bool Equals(ParamID other)
{
if(other == null)
return false;
if(ReferenceEquals(this, other))
return true;
if(string.Compare(_first, other._first, StringComparison.InvariantCultureIgnoreCase) == 0 && string.Compare(_second, other._second, StringComparison.InvariantCultureIgnoreCase) == 0)
return true;
return string.Compare(_first, other._second, StringComparison.InvariantCultureIgnoreCase) == 0 && string.Compare(_second, other._first, StringComparison.InvariantCultureIgnoreCase) == 0;
}
}
我们做的第一件事就是看看我们是否将等式与null进行比较.我们几乎总是希望在这种情况下返回false(并非总是如此,但异常是非常非常罕见的,如果你不确定你正在处理这样的异常,你几乎肯定不会),当然我们不想抛出NullReferenceException.
我们接下来要做的是查看对象是否与自身进行比较.这纯粹是一种优化.在这种情况下,它可能是浪费时间,但它对于更复杂的相等测试非常有用,所以值得指出这一点.这利用了身份需要平等的规则,即任何对象都等于自身(Ayn Rand似乎认为这在某种程度上是深刻的).
最后,在处理了这两个特例后,我们得出了实际的平等规则.正如我上面所说,我的例子认为两个对象是相同的,如果它们具有相同的两个字符串,以任何顺序,对于不区分大小写的序数比较,所以我有一些代码可以解决这个问题.
(请注意,我们比较组件部分的顺序会对性能产生影响.不是在这种情况下,但是对于包含int和字符串的类,我们首先要比较int,因为它更快,因此我们可能会找到一个false我们甚至看看之前的回答)
现在,在这一点上,我们有一个很好的基础来覆盖Equals定义的方法object:
public override bool Equals(object other)
{
return (other as ParamID);
}
由于as将返回ParamID如果引用other是ParamID和空为别的(包括如果空是什么,我们在第一时间被传递),因为我们已经处理好与空的比较,我们都是一套.
尝试在这一点编译,你会得到一个警告,你已经覆盖Equals但不是GetHashCode(如果你以相反的方式完成它也是如此).
字典(以及其他基于散列的集合,如HashTable和HashSet)使用GetHashCode来决定内部放置密钥的位置.它将采用哈希码,以其业务方式将其重新散列为较小的值,并使用它将对象放置在其内部存储中.
因此,很清楚为什么以下是一个坏主意ParamID在所有字段上都不是只读的:
ParamID x = new ParamID("a", "b");
dict.Add(x, 33);
x.First = "c";//x will now likely never be found in dict because its hashcode doesn't match its position!
这意味着以下规则适用于哈希码:
尽管最后一点,但很难值得记住结果.基于散列的集合通常会自己记忆值,因此在对象中这样做是浪费.
对于第一个实现,因为我们的相等方法依赖于字符串相等的默认方法,所以我们可以使用字符串默认哈希码.对于我的不同版本,我将使用另一种方法,稍后我们将探讨:
public override int GetHashCode()
{
return StringComparer.OrdinalIgnoreCase.GetHashCode(_first) ^ StringComparer.OrdinalIgnoreCase.GetHashCode(_second);
}
让我们将它与第一个版本进行比较.在这两种情况下,我们都获得了组件的哈希码.如果整数,字符或字节的值我们将使用值本身,但在这里我们建立在为这些部分实现相同逻辑的工作.在第一个版本中,我们使用GetHashCode的string本身,而是因为"a"有不同的哈希码为"A",将在这里工作,所以我们使用产生的散列码无视差的一类.
两者之间的另一个重要区别是,在第一种情况下,我们将这些位混合起来((fHash << 16) | (fHash >> 16)).这样做的原因是为了避免重复哈希.我们无法生成一个完美的哈希码,其中每个不同的对象具有不同的值,因为只有4294967296个可能的哈希码值,但ParamID的可能值更多(包括null,被视为哈希码为0).(有些情况下可以使用完整的哈希值,但它们会引起不同的关注点).由于这种不完美,我们不仅要考虑哪些价值可能,哪些价值可能.通常,像我们在第一个版本中所做的那样移位比特避免了具有相同散列的常见值.我们不希望{"A","B"}与{"B","A"}相同.
这是一个有趣的实验,产生一个故意不好的GetHashCode,总是返回0,它会起作用,但是不是接近O(1),字典将是O(n),而O(n)就是穷人!
第二个版本没有这样做,因为它有不同的规则,所以我们实际上想要考虑相同的值,但是切换为相等,因此具有相同的哈希码.
另一个很大的区别是使用StringComparer.OrdinalIgnoreCase.这是一个实例,StringComparer其中包括其他接口,实现IEqualityComparer<string>和IEqualityComparer.关于IEqualityComparer<T>和IEqualityComparer接口有两个有趣的事情.
第一个是基于散列的集合(例如字典)都使用它们,只是除非将一个实例传递给它们的构造函数,否则它们将使用DefaultEqualityComparer调用我们上面描述的Equals和GetHashCode方法.
另一个是,它允许我们忽略上面提到的Equals和GetHashCode,并从另一个类提供它们.这有三个好处:
我们可以在案例中使用它们(字符串是一个经典案例),其中存在多个"equals"的可能定义.
我们可以忽略该类的作者,并提供我们自己的.
我们可以使用它们来避免特定的攻击.此攻击的基础是您所提供的输入将被您正在攻击的代码进行哈希处理.您选择输入以便故意提供不同的对象,但散列相同.这意味着我们谈到避免早期的糟糕表现受到了打击,而且它可能非常糟糕,以至于它变成了拒绝服务攻击.通过向哈希代码提供具有随机元素的不同IEqualityComparer实现(但对于比较器的每个实例都是相同的),我们可以每次都改变算法以使攻击双重.对此的使用是罕见的(它必须是纯粹基于外部输入的哈希值,足以使性能差的真正伤害),但是当它出现时至关重要.
最后.如果我们覆盖Equals,我们可能也可能不想覆盖==和!=.保持它们只引用标识是有用的(有时这是我们最关心的)但是让它们引用其他语义("abc"=="ab"+"c")会很有用.是一个覆盖的例子).
综上所述:
引用对象的默认相等性是身份(仅等于其自身).
值类型的默认相等是所有字段的简单比较(但性能较差).
在任何一种情况下,我们都可以为我们的类改变相等的概念,但这必须涉及Equals和GetHashCode*
我们可以覆盖它并提供另一个平等概念.
Dictionary,HashSet,ConcurrentDictionary等都依赖于此.
Hashcodes表示从对象的所有值到32位数的映射.
对于我们认为相同的对象,哈希码必须相同.
Hashcodes必须传播良好.
*顺便说一下,匿名类有一个简单的比较,比如值类型,但性能更好,几乎可以匹配任何我们关心匿名类型哈希码的情况.
| 归档时间： |
|
| 查看次数： |
2342 次 |
| 最近记录： |