【原创】GetHashCode与Comparer相互调用关系

faunus

不多说了,先上代码:

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

[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

[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

结果如下：

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次!