0

我要解决的问题：使用 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();
    }
}
4

3 回答 3

2

你的测试坏了。

因为您的相等比较器错误地报告恰好具有相同散列的两个不同 GUID 相等，所以您的字典从一开始就不会存储冲突。

由于鸽巢原理，根本不可能为超过 2个 32项创建 32 位完美哈希。

于 2013-02-10T20:05:00.913 回答
0

不可能。你想要一个完美的散列函数来处理一组未知的键。您可以为特定的键集创建完美的散列函数。您无法创建一个适用于所有键集的完美哈希函数。

原因是“两个耶稣原则”，正如 Mark Knopfler 所说的那样：“两个人说他们是耶稣，其中一个人肯定是错的。” （它更广为人知的是“鸽巢原理”）

于 2013-02-10T21:06:10.537 回答
0

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

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

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

您正在使用GetHashCode()通用字符串，但您的字符串不太通用，它们都类似于

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

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

但是，这仍然会与 100,000 个 GUID 发生冲突。我想你看到的只是生日悖论。

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

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

我们看到（通过多次运行上述代码）碰撞几乎总是在计算出 100,000 个哈希码之前发生。

于 2013-02-10T22:21:21.897 回答