Office中国论坛/Access中国论坛

标题: 【原创】GetHashCode与Comparer相互调用关系 [打印本页]
作者: faunus    时间: 2014-2-24 11:17
标题: 【原创】GetHashCode与Comparer相互调用关系
本帖最后由 faunus 于 2014-2-24 11:18 编辑

不多说了,先上代码:




  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5. public class Comparer : IEqualityComparer<int>
  6. {
  7.     public int countEquals = 0;
  8.     public int countGetHashCode = 0;
  9.     public bool Equals(int x, int y)
  10.     {
  11.         countEquals++;
  12.         Console.WriteLine("   ->Equals:{0:00},{1:00}", x, y);
  13.         return x == y;
  14.     }
  15.     public int GetHashCode(int x)
  16.     {
  17.         countGetHashCode++;
  18.         Console.WriteLine("X:{0:00},GetHashCode:{1:00}", x, x % 7);
  19.         return x % 7;
  20.         return countGetHashCode;
  21.         return 0x7FFFFFFF;
  22.     }
  23. }
  24. class TestA
  25. {
  26.     static void Main(string[] args)
  27.     {
  28.         List<int> list = new List<int> { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 7, 14, 21, 28, 35 };
  29.         //List<int> list = new List<int> { 1, 4, 5, 2, 4, 10, 3, 4, 15 };//用于证明调用顺序
  30.         Comparer comparer = new Comparer();
  31.         int count = list.Distinct(comparer).Count();
  32.         Console.WriteLine("共" + count + "条不重复数据");
  33.         Console.WriteLine("GetHashCode:调用{0}次,Equals:调用:{1}次!", comparer.countGetHashCode, comparer.countEquals);
  34.         Console.ReadKey();
  35.     }
  36. }
复制代码



作者: faunus    时间: 2014-2-24 11:17

[size=14.399999618530273px]结果如下：

X:01,GetHashCode:01
X:02,GetHashCode:02
X:03,GetHashCode:03
X:04,GetHashCode:04
X:05,GetHashCode:05
X:06,GetHashCode:06
X:06,GetHashCode:06
   ->Equals:06,06
X:06,GetHashCode:06
   ->Equals:06,06
X:06,GetHashCode:06
   ->Equals:06,06
X:06,GetHashCode:06
   ->Equals:06,06
X:07,GetHashCode:00
X:14,GetHashCode:00
   ->Equals:07,14
X:21,GetHashCode:00
   ->Equals:14,21
   ->Equals:07,21
X:28,GetHashCode:00
   ->Equals:21,28
   ->Equals:14,28
   ->Equals:07,28
X:35,GetHashCode:00
   ->Equals:28,35
   ->Equals:21,35
   ->Equals:14,35
   ->Equals:07,35
共11条不重复数据
GetHashCode:调用15次,Equals:调用:14次!

[size=14.399999618530273px]总结:
[1]分为三种情况
A:Hash码不同,值不同.
GetHashCode执行1次,Equals未调用.
B:Hash码相同,值相同.
GetHashCode执行1次,Equals调用0次(首个)或1次(余下).
C:Hash码相同,值不同.
GetHashCode执行1次,Equals调用0次(首个)1次(第2)....n-1次(第n)
C:Hash码不同,值相同.
不允许存在这种情况

[2]GetHashCode的执行效率
完全散列:O (1)
完全不散列:O (n*n)

[3]GetHashCode自动调用Equals
这又是一个编译器魔法,
GetHashCode是在冲突的情况下才去调用Equals
如果GetHashCode设计的足够好,可以极大提高查询效率.

[4]GetHashCode的正确性保障
-----------正确情况--------------
GetHashCode相同,Equals必相同(重码)
GetHashCode不同,Equals可相同(不充分散列,效率低)
GetHashCode不同,Equals不相同(充分散列)
-----------错误情况--------------
GetHashCode相同,Equals不相同(导致不可预料的错误)


作者: faunus    时间: 2014-2-24 11:17
[size=14.399999618530273px]其它一些方法的影响:
[size=14.399999618530273px]

[size=14.399999618530273px]
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5. public class Comparer : IEqualityComparer<int>
  6. {
  7.     public int countEquals = 0;
  8.     public int countGetHashCode = 0;
  9.     public bool Equals(int x, int y)
  10.     {
  11.         countEquals++;
  12.         Console.Write("->Equals:{0:00},{1:00}", x, y);
  13.         return x == y;
  14.     }
  15.     public int GetHashCode(int x)
  16.     {
  17.         countGetHashCode++;
  18.         Console.WriteLine();
  19.         Console.Write("X:{0:00},GetHashCode:{1:00}", x, x % 7);
  20.         return x % 7;
  21.     }
  22. }
  23. class TestA
  24. {
  25.     static void Main(string[] args)
  26.     {
  27.         Comparer comparer = new Comparer();
  28.         Dictionary<int, int> dic = new Dictionary<int, int>(comparer)
  29.         {
  30.             { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 }, { 5, 1 },
  31.           //{ 6, 1 }, { 6, 1 }, { 6, 1 }, { 6, 1 }, { 6, 1 },
  32.             { 7, 1 }, { 14, 1 }, { 21, 1 }, { 28, 1 }, { 35, 1 }
  33.         };
  34.         Console.WriteLine();
  35.         Console.WriteLine();
  36.         Console.Write("dic.Add(99, 1);");
  37.         dic.Add(99, 1);
  38.         Console.WriteLine();
  39.         Console.Write("dic.ContainsKey(99);");
  40.         dic.ContainsKey(99);
  41.         Console.WriteLine();
  42.         Console.Write("dic.ContainsKey(98);");
  43.         dic.ContainsKey(98);
  44.         Console.WriteLine();
  45.         Console.Write("dic.ContainsValue(1);");
  46.         dic.ContainsValue(1);
  47.         Console.WriteLine();
  48.         Console.Write("dic.Remove(35);");
  49.         dic.Remove(35);
  50.         int val;
  51.         Console.WriteLine();
  52.         Console.Write("dic.TryGetValue(97, out val);");
  53.         dic.TryGetValue(97, out val);
  54.         Console.WriteLine();
  55.         Console.Write("dic.TryGetValue(97, out val);");
  56.         dic.TryGetValue(99, out val);
  57.         Console.WriteLine();
  58.         Console.WriteLine();
  59.         int count = dic.Distinct().Count();
  60.         Console.WriteLine("共" + count + "条不重复数据");
  61.         Console.WriteLine("GetHashCode:调用{0}次,Equals:调用:{1}次!", comparer.countGetHashCode, comparer.countEquals);
  62.         Console.ReadKey();
  63.     }
  64. }
复制代码



作者: faunus    时间: 2014-2-24 11:18
结果如下：

X:01,GetHashCode:01

X:02,GetHashCode:02

X:03,GetHashCode:03

X:04,GetHashCode:04

X:05,GetHashCode:05

X:07,GetHashCode:00

X:14,GetHashCode:00->Equals:07,14

X:21,GetHashCode:00->Equals:14,21->Equals:07,21

X:28,GetHashCode:00->Equals:21,28->Equals:14,28->Equals:07,28

X:35,GetHashCode:00->Equals:28,35->Equals:21,35->Equals:14,35->Equals:07,35



dic.Add(99, 1);

X:99,GetHashCode:01->Equals:01,99

dic.ContainsKey(99);

X:99,GetHashCode:01->Equals:99,99

dic.ContainsKey(98);

X:98,GetHashCode:00->Equals:35,98->Equals:28,98->Equals:21,98->Equals:14,98->Equals:07,98

dic.ContainsValue(1);

dic.Remove(35);

X:35,GetHashCode:00->Equals:35,35

dic.TryGetValue(97, out val);

X:97,GetHashCode:06

dic.TryGetValue(97, out val);

X:99,GetHashCode:01->Equals:99,99



共10条不重复数据

GetHashCode:调用16次,Equals:调用:19次!



欢迎光临 Office中国论坛/Access中国论坛 (http://www.office-cn.net/) Powered by Discuz! X3.3