创build两个数字的哈希码

我正在尝试在C#中为复数类(a + b)创build一个快速哈希码函数。

我已经多次看到了a.GetHashcode()^b.GetHashCode()方法。 但是这会给出(a,b)(b,a)相同的哈希码。

有没有任何标准的algorithm来做到这一点,并在.Net框架有帮助的任何function?

我为任意可哈希项目创build哈希码的一般方法:

 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的值是相对不重要的,只要它们是素数(或至less是互质)。

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

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

如果你更了解ab的真实价值可能会更好,但是这是一个很好的初始实现,很容易记住和实现。 请注意,如果有机会用“检查算术溢出/下溢”来构build程序集,则应该将其全部置于未经检查的块中。 (这个algorithm溢出很好。)

这是考虑到订单的一种可能的方法。 (第二种方法被定义为扩展方法。)

 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)) } 

看看.NET 4.0的Complex类是怎么做的,肯定会很有趣。

一个标准的方法是:

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

23和37是相互矛盾的,但是你也可以使用其他的数字。

那这个呢:

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

(a,b)和(b,a)给你一个不同的代码,加上它不是那么奇特。

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

  1. 只有公共的,不可变的属性和字段应该有助于对象散列码。 它们应该是公开的(或者与公众同构),因为我们应该能够指望具有相同散列码的相同可见表面上的两个对象(暗示对象相等和散列码相等之间的关系),并且它们应该是不可变的一个对象的哈希代码不应该改变其生命周期(因为那样你可能会在一个哈希表的错误槽中结束一个对象!)。
  2. 空成员应该散列为一个常数,如0
  3. @ JonSkeet的algorithm是一个应用通常被称为fold (C#LINQ中的Aggregate )的函数式编程高级函数的文本示例,其中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); 

所有这一切取决于你想要达到的目标。 如果散列是用于像Dictionary这样的散列结构,那么你必须平衡散列的冲突率和速度 。 要有一个完美的哈希没有碰撞,将是更耗时。 同样,最快的哈希algorithm会有更多的碰撞。 寻找完美的平衡是这里的关键。 你也应该考虑你的有效散列可以有多大,如果散列应该是可逆的 ! 如果你的复数的实部和虚部始终是正的,那么Noldorin的方法给你提供了完美的哈希(不读取碰撞)。 如果你遇到罕见的碰撞,这将甚至为负数。 但是我担心它可以产生的价值范围,对我来说是相当大的。

如果你完成了一些完美的哈希(出于一些学术/研究兴趣),即使对于负数,也可以工作,你可以看到这个解决scheme (和一系列其他解决scheme在同一个线程中)。 在我的testing中,它比我见过的其他任何一个都更快,更利用空间。