c# - 哈希整数数组

Question

我正在使用一个散列集，我在其中存储整数数组(32 位)。这意味着我需要一种算法来散列整数数组。我正在寻找 32 位整数 (C# int) 哈希。

我尝试并编辑了两个现有算法，您可以在底部看到它的四个版本，包括它们的基准。

我的问题如下:

1.您认为底层算法适合这个目的吗？

2。是否有更好的算法可用于此目的？

节目信息

• 通常一个数组有 16 个条目，整数小于 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));

由于复制，这是非常低效的。

• 性能: 40880 毫秒
• 碰撞: < 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;
    }
}

现在复制消失了，效率更高了。

• 性能:16640 毫秒
• 碰撞: < 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;
    }
}

• 性能:13027 毫秒
• 碰撞: < 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;

• 性能: 4564 毫秒
• 碰撞: < 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;

Answer 1

最后我采用了最后一种算法。

int hash = 17;
for (int i = 0, l = carCoords.Length; i < l; ++i)
{
    hash = hash * 19 + carCoords[i].x;
    hash = hash * 19 + carCoords[i].y;
}
return hash;

这计算起来非常快，而且对于我使用的(小)数字，哈希非常棒。

如果您要使用它，请确保您使用的数字是质数。因此，您不能使用移位来优化它。