.NET字典解决冲突的效果如何?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (14)

我有一个自定义对象需要键入表格的问题。我需要生成一个唯一的数字键。我遇到碰撞问题,我想知道我是否可以利用字典来帮助我。假设我有这样一个对象:

class Thingy
{
    public string Foo;
    public string Bar;
    public string Others;
}

等等更多的领域。假设Foo和Bar是我的关键字段 - 如果它们在两个Thingys之间相等,那么这两个对象应该被认为是相等的(一个可能代表另一个的更新,其他字段被更新)。所以我有这些:

public override bool Equals(object obj)
{
    Thingy thing = (Thingy)obj; // yes I do type check first
    return (this.Foo == thing.Foo && this.Bar == thing.Bar);
}

public override int GetHashCode()
{
    return (this.Foo + this.Bar).GetHashCode(); // using default string impl
}

所以这在大部分情况下都适用,但是在极少数情况下,实际上不同的两个Thingys具有相同的哈希码。

我的问题是这样的:我可以使用字典<Thingy, int>在哪里放入我的Thingys,并使用字典中出现的顺序值作为我的实际密钥?我想知道,如果字典在检测到罕见的哈希码冲突时会调用我的Equals方法,确定这些对象实际上是不同的,并以不同的方式存储它们。然后,当我查看图像时,它会看到该散列的存储桶并搜索正确的Thingy,再次使用Equals进行比较。

这是字典的情况,还是它只解决散列码不同的冲突,但(散列%大小)是相同的?如果这不起作用,可能会发生什么?

提问于
用户回答回答于

散列冲突只影响性能,不影响完整性。

一个简单的测试是将GetHashCode()更改为仅返回1 ;. 你会注意到字典仍然行为正常,但是对于任何合理的数据集,它将表现得非常糟糕。

用户回答回答于

散列冲突将主要影响性能 - 不正确。只要Equals()行为正确。

Dictionary使用散列码作为将项目组织到单独的“桶”中的一种方式。如果太多项共享相同的散列码,则可能会遇到性能问题。但是,只要Equals()能够正确区分实例,就应该得到正确的结果。

散列码可能导致问题的地方在于可变对象如果Thingy课程允许FooBar更改字典中的项目,则可能无法在随后的访问尝试中找到它。这是因为现在生成的散列码与用于在字典中存储值的散列码不同。

扫码关注云+社区