c# - 对于顺序不改变值的整数列表的良好哈希函数

Question

给定一组整数，一个“功能组”，是否有更好的方法来获取整数的 GetHashCode，其中数字的位置不影响哈希？

void Main()
{
    int[] ints = { 10001, 10002, 10003, 10004, 10005 };

    int hash = GetHashCode(ints);

    Console.WriteLine("hash={0}", hash);
}

int GetHashCode(IEnumerable<int> integers)
{
    IEnumerator<int> intEnum = integers.GetEnumerator();

    if(intEnum.MoveNext()==false) return 0;

    int hash = 0;
    unchecked {
        hash = intEnum.Current.GetHashCode();
        for(;intEnum.MoveNext()==true;)
            hash = 31 * hash + intEnum.Current.GetHashCode();
    }

    return hash;
}

输出为:hash=954101523如果我交换 10003 和 10002，我得到:hash=954130353

除了在获取哈希之前对列表进行排序之外，是否有更好的替代方法，如果列表位置发生变化，则不会发生变化？

整数列表基本上代表了一组作为“功能组”的记录ID，所以“功能组”才是真正的关键，而不是真正依赖于顺序

Answer 1

用一个好的单值哈希函数加法

由于 Hash Function Prospector，一个好的单值哈希函数在 C 中有一个公共(public)域实现:

// exact bias: 0.020888578919738908
uint32_t
triple32(uint32_t x)
{
    x ^= x >> 17;
    x *= UINT32_C(0xed5ad4bb);
    x ^= x >> 11;
    x *= UINT32_C(0xac4c1b51);
    x ^= x >> 15;
    x *= UINT32_C(0x31848bab);
    x ^= x >> 14;
    return x;
}

您可以将其转换为 C#，将其应用于每个值，然后将所有散列结果相加。加法完全满足您的“顺序无关紧要”标准，因为顺序与加法无关，您仍然会得到相同的结果。上面的单值哈希函数满足了你对一个像样的哈希函数的渴望。

实现

下面实现了上面的想法(通过测试重新排列来显示它给出了相同的哈希值):

using System;
using System.Collections.Generic;

public class Test
{
    static void Main()
    {
        int[] ints = { 10001, 10002, 10003, 10004, 10005 };
        int hash = GetHashCode(ints);
        int[] reorderedInts = { 10004, 10002, 10005, 10001, 10003 };
        int reorderedHash = GetHashCode(reorderedInts);

        Console.WriteLine("hash          == {0}", hash);
        Console.WriteLine("hashReordered == {0}", reorderedHash);
    }

    static int GetHashCode(IEnumerable<int> integers)
    {
        int hash = 0;

        foreach(int integer in integers)
        {
            int x = integer;

            x ^= x >> 17;
            x *= 830770091;   // 0xed5ad4bb
            x ^= x >> 11;
            x *= -1404298415; // 0xac4c1b51
            x ^= x >> 15;
            x *= 830770091;   // 0x31848bab
            x ^= x >> 14;

            hash += x;
        }

        return hash;
    }
}

这produces the output :

hash          == -2145263134
hashReordered == -2145263134