试图理解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]));
}

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

Answer 1

一个基于针孔原理的简单观察：

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

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

“有趣”的事实:由于生日悖论，在一个100.000人口的城市，你有超过50%的机会发生哈希碰撞。

Answer 2

以下是一个例子；

String s1 = new String("AMY");
String s2 = new String("MAY");

两个不同的对象，但是如果hashCode是用字符的ASCII代码计算的，那么对于五月和艾米，它将是相同的。

您应该基本理解散列的概念。

hashing an object means "finding a value (number) that can be reproduced by the very same instance again and again".

因为来自Object.hashCode()的哈希代码是int类型的，所以只能使用2^32不同的值。这就是为什么当两个不同的对象产生相同的hashCode时，将根据散列算法产生所谓的“冲突”。

为了更好地理解它们，你可以通过一系列的好例子；

1. PigeonHole，袜子采摘，头发计数
2. SoftBall团队
3. 生日问题。

希望这能有所帮助。

Answer 3

散列码是int，它有2^32个不同的值。现在我们来看看 String 类--它可以有无穷多个不同的值，因此我们可以得出结论，对于不同的字符串值，必须有相同的哈希码。

为了找出哈希冲突，你可以利用生日悖论。例如，对于双打，它可能是

  random gen = new Random();

  Dictionary<int, Double> dict = new Dictionary<int, Double>();

  // In general it'll take about 
  // 2 * sqrt(2^32) = 2 * 65536 = 131072 = 1e5 itterations
  // to find out a hash collision (two unequal values with the same hash)  
  while (true) {
    Double d = gen.NextDouble();
    int key = d.GetHashCode();

    if (dict.ContainsKey(key)) {
      Console.Write(d.ToString(Culture.InvariantCulture));
      Console.Write(".GetHashCode() == ");

      Console.Write(dict[key].ToString(Culture.InvariantCulture));
      Console.Write(".GetHashCode() == ");
      Console.Write(key.ToString(Culture.InvariantCulture));

      break;
    }

    dict.Add(key, d);
   }

在我的情况下

  0.540086061479564.GetHashCode() == 0.0337553788133689.GetHashCode() == -1350313817