在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。

对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?


当前回答

微软引领了几种哈希方法。。。

//for classes that contain a single int value
return this.value;

//for classes that contain multiple int value
return x ^ y;

//for classes that contain single number bigger than int    
return ((int)value ^ (int)(value >> 32)); 

//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();

//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode(); 

我可以猜测,对于多个大整数,您可以使用这个:

int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;

对于多类型也是如此:首先使用GetHashCode()将所有类型转换为int然后int值将被xor'ed,结果是您的哈希值。

对于那些使用哈希作为ID(我的意思是一个唯一的值)的人来说,哈希自然被限制在数字个数,我认为哈希算法是5个字节,至少是MD5。

您可以将多个值转换为哈希值,其中一些值是相同的,因此不要将其用作标识符。(也许有一天我会使用你的组件)

其他回答

如果我们的财产不超过8处(希望如此),这里还有另一种选择。

ValueTuple是一个结构,似乎有一个可靠的GetHashCode实现。

这意味着我们可以简单地这样做:

// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();

让我们来看看.NETCore当前对ValueTuple的GetHashCode的实现。

这来自ValueTuple:

    internal static int CombineHashCodes(int h1, int h2)
    {
        return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
    }

    internal static int CombineHashCodes(int h1, int h2, int h3)
    {
        return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
    }

这来自HashHelper:

    public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();

    public static int Combine(int h1, int h2)
    {
        unchecked
        {
            // RyuJIT optimizes this to use the ROL instruction
            // Related GitHub pull request: dotnet/coreclr#1830
            uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
            return ((int)rol5 + h1) ^ h2;
        }
    }

英语:

向左旋转(循环移位)h1 5个位置。将结果和h1相加。将结果与h2进行异或运算。首先对{static random seed,h1}执行上述操作。对于每个其他项目,对上一个结果和下一个项目(例如h2)执行操作。

如果能更多地了解这个ROL-5散列代码算法的财产,那就太好了。

遗憾的是,为我们自己的GetHashCode延迟ValueTuple可能不像我们希望的那样快。相关讨论中的这条评论说明了直接调用HashHelpers.Combine更具性能。另一方面,这是内部的,所以我们必须复制代码,牺牲了我们在这里获得的大部分。此外,我们将负责记住首先与随机种子结合。我不知道如果我们跳过这一步会有什么后果。

我通常会使用Josh Bloch精彩的有效Java中给出的实现。它很快,创建了一个很好的哈希,不太可能导致冲突。选择两个不同的素数,例如17和23,并执行以下操作:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

正如评论中所指出的,你可能会发现最好选择一个大素数来乘。很显然486187639很好。。。虽然我见过的大多数小数字的例子都倾向于使用素数,但至少有一些类似的算法经常使用非素数。例如,在后面的FNV示例中,我使用的数字显然很好,但初始值不是质数。(不过乘法常数是质数。我不知道这有多重要。)

这比XORing散列码的常见做法要好,主要原因有两个。假设我们有一个具有两个int字段的类型:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

顺便说一下,早期的算法是C#编译器当前用于匿名类型的算法。

这个页面提供了很多选项。我认为,在大多数情况下,上述内容“足够好”,而且非常容易记住并正确理解。FNV替代方案同样简单,但使用不同的常数和XOR代替ADD作为组合操作。它看起来像下面的代码,但正常的FNV算法对单个字节进行操作,因此这需要进行修改,以每个字节执行一次迭代,而不是每个32位哈希值。FNV也设计用于可变长度的数据,而我们在这里使用它的方式总是用于相同数量的字段值。对这个答案的评论表明,这里的代码实际上并不像上面的添加方法那样有效(在测试的示例案例中)。

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

请注意,需要注意的一点是,理想情况下,您应该防止在将其添加到依赖于哈希代码的集合后,对等式敏感(因此对哈希代码敏感)的状态发生变化。

根据文件:

可以为不可变引用类型重写GetHashCode。通常,对于可变引用类型,只有在以下情况下才应重写GetHashCode:您可以从不可变的字段计算哈希代码;或当可变对象包含在依赖其哈希代码的集合中时,可以确保该对象的哈希代码不会更改。

FNV文章的链接已断开,但这是互联网档案馆的一份副本:永恒的困惑-哈希的艺术

这是我的简单方法。我使用的是经典的生成器模式。它是类型安全的(无装箱/拆箱),并且与.NET 2.0兼容(无扩展方法等)。

它的用法如下:

public override int GetHashCode()
{
    HashBuilder b = new HashBuilder();
    b.AddItems(this.member1, this.member2, this.member3);
    return b.Result;
} 

这里是实际的生成器类:

internal class HashBuilder
{
    private const int Prime1 = 17;
    private const int Prime2 = 23;
    private int result = Prime1;

    public HashBuilder()
    {
    }

    public HashBuilder(int startHash)
    {
        this.result = startHash;
    }

    public int Result
    {
        get
        {
            return this.result;
        }
    }

    public void AddItem<T>(T item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

    public void AddItems<T1, T2>(T1 item1, T2 item2)
    {
        this.AddItem(item1);
        this.AddItem(item2);
    }

    public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
    }

    public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3, 
        T4 item4)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
    }

    public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3, 
        T4 item4, T5 item5)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
        this.AddItem(item5);
    }        

    public void AddItems<T>(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}

ReSharper用户可以使用ReSharper->Edit->generate Code->Equality Members生成GetHashCode、Equals等。

// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
    unchecked {
        int hashCode = Id;
        hashCode = (hashCode * 397) ^ IntMember;
        hashCode = (hashCode * 397) ^ OtherIntMember;
        hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
        // ...
        return hashCode;
    }
}

微软引领了几种哈希方法。。。

//for classes that contain a single int value
return this.value;

//for classes that contain multiple int value
return x ^ y;

//for classes that contain single number bigger than int    
return ((int)value ^ (int)(value >> 32)); 

//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();

//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode(); 

我可以猜测,对于多个大整数,您可以使用这个:

int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;

对于多类型也是如此:首先使用GetHashCode()将所有类型转换为int然后int值将被xor'ed,结果是您的哈希值。

对于那些使用哈希作为ID(我的意思是一个唯一的值)的人来说,哈希自然被限制在数字个数,我认为哈希算法是5个字节,至少是MD5。

您可以将多个值转换为哈希值,其中一些值是相同的,因此不要将其用作标识符。(也许有一天我会使用你的组件)