我有一个自定义对象的问题,它需要为一个表设置键值。我需要生成一个唯一的数字密钥。我有碰撞问题,我想知道我是否可以利用字典来帮助我。假设我有一个这样的对象:
class Thingy
{
public string Foo;
public string Bar;
public string Others;
}
更多的字段,依此类推。假设Foo和Bar是我的关键字段-如果它们在两个事物之间相等,那么这两个对象就应该被认为是相等的(一个可能代表对另一个的更新,而其他字段则被更新)。所以我有这些:
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
>放在我的东西中,并使用字典中的序列值作为实际的键?我想知道,当检测到罕见的散列代码冲突时,Dictionary是否会调用我的Equals方法,确定对象实际上是不同的,并以不同的方式存储它们。我想象一下,当查找它时,它会看到一个存储该散列的桶,并搜索正确的Thingy,再次使用Equals进行比较。
这是字典的情况,还是它只解决散列代码不同,但(散列%大小)相同的冲突?如果这不起作用,还有什么可能呢?
发布于 2010-02-11 04:52:39
哈希冲突只会影响性能,而不会影响完整性。
一个简单的测试是将GetHashCode()简单地更改为返回1;。您将注意到,字典仍然可以正常运行,但对于任何合理的数据集,它的性能都会很差。
发布于 2010-02-11 08:50:59
GetHashCode是为在哈希表中使用而设计的,在哈希表中,冲突需要最小化但不能消除。如果需要生成真正唯一的键,GetHashCode是一个合理的起点(并且不像guid那样过长),但是您需要将键存储为对象的一部分,并单独维护所用键的列表。
虽然您可能能够从Dictionary的内部检索看起来有用的内容,但它可能不会可靠地工作-例如,如果您添加的条目多于最初分配给字典处理的条目,则底层数据结构将重新构建,单个条目可能最终位于词典的一个完全不同的部分。
https://stackoverflow.com/questions/2240231
复制相似问题