散列整数数组

Question

我正在使用哈希集,其中我存储整数数组(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;

Answer 1

您是否考虑过使用空间填充曲线来生成哈希？这将最大限度地减少（或消除）所选分辨率（maxX、maxY）的冲突

这是使用此方法的两个 SO 问题及其答案。

1. 将 N 维值映射到希尔伯特曲线上的点
2. 计算希尔伯特 R 树中使用的点的希尔伯特值？

希望这可以帮助！