创建两个数字的哈希码

我正在尝试为C＃中的复数类型(a + b)创建一个快速哈希码函数。创建两个数字的哈希码

我曾多次看到a.GetHashcode()^b.GetHashCode()方法。但是，这将给出(a,b)和(b,a)相同的散列码。

是否有任何标准算法来做到这一点，并在.Net框架中有帮助的任何功能？

2009-05-21 JDunkerley

http://stackoverflow.com/questions/682438/hash-function-providing-unique-uint-from-an-integer-coordinate-pair/682617#682617 – 2009-05-22 11:42:36

我对哈希的物品任意一组创建一个散列码的正常方式：

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的值是相对不重要的，只要它们是素数（或至少是coprime）。

显然仍然会有冲突，但你没有碰上正常讨厌的问题：

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

如果你知道更多关于什么a和b实际值可能是，你可以可能会做得更好，但这是一个很好的初始实现，很容易记住和实现。请注意，如果您有机会使用“检查算术溢出/下溢”构建程序集，您应该将其全部置于未经检查的块中。（溢出是罚款，这种算法）。

来源

2009-05-21 12:12:30

这个怎么样：

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

为您提供了不同的代码（A，B）和（B，A），再加上它不是真正的花哨。

来源

2009-05-21 12:09:54 Welbog

这并不总是正确的。对于Int32s，x.GetHashCode（）只返回x。因此（a.GetHasCode（）+ b）.GetHashCode（）只是a + b。 – hwiechers 2009-08-22 08:37:47

在a和b是Int32的情况下。 – hwiechers 2009-08-22 08:38:31

下面是一个考虑顺序的可能方法。（第二种方法被定义为扩展方法。）

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是怎么做的。

来源

2009-05-21 12:11:50 Noldorin

如果整数值偏斜，这是最好的答案，例如如果他们倾向于小方面，因为他们是自动生成数据库中的主键。对a.GetHashCoce（）和b.GetHashCode（）的调用不是必须的，因为它只会分别返回a和b的值（我相信这是当前的实现细节而不是记录的行为）。 – 2012-08-07 21:14:53

一个标准的方法是这样的：

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

23和37是互质，但可以使用其他数字也是如此。

来源

2009-05-21 12:12:55

所有这一切都取决于你想要达到的目标。如果散列意味着像Dictionary这样的散列结构，那么你必须要有平衡冲突率和散列速度。要完全没有碰撞地完成哈希将会更耗时。同样，最快的哈希算法会有更多的碰撞。找到完美的平衡是这里的关键。你也应该考虑你的有效散列可以有多大，如果散列应该是可逆的！如果你的复数的实部和虚部总是正的，那么Noldorin的方法给你提供了完美的哈希（不读碰撞）。如果你遇到罕见的碰撞，这将甚至对负数做出。但是我担心它可能产生的价值范围，对我的品味来说相当大。

如果你追求完美的哈希（出于一些学术/研究兴趣），即使对于负数，也可以工作，你可以在同一个线程中使用see this solution（以及其他一些解决方案）。在我的测试中，它比我见过的任何其他测试都快，并且利用空间更好。

来源

2012-12-15 08:31:50 nawfal

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

只有公共的，不可变的属性和字段应该有助于对象哈希码。它们应该是公开的（或者与公众同构），因为我们应该能够依靠具有相同散列码的相同可见表面的两个对象（暗示对象相等和散列码相等之间的关系），并且它们应该是不可变的，因为它们应该是不变的一个对象的哈希代码在其生命周期中绝不应该改变（因为那时你最终可能会在哈希表的错误槽中产生一个对象！）。
空成员应散列为常数，如0
@ JonSkeet的算法是用于将功能性编程高阶函数通常被称为（在C＃LINQ Aggregate）fold文本书例如，当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);

来源

2013-05-20 14:06:32

创建两个数字的哈希码

回答

相关问题