代码之家  ›  专栏  ›  技术社区  ›  Tesserex

.NET字典解决冲突的能力如何?

  •  15
  • Tesserex  · 技术社区  · 15 年前

    我有一个自定义对象的问题,需要为表设置键。我需要生成一个唯一的数字键。我有碰撞的问题,我想知道我是否能利用字典来帮助我。假设我有这样一个物体:

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

    还有更多的领域。假设foo和bar是我的关键字段-如果它们在两个thingy之间相等,那么这两个对象应该被视为相等(一个表示对另一个对象的更新,另一个则表示对其他对象的更新),所以我有:

    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
    }
    

    所以这在很大程度上是可行的,但是很少有两种不同的东西有相同的哈希代码。

    我的问题是:我能用字典吗 <Thingy, int >我把我的东西放在哪里,用字典中的序列值作为我的实际键?我想知道,在检测到罕见的哈希代码冲突时,字典是否会调用我的equals方法,确定对象实际上是不同的,并以不同的方式存储它们。我想象一下,当它向上看的时候,它会看到一个桶,里面有一个散列,然后搜索正确的内容,再次使用equals进行比较。

    这是字典的情况,还是它只解决哈希代码不同但(哈希%大小)相同的冲突?如果这行不通,怎么办?

    3 回复  |  直到 11 年前
        1
  •  25
  •   Bob    15 年前

    哈希冲突只影响性能,而不影响完整性。

    一个简单的测试是将getHashCode()更改为只返回1;。您会注意到字典的行为仍然正常,但是对于任何合理的数据集,它的性能都非常糟糕。

        2
  •  18
  •   LBushkin    15 年前

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

    Dictionary 使用哈希代码作为将项目组织为单独的“bucket”的方法。如果有太多的项共享相同的哈希代码,则可能会遇到性能问题。但是,只要 等式() 能够正确区分实例,应该得到正确的结果。

    哈希代码可能导致问题的地方在于 可变对象 . 如果你 Thingy 类允许 Foo Bar 若要更改字典中的某个项目,则在随后的访问尝试中可能找不到该项目。这是因为现在生成的哈希代码与用于在字典中存储值的哈希代码不同。

        3
  •  1
  •   Tom Clarkson    15 年前

    GetHashCode设计用于哈希表,在哈希表中需要最小化冲突,但不能消除冲突。如果您需要生成一个真正唯一的密钥,gethashcode是一个合理的起点(不超过guid),但是您需要将密钥存储为对象的一部分,并单独维护已使用密钥的列表。

    虽然您可能能够从字典的内部检索到看起来可用的内容,但它可能无法可靠地工作——例如,如果您添加的项多于字典最初分配给处理的项,则底层数据结构将得到重建,单个项最终可能位于字典的完全不同的部分。