我正在使用一个哈希集，其中存储整数数组（32 位）。这意味着我需要一个算法来散列一个整数数组。我正在寻找一个 32 位整数（C# int）哈希。
我已经尝试并编辑了两个现有算法，您可以在底部看到四个版本，包括它们的基准。
我的问题如下：
1、你认为底层算法适合这个目的吗？
2. 是否有更好的算法可用于此目的？
节目信息
- 通常一个数组有
16 entries，整数是smaller than 10，尽管两者都必须支持更大的值。我可以说有机会发生的最大值是 200 个条目和值为 20 的整数。 - 我在呼吸优先搜索算法中使用 HashSet 来比较两个节点是否相同。http://en.wikipedia.org/wiki/Breadth-first_search。
- 对于这个特定的程序，我无法使用不安全的代码。
基准和代码
下面是我的基准测试和代码，在我的程序中从最差到最好的性能。
- Coordinates2D 是一个包含一个 int x 和一个 int y 的结构。
- 运行结束时 HashSet 中的总条目是
356525 - 我无法准确检索碰撞次数。给定的数字是对象实际比较且不相等的次数（相同的哈希，不同的对象）。但是，这在相同的对象之间会发生多次。由于程序是多线程的，因此该值每次执行都会有所不同。
- MurMurHash3 种子是
const uint seed = 144
MurMurHash3 使用直接从坐标检索的字节
代码等于https://gist.github.com/automatonic/3725443 使用以下代码检索字节数组：
int size = Marshal.SizeOf(typeof(Coordinates2D));
int length = carCoords.Length;
Byte[] bytes = new Byte[size * length];
for (int i = 0; i < length; ++i)
{
GCHandle pinStructure = GCHandle.Alloc(carCoords[i], GCHandleType.Pinned);
Marshal.Copy(pinStructure.AddrOfPinnedObject(), bytes, i*size, size);
pinStructure.Free();
}
// Hash the byte array
return MurMurHash3.Hash(new System.IO.MemoryStream(bytes));
由于复制，这是非常低效的。
- 性能： 40880ms
- 碰撞次数： < 84
MurMurHash3 使用从对象中的整数中检索到的字节
public static int Hash2(RushHourPathLengthNode.Coordinates2D[] coords)
{
const uint c1 = 0xcc9e2d51;
const uint c2 = 0x1b873593;
uint h1 = seed;
uint k1 = 0;
uint streamLength = (uint)coords.Length * 2;
for (int i = 0, l = coords.Length; i < l; ++i)
{
// Do it for X
byte[] chunk = BitConverter.GetBytes(coords[i].x);
/* Get four bytes from the input into an uint */
k1 = (uint)
(chunk[0]
| chunk[1] << 8
| chunk[2] << 16
| chunk[3] << 24);
/* bitmagic hash */
k1 *= c1;
k1 = rotl32(k1, 15);
k1 *= c2;
h1 ^= k1;
h1 = rotl32(h1, 13);
h1 = h1 * 5 + 0xe6546b64;
// Do it for y
chunk = BitConverter.GetBytes(coords[i].y);
/* Get four bytes from the input into an uint */
k1 = (uint)
(chunk[0]
| chunk[1] << 8
| chunk[2] << 16
| chunk[3] << 24);
/* bitmagic hash */
k1 *= c1;
k1 = rotl32(k1, 15);
k1 *= c2;
h1 ^= k1;
h1 = rotl32(h1, 13);
h1 = h1 * 5 + 0xe6546b64;
}
// finalization, magic chants to wrap it all up
h1 ^= streamLength;
h1 = fmix(h1);
unchecked //ignore overflow
{
return (int)h1;
}
}
现在复制消失了，这效率更高。
- 性能： 16640ms
- 碰撞次数： < 92
MurMurHash3 使用整数
public static int Hash(RushHourPathLengthNode.Coordinates2D[] coords)
{
const uint c1 = 0xcc9e2d51;
const uint c2 = 0x1b873593;
uint h1 = seed;
uint k1 = 0;
uint streamLength = (uint)coords.Length * 2;
for (int i = 0, l = coords.Length; i < l; ++i)
{
k1 = (uint)coords[i].x;
//bitmagic hash
k1 *= c1;
k1 = rotl32(k1, 15);
k1 *= c2;
h1 ^= k1;
h1 = rotl32(h1, 13);
h1 = h1 * 5 + 0xe6546b64;
k1 = (uint)coords[i].y;
//bitmagic hash
k1 *= c1;
k1 = rotl32(k1, 15);
k1 *= c2;
h1 ^= k1;
h1 = rotl32(h1, 13);
h1 = h1 * 5 + 0xe6546b64;
}
// finalization, magic chants to wrap it all up
h1 ^= streamLength;
h1 = fmix(h1);
unchecked //ignore overflow
{
return (int)h1;
}
}
- 性能： 13027ms
- 碰撞次数： < 95
使用整数加法乘法散列
int hash = 17;
for (int i = 0, l = carCoords.Length; i < l; ++i)
{
hash = hash * 31 + carCoords[i].x;
hash = hash * 31 + carCoords[i].y;
}
return hash;
- 性能： 4564ms
- 碰撞次数： < 44
如您所见，这个效率要高得多。它适用于任何素数。据我了解，没有科学证据证明这一点有效，我不太喜欢。
根据 Michal B. 的说法，更快的版本将使用位移。但是，测试表明这不是一个成功的哈希。该问题需要更长的时间才能运行（它没有在 5 分钟内完成）。移位可能很好，但似乎 31（质数）至关重要。
int hash = 17;
for (int i = 0, l = carCoords.Length; i < l; ++i)
{
hash = hash << 5 - carCoords[i].x;
hash = hash << 5 - carCoords[i].y;
}
return hash;