标签: gethashcode

在编写我自己的ByteArray内部使用字节数组的不可变类时,我实现了IStructuralEquatable接口.在我的实现中,我将计算哈希码的任务委托给内部数组.在测试它时,令我惊讶的是,我发现我的两个不同的数组具有相同的结构哈希码,即它们返回相同的值GetHashCode.重现:

IStructuralEquatable array11 = new int[] { 1, 1 };
IStructuralEquatable array12 = new int[] { 1, 2 };
IStructuralEquatable array22 = new int[] { 2, 2 };

var comparer = EqualityComparer<int>.Default;
Console.WriteLine(array11.GetHashCode(comparer));     // 32
Console.WriteLine(array12.GetHashCode(comparer));     // 32
Console.WriteLine(array22.GetHashCode(comparer));     // 64

IStructuralEquatable是一个非常新的和未知的,但我在某处读到它可以用来比较集合和数组的内容.我错了,还是我的.Net错了？

请注意,我不是在谈论Object.GetHashCode!

编辑:所以,我显然是错的,因为不等对象可能有相同的哈希码.但是,不是要求GetHashCode一组有点随机分布的值作为要求吗？经过一些测试后,我发现任何两个具有相同第一个元素的数组都具有相同的哈希值.我仍然认为这是一种奇怪的行为.

尝试 #3 来简化这个问题：

泛型List<T>可以包含任何类型 - 值或引用。当检查列表是否包含对象时，.Contains()使用类型 T 的默认值EqualityComparer<T>并调用.Equals()（这是我的理解）。如果没有定义 EqualityComparer，则默认比较器将调用.Equals(). 默认情况下，.Equals()调用.ReferenceEquals(), so.Contains()仅当列表包含完全相同的对象时才返回 true。

直到您需要重写.Equals()以实现值相等，此时默认比较器表示如果两个对象具有相同的值，则它们是相同的。我想不出有哪一种情况适合引用类型。

我从 @Enigmativity 听到的是，实现IEqualityComparer<StagingDataRow>将为我键入的 DataRow 提供一个默认的相等比较器，该比较器将用于代替Object\xe2\x80\x93 的默认比较器，从而允许我在StagingDataRow.Equals().

问题：

\n
1. 我的理解正确吗？
\n
2. 我能否保证 .NET 框架中的所有内容都会调用EqualityComparer<StagingDataRow>.Equals()而不是调用StagingDataRow.Equals()？
\n
3. 应该IEqualityComparer<StagingDataRow>.GetHashCode(StagingDataRow obj)哈希什么，它应该返回与 相同的值吗StagingDataRow.GetHashCode()？
\n
4. 传递给什么IEqualityComparer<StagingDataRow>.GetHashCode(StagingDataRow obj)？我正在寻找的对象还是列表中的对象？两个都？让实例方法接受自身作为参数会很奇怪......
\n

一般来说，在重写时如何区分值相等和引用相等.Equals()？

我已经看到建议使用GetHashCode函数的素数实现,例如这里.但是使用下面的代码(在VB中,抱歉),似乎该实现提供了与"天真"xor实现相同的哈希密度.如果密度相同,我认为在两种实现中都存在相同的碰撞概率.我错过了为什么主要方法更受欢迎？

我认为如果哈希码是一个字节,我不会失去整数情况的一般性.

Sub Main()
    Dim XorHashes(255) As Integer
    Dim PrimeHashes(255) As Integer

    For i = 0 To 255
        For j = 0 To 255
            For k = 0 To 255
                XorHashes(GetXorHash(i, j, k)) += 1
                PrimeHashes(GetPrimeHash(i, j, k)) += 1
            Next
        Next
    Next

    For i = 0 To 255
        Console.WriteLine("{0}: {1}, {2}", i, XorHashes(i), PrimeHashes(i))
    Next
    Console.ReadKey()
End Sub

Public Function GetXorHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Return CByte((valueOne Xor …

我需要在GetHashCode中为BitArray生成快速哈希码.我有一个字典,其中键是BitArrays,所有BitArrays长度相同.

有没有人知道从可变位数生成良好哈希的快速方法,如在这种情况下？

更新:

我最初采用的方法是直接通过反射访问内部int数组(速度比这种情况下的封装更重要),然后对这些值进行异或.XOR方法似乎运行良好,即在"字典"中搜索时,我的"等于"方法不会过度调用:

    public int GetHashCode(BitArray array)
    {
        int hash = 0;
        foreach (int value in array.GetInternalValues())
        {
            hash ^= value;
        }
        return hash;
    }

但是,Mark Byers建议并在StackOverflow其他地方看到的方法稍好一些(对于我的测试数据,XOR为16570等于呼叫,而对于XOR为16608).请注意,此方法修复了前一个错误,其中超出位数组末尾的位可能会影响散列值.如果位数组的长度减少,则可能发生这种情况.

    public int GetHashCode(BitArray array)
    {
        UInt32 hash = 17;
        int bitsRemaining = array.Length;
        foreach (int value in array.GetInternalValues())
        {
            UInt32 cleanValue = (UInt32)value;
            if (bitsRemaining < 32)
            {
                //clear any bits that are beyond the end of the array
                int bitsToWipe = 32 - bitsRemaining;
                cleanValue <<= bitsToWipe;
                cleanValue >>= bitsToWipe;
            } …

我对此感到疑惑,所以我想我会问它.

您将看到的大多数地方使用相同的语义逻辑来覆盖Equals作为成员相等的GetHashCode ...但是它们通常使用不同的实现:

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }
        var other = (MyType)obj;
        if (other.Prop1 != Prop1)
        {
            return false;
        }
        return true;
    }

    public override int GetHashCode()
    {
        int hash = -657803396;
        num ^= Prop1.GetHashCode();
        return num;
    }

如果您正在为您的类型实现成员相等(假设存储在字典中),为什么不重写GetHashCode,然后对Equals执行类似的操作:

    public override bool Equals(object obj)
    {
        return this.HashEqualsAndIsSameType(obj);
    }

    public static bool HashEquals(this object source, object obj)
    {
        if (source != null && obj != null)
        {
            return …

可能的重复：
如何在.net（c＃）中为可安全存储在数据库中的字符串创建HashCode？

我计划在数据库中存储数十万个URL。我的UrlInfo表中的每一行都是不可变的，其中URL本身是逻辑主键。由于URL可能相当长，因此我决定对URL进行哈希处理，以作为添加新行时查找可能匹配项的快速方法。哈希不是我真正的钥匙，只是一种快速查找可能匹配项的方法。另外，我在每个域中使用RegEx模式，该模式将URL的本质提取为可以与其他URL进行比较的内容。我也将RegEx的结果存储为哈希，并且不关心它是否会产生重复项。

直到我了解到C＃的string.GetHashCode（）方法（我一直在使用它来对事物进行哈希处理）之前，一切都进展顺利，并不能保证它在.Net实现中是唯一的。当我尝试将哈希函数从ASP.Net迁移到SQLServer CLR代码时，我注意到了这一点。该Web应用程序使用.Net 4.0，而我了解到，SQLServer 2008 R2使用.Net 3.5。他们为相同的字符串产生了单独的哈希结果，所以现在我需要摆脱使用string.GetHashCode（）的原因，因为当我将应用程序升级到.Net的将来版本时，我不必担心这种变化。

所以，问题：

1. 自从在数据库中存储哈希后，我的体系结构是否有气味？还有更好的方法吗？显然，微软不希望我存储哈希结果！

2. 有人可以推荐一个好的C＃替换算法来哈希字符串吗？我在这里看到了乔恩（Jon），但不完全确定如何修改以使其适用于字符串（使用ascii代码遍历每个字符？）。

3. 有没有比使用散列算法更好的字符串压缩算法？

谢谢

令人敬畏的回应有很多。非常感谢你！！！

我需要使用Dictionary<long, string>给定两个实例的集合d1以及d2它们各自具有相同KeyValuePair<long, string>内容的集合,这些集合可以按任何顺序插入:

1. (d1 == d2) 评估为 true
2. d1.GetHashCode() == d2.GetHashCode()

通过使用SortedDictionary而不是常规来最容易地实现第一个要求Dictionary.

第二个要求是必要的,因为我需要存储一个点Dictionary<Dictionary<long, string>, List<string>- 主要Dictionary类型用作另一个的键Dictionary,如果HashCodes不基于相同的内容进行评估,则使用ContainsKey()将不会按照我想要的方式工作(即:如果已经有一个项目d1作为其键插入到字典中,那么dictionary.ContainsKey(d2)应该评估为true.

为此,我创建了一个新对象class ComparableDictionary : SortedDictionary<long, string>,并包含以下内容:

public override int GetHashCode() {            
   StringBuilder str = new StringBuilder();
   foreach (var item in this) {
      str.Append(item.Key);
      str.Append("_");
      str.Append(item.Value);
      str.Append("%%");
   }
   return str.ToString().GetHashCode();
 }

在我的单元测试中,这符合相等和哈希码的标准.但是,在阅读GetHashCode的指南和规则时,我遇到了以下内容:

规则:当对象包含在依赖于哈希代码保持稳定的数据结构中时,GetHashCode返回的整数必须永远不会更改

虽然很危险,但允许一个对象的哈希码值可以随着对象的字段变异而变异.如果你有这样一个对象,并把它放在一个哈希表中,那么改变对象的代码和维护哈希表的代码需要有一些商定的协议,以确保对象在进入时不会发生变异.哈希表.该协议的外观取决于您.

如果对象的哈希代码在哈希表中变异,那么显然Contains方法就会停止工作.你把对象放在#5桶中,你改变它,当你问集合是否包含变异对象时,它会在#74桶中查找并找不到它.

请记住,对象可以以您不期望的方式放入哈希表中.许多LINQ序列运算符在内部使用哈希表.在枚举返回它们的LINQ查询时,不要危险地改变对象! …

这是一个学术观点,但我觉得如果我不理解为什么这会被诸如Effective Java和许多SO问题这样的书推荐,我不完全理解哈希码.

假设:

public sealed class Point
{
    private readonly int x;
    private readonly int y;

    //constructor ommited

    //equals ommited

    public override int GetHashcode()
    {
       int hash = 17; //why should the initial value be non-zero?
       unchecked
       {
         hash = hash * 31 + x; //do not tell me why I should use primes - that is not the question
         hash = hash * 31 + y;
         return hash;
       }
    }
}

现在,据推测,初始值的原因是它减少了其中一个组件为零的冲突.

我很想找到任何有帮助的例子.

这是一个碰撞的例子,但是初始值没有任何可能性.

x   y   Hash Without initial …

我有两个相关的问题:

1. 按位运算符>>>表示我们正在将二进制数转移多个位置,同时在最高位填充0.但是,为什么以下操作产生相同的数字:5 >>> 32产生5和-5 >>> 32产生-5.因为如果上面的描述是正确的,那么这两个操作都会产生0作为最终结果.

2. 在上面的继续中,根据Effective Java book,我们应该在计算哈希码时使用(int)(f ^(f >>> 32))(如果字段很长)(如果字段很长).为什么我们这样做,解释是什么

帮助说:

匿名类型是直接从对象派生的类类型,不能转换为除object之外的任何类型.尽管您的应用程序无法访问它,但编译器为每个匿名类型提供了一个名称.从公共语言运行库的角度来看,匿名类型与任何其他引用类型没有区别.

如果程序集中的两个或多个匿名对象初始值设定项指定了具有相同顺序且具有相同名称和类型的属性序列,则编译器会将对象视为相同类型的实例.它们共享相同的编译器生成的类型信息.

因为匿名类型上的Equals和GetHashCode方法是根据属性的Equals和GetHashCode方法定义的,所以同一匿名类型的两个实例只有在它们的所有属性相等时才相等.

这些都是真的,但是怎么样？参考源明确显示了如何比较对象(ReferenceEquals)和"直接从对象派生"的类型不能具有此特殊行为.它不匹配的水煤浆Equals在ValueType任.

那怎么办？匿名类型如何覆盖Equals()并且GetHashCode()没有任何可见的覆盖？