c# - 试图理解 GetHashCode()

Question

我在 Microsoft 文档中找到了以下内容:

Two objects that are equal return hash codes that are equal. However, the reverse is not true: equal hash codes do not imply object equality, because different (unequal) objects can have identical hash code

我做了自己的测试来理解这个方法:

public static void HashMetod() 
{
    List<Cliente> listClientTest = new List<Cliente>
    {
        new Cliente { ID = 1, name = "Marcos", Phones = "2222"}
    };

    List<Empresa> CompanyList = new List<Empresa>
    {
        new Empresa { ID = 1, name = "NovaQuimica", Clients = listClientTest },
        new Empresa { ID = 1, name = "NovaQuimica", Clients = listClientTest }
    };

    CompanyList.Add(CompanyList[0]);

    foreach (var item in CompanyList)
    {
        Console.WriteLine("Hash code = {0}", item.GetHashCode());
    }

    Console.WriteLine("CompanyList[0].Equals(CompanyList[1]) = {0}", CompanyList[0].Equals(CompanyList[1]));
    Console.WriteLine("CompanyList[0].Equals(CompanyList[2]) = {0}", CompanyList[0].Equals(CompanyList[2]));
}

我的问题是:两个 Differents 对象如何返回相同的 HashCode？我相信如果两个对象返回相同的值，那么它们就是 Equals(这就是我的方法所显示的)。执行我的方法并检查它。

Answer 1

基于 pigeonhole principle 的简单观察:

1. GetHashCode 返回一个 int - 一个 32 位整数。
2. 有4.294.967.296个32位整数；
3. 只考虑大写英文字母，有 141.167.095.653.376 个十字母单词。如果我们包括大写字母和小写字母，那么我们有 144.555.105.949.057.024 种组合。
4. 由于对象的数量多于可用的哈希码，一些(不同的)对象必须具有相同的哈希码。

另一个更真实的例子是，如果你想给地球上的每个人一个哈希码，你就会发生冲突，因为我们有比 32 位整数更多的人。

“有趣”的事实:因为 birthday paradox ，在一个拥有 100.000 人的城市中，哈希冲突的可能性超过 50%。