3

我在 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？我相信如果两个对象返回相同的值，它们就是 Equals（这就是我的方法所显示的）。执行我的方法并检查一下。

4

6 回答 6

9

基于鸽巢原理的简单观察：

  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% 的概率发生哈希冲突。

于 2013-08-16T13:09:35.543 回答
4

这是一个例子；

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

两个不同的 Objects，但是如果hashCode 是用字符的 ASCII 码计算的，那么MAY 和 AMY将是相同的。

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

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. 垒球队
  3. 生日问题。

希望这可以帮助。

于 2013-08-16T13:04:28.117 回答
1

哈希码是int，它有 2^32 个不同的值。现在让我们来看看String类——它可以有无数个不同的值，所以我们可以得出结论，不同的 String 值必须有相同的哈希码。

要找出哈希冲突，您可以利用生日悖论。例如，对于 Doubles，它可能是

  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
于 2013-08-16T13:06:57.910 回答
1

您可以在 wiki 页面上阅读有关散列的信息。但是散列的全部意义在于将值转换为索引，这是通过散列函数完成的。散列函数可能会有所不同，但几乎所有函数都以将索引值限制在最大值内的 mod 结尾，因此可以将其放入数组中。对于每个 mod n，有无限数量的数字会产生相同的索引（IE 5 mod 2、7 mod 2 等）。

于 2013-08-16T13:07:43.700 回答
1

您可能只需要阅读一般的散列函数以确保您理解这一点。来自维基百科：

散列函数主要用于生成固定长度的输出数据，作为对原始数据的缩短引用

所以基本上你知道你正在接受一个大的（可能是无限的）可能性，并试图将它们放入一个更小、更易于管理的可能性中。由于集合的两种不同大小，您可以保证在两个不同的源对象及其哈希之间发生冲突。也就是说，一个好的哈希函数尽可能地减少这些冲突。

于 2013-08-16T13:08:56.873 回答
0

哈希码的目的是允许接收对象的代码快速识别对象不可能等于的事物。如果一个集合类被要求存储许多对象，它只知道如何测试它们是否相等，然后被赋予另一个对象并被询问它是否与它存储的任何对象匹配，则集合必须调用Equals在集合中的每个对象上。另一方面，如果集合可以调用GetHashCode添加到集合中的每个项目，以及它正在寻找的项目，并且如果集合中 99% 的对象报告了与哈希码不匹配的哈希码如果要查找的项目，则只需检查其哈希码匹配的 1% 的对象。

两个项目的哈希码匹配的事实不会比不检查它们的哈希码更快地比较这两个项目，但是项目的哈希码不匹配的事实将消除进一步检查它们的需要. 在项目不匹配的可能性远大于匹配的情况下，哈希码可以加速不匹配的情况，有时可以加快许多数量级。

于 2013-08-16T20:44:54.213 回答