guid的哈希接近完美，可以将字符串作为字典键

本文关键字：字符串 字典 哈希 接近 完美 guid | 更新日期: 2023-09-27 17:58:39

我试图解决的问题：使用guid字符串作为Dictionary（string，someObject）的键，并且我希望在键上进行完美的哈希。。。

不确定我是否错过了什么。。。当我用字典构造函数只传递大小分配来运行下面的测试时，每次运行都会发生+-10次冲突。当我传入IEqualityComparer，只是在字符串上调用gethashcode时，我的测试通过得很好！在某些情况下使用x=10次迭代进行多次运行，y高达一百万次！我以为字典在调整哈希函数，尤其是在处理字符串时？我的机器上没有反射器：（所以我今晚不能检查……如果你对交替的字典初始化进行评论，你会看到……在我的i7上测试运行得相对较快。

            [TestMethod]
    public void NearPerfectHashingForGuidStrings()
    {
        int y = 100000;
        int collisions = 0;
        //Dictionary<string, string> list = new Dictionary<string, string>(y, new GuidStringHashing());
        Dictionary<string, string> list = new Dictionary<string, string>(y);
        for (int x = 0; x < 5; x++)
        {
            Enumerable.Range(1, y).ToList().ForEach((h) =>
            {
                list[Guid.NewGuid().ToString()] = h.ToString();
            });
            var hashDuplicates = list.Keys.GroupBy(h => h.GetHashCode())
                .Where(group => group.Count() > 1)
                .Select(group => group.Key).ToList();
            hashDuplicates.ToList().ForEach(v => Debug.WriteLine( x +  "--- " + v));
            collisions += hashDuplicates.Count();
            list.Clear();
        }
        Assert.AreEqual(0, collisions);
    }
        public class GuidStringHashing : IEqualityComparer<string>
{
    public bool Equals(string x, string y)
    {
        return GetHashCode(x) == GetHashCode(y);
    }
    public int GetHashCode(string obj)
    {
        return obj.GetHashCode();
    }
}

guid的哈希接近完美，可以将字符串作为字典键

您的测试已中断。

由于相等比较器错误地报告恰好具有相同哈希的两个不同GUID相等，因此字典从不首先存储冲突。

由于鸽子洞原理，根本不可能为超过232的项创建32位完美哈希。

这是不可能的。对于一组未知的密钥，您需要一个完美的哈希函数。您可以为特定的密钥集创建完美的哈希函数。你不可能创建一个完美的哈希函数来处理所有的密钥集。

原因是"两个耶稣原则"，正如Mark Knopfler所说："两个人说他们是耶稣，其中一个肯定错了。"（更广为人知的是"鸽子洞原则"）

完美的哈希代码是什么意思？

您的代码有些混乱，尤其是因为您发布了一个测试方法未使用的类GuidStringHashing。

但您的代码表明，当您生成100000个GUID，将它们全部转换为字符串，然后获取字符串的哈希代码时，并非所有哈希代码都是不同的。当有超过40亿个整数可供选择，而您只生成100000个字符串时，这可能会令人惊讶。

您将GetHashCode()用于一般字符串，但您的字符串并不太一般，它们都类似于

"2315c2a7-7d29-42b1-9696-fe6a9dd72ffd"

所以也许你的散列码不是最优的。最好将字符串h解析回GUID，并使用其哈希代码，如(new Guid(h)).GetHashCode()中所示。

然而，这仍然会导致100000个GUID发生冲突。我想你看到的只是生日悖论。

试试这个更简单的代码。这里我在GUID上使用GetHashCode()，所以我们认为整数是随机的：

        var set = new HashSet<int>();
        for (int i = 1; true; ++i)
        {
            if (!set.Add(Guid.NewGuid().GetHashCode()))
                Console.WriteLine("Collision, i is: " + i);
        }

我们看到（通过多次运行上面的代码），冲突几乎总是在计算出100000个哈希代码之前发生。

相关文章：