我在C#中有一个结构:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| public struct UserInfo
{
public string str1
{
get;
set;
}
public string str2
{
get;
set;
}
} |
唯一的规则是UserInfo(str1="AA", str2="BB").Equals(UserInfo(str1="BB", str2="AA"))
如何重写此结构的GetHashCode函数?
MSDN:
哈希函数必须具有以下属性:
-
If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.
-
The GetHashCode method for an object must consistently return the same hash code as long as there is no modification to the object state that determines the return value of the object's Equals method. Note that this is true only for the current execution of an application, and that a different hash code can be returned if the application is run again.
-
For the best performance, a hash function must generate a random distribution for all input.
考虑到正确的方法是:
1
| return str1.GetHashCode() ^ str2.GetHashCode() |
^可以用其他交换运算代替
请参阅乔恩·斯基特(Jon Skeet)的答案-像^这样的二进制操作不好,它们经常会产生冲突哈希!
1 2 3 4 5 6 7 8
| public override int GetHashCode()
{
unchecked
{
return (str1 ?? String.Empty).GetHashCode() +
(str2 ?? String.Empty).GetHashCode();
}
} |
使用'+'运算符可能比使用'^'更好,因为尽管您明确希望('AA','BB')和('BB','AA')相同,但您可能不希望( 'AA','AA')和('BB','BB')相同(或与此完全相同的对)。
此解决方案未完全遵循"尽可能快"的规则,因为在为null的情况下,它将对空字符串执行" GetHashCode()",而不是立即返回已知常量,但是即使没有显式测量,我也愿意除非您预期会有很多空值,否则可能会造成很大的差异,以至于您无法担心差异。
通常,生成类的哈希码的一种简单方法是对可以参与生成哈希码的所有数据字段进行XOR(小心检查其他人指出的null)。这也满足(人工?)要求,即UserInfo(" AA"," BB")和UserInfo(" BB"," AA")的哈希码相同。
如果可以对类的使用做出假设,则可以改善哈希函数。例如,如果str1和str2通常相同,那么XOR可能不是一个好选择。但是,如果str1和str2分别代表名字和姓氏,那么XOR可能是一个不错的选择。
尽管这显然并不意味着要成为现实世界中的示例,但值得指出的是:
-这可能是使用结构的一个不好的例子:结构通常应该具有值语义,在这里似乎不是这种情况。
-使用带有setter的属性来生成哈希码也很麻烦。
一种简单的通用方法是:
1
| return string.Format("{0}/{1}", str1, str2).GetHashCode(); |
除非您有严格的性能要求,否则这是我能想到的最简单的方法,并且在需要组合键时经常使用此方法。它可以很好地处理null情况,并且不会引起(m)任何哈希冲突(通常)。如果您希望字符串中包含" /",则只需选择一个您不需要的分隔符即可。
ReSharper建议遵循以下原则:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public int GetHashCode()
{
unchecked
{
int hashCode;
// String properties
hashCode = (hashCode * 397) ^ (str1!= null ? str1.GetHashCode() : 0);
hashCode = (hashCode * 397) ^ (str2!= null ? str1.GetHashCode() : 0);
// int properties
hashCode = (hashCode * 397) ^ intProperty;
return hashCode;
}
} |
397是足够大的素数,足以导致结果变量溢出并在某种程度上混合哈希的位,从而提供更好的哈希码分布。否则,在397中没有什么特别之处可以将其与相同大小的其他素数区分开。
1 2 3 4 5 6 7
| public override int GetHashCode()
{
unchecked
{
return(str1 != null ? str1.GetHashCode() : 0) ^ (str2 != null ? str2.GetHashCode() : 0);
}
} |
是的,正如Gary Shutler指出的那样:
1
| return str1.GetHashCode() + str2.GetHashCode(); |
会溢出。您可以尝试按Artem的建议进行强制转换,也可以将语句放在unchecked关键字中:
1
| return unchecked(str1.GetHashCode() + str2.GetHashCode()); |
试试这个:
1
| (((long)str1.GetHashCode()) + ((long)str2.GetHashCode())).GetHashCode() |
GetHashCode的结果应该是:
尽可能快地。
尽可能独特。
牢记这些,我将采用以下方式:
1 2 3 4 5 6 7 8 9 10
| if (str1 == null)
if (str2 == null)
return 0;
else
return str2.GetHashCode();
else
if (str2 == null)
return str1.GetHashCode();
else
return ((ulong)str1.GetHashCode() | ((ulong)str2.GetHashCode() << 32)).GetHashCode(); |
编辑:忘记了空值。代码固定。
对它们进行排序,然后将它们串联:
1 2
| return ((str1.CompareTo(str2) < 1) ? str1 + str2 : str2 + str1)
.GetHashCode(); |
也许像str1.GetHashCode()+ str2.GetHashCode()一样?或(str1.GetHashCode()+ str2.GetHashCode())/ 2?这样一来,无论str1和str2是否被交换,它都是相同的。
许多可能性。例如
return str1.GetHashCode() ^ str1.GetHashCode()
太复杂了,忘记了空值等。它用于存储分区之类的东西,因此您可以摆脱诸如
1 2 3 4 5 6 7 8
| if (null != str1) {
return str1.GetHashCode();
}
if (null != str2) {
return str2.GetHashCode();
}
//Not sure what you would put here, some constant value will do
return 0; |
假设str1在很大比例的实例中不太可能是常见的,这是有偏见的。