我有一个类，内部只是一个整数数组。一旦构造，该数组永远不会改变。我想预先计算出一个好的哈希码，以便该类可以作为Dictionary中的键被非常高效地使用。数组长度少于30个项，通常情况下整数值在-1000到1000之间。
C# 整型数组的哈希码
23
- freddy smith
4
1字典的键是唯一的，如果你的对象存储一组值，并且键是基于它们计算出来的，那么就不能保证你可以为字典获取一个唯一的哈希键。 - Fadrian Sudaman
1@Fadrian：OP 不想计算密钥，而是哈希值。了解一下这是什么意思。哈希值是伪唯一的。 - H H
谢谢，Henk。我知道哈希值应该如何工作，当我发表评论时可能误读了问题的意图，你指出这一点真是太好了。 - Fadrian Sudaman
Fadrian，Henk是对的。我的意图不是获得唯一的代码，而是获得非常接近于它且可以快速计算的东西，这样我就不需要经常进行完整的Equals比较。我意识到，如果您相当了解所期望的数据，那么可能会做出更合适的选择，这也是我的问题所寻求的。下面很多答案都相当数学化，我需要时间来理解它们。 - freddy smith
9个回答
32
虽然不是非常聪明，但足以满足大多数实际需求：
编辑：由于Henk Holterman的评论而进行更改，感谢他的建议。
int hc = array.Length;
foreach (int val in array)
{
hc = unchecked(hc * 314159 + val);
}
如果您需要更先进的东西，请点击这里。
- Doc Brown
13
13看起来还好，但是 314159 可能有点太大了。像 17 或者 31 这样的数字也很好。并且，将
hc=unchecked(hc*SHIFTVAL+array[i]); 修改为与编译器设置无关的代码。 - H H1是的，可以用许多不同的方式来改进它，我已经点赞了你的评论。 - Doc Brown
4那又怎样？ - Doc Brown
2@chhenning 哈希冲突可能会发生，没有人声称这将是“哈希冲突安全”的。这就是覆盖
Equals 方法发挥作用的地方。据我所记，字典使用 Equals 方法来区分具有相同哈希值的对象（这就是为什么 Equals 方法不应该依赖于哈希本身）。 - Alisson Reinaldo Silva1@chhenning：或者，如果你更喜欢这样说：给定两个有限集合X和Y，其中X的基数大于Y，任何函数f:X->Y都必然是非单射的。这被称为“鸽巢原理”，我想你一定听说过它。 - Doc Brown
显示剩余8条评论
7
对于一组通常在-1000和1000之间的值，我可能会使用以下代码：
static int GetHashCode(int[] values)
{
int result = 0;
int shift = 0;
for (int i = 0; i < values.Length; i++)
{
shift = (shift + 11) % 21;
result ^= (values[i]+1024) << shift;
}
return result;
}
- BlueMonkMN
1
3我选择数字11是因为11比特是存储2048个不同值所必需的位数（-1000到+1000是2000，接近2048）。我选择数字21是因为32位整数减去11位等于21位。将左移21位将留下11位以包含从0到2048的一个值。 - BlueMonkMN
2
你也可以使用 Linq 方法：
var array = new int[10];
var hashCode = array.Aggregate(0, (a, v) =>
HashCode.Combine(a, v.GetHashCode()));
- Amir Mahdi Nassiri
2
您可以使用CRC32校验和。以下是代码：
您可以使用CRC32校验和。以下是代码：
[CLSCompliant(false)]
public class Crc32 {
uint[] table = new uint[256];
uint[] Table { get { return table; } }
public Crc32() {
MakeCrcTable();
}
void MakeCrcTable() {
for (uint n = 0; n < 256; n++) {
uint value = n;
for (int i = 0; i < 8; i++) {
if ((value & 1) != 0)
value = 0xedb88320 ^ (value >> 1);
else
value = value >> 1;
}
Table[n] = value;
}
}
public uint UpdateCrc(uint crc, byte[] buffer, int length) {
uint result = crc;
for (int n = 0; n < length; n++) {
result = Table[(result ^ buffer[n]) & 0xff] ^ (result >> 8);
}
return result;
}
public uint Calculate(Stream stream) {
long pos = stream.Position;
const int size = 0x32000;
byte[] buf = new byte[size];
int bytes = 0;
uint result = 0xffffffff;
do {
bytes = stream.Read(buf, 0, size);
result = UpdateCrc(result, buf, bytes);
}
while (bytes == size);
stream.Position = pos;
return ~result;
}
}
- osprey
3
5针对一个由约30个整数组成、范围在-1000到1000之间的数组来说，这个看起来过于复杂了。因为没有一个可以接受整数数组作为输入的函数，所以需要先将整数数组转换为字节数组或流。 - BlueMonkMN
将每个int转换为byte[]非常容易：
int value = 0;
byte[] bytes = BitConverter.GetBytes(value);
这些字节可以用于计算校验和，而不是从流中读取的字节。 - osprey
是的，但您忽略了一个事实，即您必须将整个数组转换为字节。这也很容易，但仍然会在代码复杂性和运行时方面产生一些显着的开销，相对于直接针对整数数组进行哈希的解决方案。 - BlueMonkMN
1
我正在这里使用它
var arrayHash = string.Join(string.Empty, array).GetHashCode();
如果数组中的元素发生了变化，您将得到一个新的哈希值。
- David Stania
0
任何CRC（甚至XOR）都可以。
- leppie
3
3异或运算永远不会超出 -/+ 1000 的窗口范围。 - H H
@Henk Holterman: 抱歉，我不太明白。如果值受限制，您仍将具有10位有效CRC。编辑：实际上，其余的位数取决于符号会翻转。 - leppie
4CRC是可行的，但有些过于复杂，简单地对数值进行异或操作（不需要移位）则不可行。 - H H
0
你可以采用不同的方法，为整数数组中的每个值使用递归字典。这样，你就可以让 .net 来执行原始类型哈希处理。
internal class DictionaryEntry<TKey, TValue>
{
public Dictionary<TKey, DictionaryEntry<TKey, TValue>> Children { get; private set; }
public TValue Value { get; private set; }
public bool HasValue { get; private set; }
public void SetValue(TValue value)
{
Value = value;
HasValue = true;
}
public DictionaryEntry()
{
Children = new Dictionary<TKey, DictionaryEntry<TKey, TValue>>();
}
}
internal class KeyStackDictionary<TKey, TValue>
{
// Helper dictionary to work with a stack of keys
// Usage:
// var dict = new KeyStackDictionary<int, string>();
// int[] keyStack = new int[] {23, 43, 54};
// dict.SetValue(keyStack, "foo");
// string value;
// if (dict.GetValue(keyStack, out value))
// {
// }
private DictionaryEntry<TKey, TValue> _dict;
public KeyStackDictionary()
{
_dict = new DictionaryEntry<TKey, TValue>();
}
public void SetValue(TKey[] keyStack, TValue value)
{
DictionaryEntry<TKey, TValue> dict = _dict;
for (int i = 0; i < keyStack.Length; i++)
{
TKey key = keyStack[i];
if (dict.Children.ContainsKey(key))
{
dict = dict.Children[key];
}
else
{
var child = new DictionaryEntry<TKey, TValue>();
dict.Children.Add(key, child);
dict = child;
}
if (i == keyStack.Length - 1)
{
dict.SetValue(value);
}
}
}
// returns false if the value is not found using the key stack
public bool GetValue(TKey[] keyStack, out TValue value)
{
DictionaryEntry<TKey, TValue> dict = _dict;
for (int i = 0; i < keyStack.Length; i++)
{
TKey key = keyStack[i];
if (dict.Children.ContainsKey(key))
{
dict = dict.Children[key];
}
else
{
break;
}
if (i == keyStack.Length - 1 && dict.HasValue)
{
value = dict.Value;
return true;
}
}
value = default(TValue);
return false;
}
}
- David
-2
我建议：
HashCode.Combine(array)
适用于.NET Core 2.1 / .NET Standard 2.1 / .NET 5及更高版本。
- Stephen Aggett
2
1这只是一个基于数组内存地址的哈希码，而不是基于数组内容的哈希码。 - Emil
这个答案的编辑队列已满，但是基于
HashCode.Add() 的正确解决方案在 https://dev59.com/aFIH5IYBdhLWcg3wfu1c 上给出。 - Todd West网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接