创建两个数字的哈希码

Question

我正在尝试为(a + b)C#中的复数类创建快速哈希码函数.

我反复看过这个a.GetHashcode()^b.GetHashCode()方法.但是,这将给予相同的哈希码(a,b)和(b,a).

是否有任何标准算法来执行此操作,.Net框架中是否有任何功能可以帮助您？

Answer 1

我为任意一组可散列项创建哈希码的常规方法:

int hash = 23;
hash = hash * 31 + item1Hash;
hash = hash * 31 + item2Hash;
hash = hash * 31 + item3Hash;
hash = hash * 31 + item4Hash;
hash = hash * 31 + item5Hash;
// etc

在你的情况下,item1Hash可能只是a,而且item2Hash可能只是b.

23和31的值相对不重要,只要它们是素数(或至少是互质).

显然仍会有碰撞,但你不会遇到以下常见的令人讨厌的问题:

hash(a, a) == hash(b, b)
hash(a, b) == hash(b, a)

如果你更了解真正的价值a和b可能的价值,你可能会做得更好,但这是一个很好的初始实现,很容易记住和实现.请注意,如果您有可能使用"检查算术溢出/下溢"来构建程序集,则应将其全部放在未经检查的块中.(此算法溢出很好.)

Answer 2

这是一种考虑到顺序的可能方法.(第二种方法被定义为扩展方法.)

public int GetHashCode()
{
    return a.GetHashcode() ^ b.GetHashcode().RotateLeft(16);
}

public static uint RotateLeft(this uint value, int count)
{
    return (value << count) | (value >> (32 - count))
}

看看Complex.NET 4.0 的类是如何做的肯定会很有趣.

Answer 3

一种标准方式是:

hashcode = 23
hashcode = (hashcode * 37) + v1
hashcode = (hashcode * 37) + v2

23和37是互质的,但你也可以使用其他数字.

Answer 4

那这个呢:

(a.GetHashcode() + b).GetHashcode()

给你一个不同的代码(a,b)和(b,a)加上它并不是那么花哨.

Answer 5

@JonSkeet提供了一个公平的通用算法,用于计算来自n个哈希码的哈希码,但假设您已经知道对象的哪些成员需要哈希,知道如何处理空成员,并省略n个任意项的实现.所以我们扩展他的答案:

1. 只有公共的,不可变的属性和字段才应该对对象哈希代码做出贡献.它们应该是公共的(或者与公众同构),因为我们应该能够依赖具有相同哈希码的相同可见表面的两个对象(暗示对象相等和哈希码相等之间的关系),并且它们应该是不可变的,因为它们应该是不可变的.一个对象的哈希代码在其生命周期中永远不会改变(从那以后你最终可能会在哈希表的错误插槽中找到一个对象!).
2. null成员应该作为常量哈希,例如0
3. @ JonSkeet的算法是一个教科书示例,用于应用通常称为fold(Aggregate在C#LINQ中)的函数式编程高阶函数,其中23是我们的种子并且<hash accumulator> * 31 + <current item hash>是我们的折叠函数:

在F#中

let computeHashCode items =
    items
    |> Seq.map (fun item -> if item = null then 0 else item.GetHashCode())
    |> Seq.fold (fun hash itemHash -> hash * 31 + itemHash) 23

在C#中

Func<IEnumerable<Object>, int> computeHashCode = items =>
    items
    .Select(item => item == null ? 0 : item.GetHashCode())
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);