HashTable 과 HashSet 의 유형 함정

이 함정 의 원인 은 이 렇 습 니 다. 저 는 지금 수백 만 개의 문자열 이 있 습 니 다. 저 는 TopK 알고리즘 으로 횟수 가 많은 100 개의 문자열 을 통계 하려 고 합 니 다.
우선 나 는 모든 문자열 이 나타 나 는 횟수 를 Hashtable 로 집계 했다.
그리고 나 서 나 는 이 문자열 의 쓸모없는 단 어 를 사전 으로 걸 러 내야 한 다 는 것 을 알 게 되 었 다. 그래서 나 는 또 하나의 HashSet 를 통계 사전 으로 정의 했다.
나의 최초의 코드 는 다음 과 같다.

 1     Stopwatch st = new Stopwatch();//   

 2             Hashtable queryTable = TopK.GetHashtable();//  HashTable

 3             HashSet<string> test = new HashSet<string>();

 4             string path = "dic.txt";

 5             if (File.Exists(path))

 6             {

 7 

 8                 using (StreamReader sr = new StreamReader(path, System.Text.Encoding.Default))

 9                 {

10                     string s = string.Empty;

11                     while (!string.IsNullOrEmpty(s = sr.ReadLine()))

12                     {

13                         test.Add(s);

14                     }

15                 }

16             }//      

17             Hashtable queryTable2 = new Hashtable();

18             List<string> teststring = new List<string>();

19             var aa = teststring[0];

20             foreach (var key in queryTable.Keys)// Hashtable  key    

21             {

22 

23                 if (!test.Contains(key))

24                 {

25                     queryTable2.Add(key, queryTable[key]);

26                 }

27              

28             }

29             st.Stop();

30             Console.WriteLine(st.ElapsedMilliseconds);

31             Console.Read();

한눈 에 보기에 이 코드 는 아무런 오류 가 없 었 다. (HashTable 에는 120 여 만 개의 문자열 이 있 고 사전 에는 11 만 개의 문자열 이 있다.)
그런데 내 가 운행 한 후에 오 랜 만 에 결과 가 나 오지 않 았 다. 마침내 콘 솔 에서 2400000 을 수출 했 는데 2400 초 를 운행 했다!
곰 곰 이 생각해 본 후에 먼저 사전 을 불 러 오 는 데 시간 이 걸 릴 수 없 으 며, 유일 하 게 시간 이 걸 릴 수 있 는 것 은 바로 이 문장 이다.

1    foreach (var key in queryTable.Keys)// Hashtable  key    

2             {

3 

4                 if (!test.Contains(key))

5                 {

6                     queryTable2.Add(key, queryTable[key]);

7                 }

8              

9             }

test 는 HashSet 형식 입 니 다. 검색, 즉 contains 방법의 시간 복잡 도 는 O (1) 여야 합 니 다. 그렇게 오래 걸 리 지 말 아야 합 니 다. var 가 정의 한 key, 포장 / 분해 로 인 한 것 입 니까?
그리고 나 서 나 는 var 를 string 으로 바 꾸 었 다.

1       foreach (string key in queryTable.Keys)// Hashtable  key    

2             {

3 

4                 if (!test.Contains(key))

5                 {

6                     queryTable2.Add(key, queryTable[key]);

7                 }

8              

9             }

결 과 는 15 초 만 에 콘 솔 에서 실행 결 과 를 출력 했다. 1537
 
그러나 MSDN 에서 var 에 대한 정 의 는:
방법 범위 에서 설명 하 는 변 수 는 암시 적 형식 var 를 가 질 수 있 습 니 다.암시 적 형식의 로 컬 변 수 는 강 한 형식 변수 입 니 다.
그런데 제 HashTable 에 있 는 key 는 문자열 을 추 가 했 습 니 다. 그리고 HashTable. add 방법의 원형 을 찾 았 습 니 다.

 
  
 
   
1 public virtual void Add (

2     Object key,

3     Object value

4 )
  
 
  
真是坑啊，原来Hashtable在添加元素的时候，自动转化成了object类型
 
  
为了一探究竟，再用ILspy查看底层源代码，
 
  
找到if (!test.Contains(key))这一句
 
  
修改前
 
  
 
   
 1     IL_00a4: ldloc.s CS$5$0001

 2                 IL_00a6: callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()

 3                 IL_00ab: stloc.s key

 4                 IL_00ad: nop

 5                 IL_00ae: ldloc.2

 6                 IL_00af: ldloc.s key

 7                 IL_00b1: call bool [System.Core]System.Linq.Enumerable::Contains<object>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, !!0)

 8                 IL_00b6: stloc.s CS$4$0000

 9                 IL_00b8: ldloc.s CS$4$0000

10                 IL_00ba: brtrue.s IL_00d0
  
컴 파 일 러 의 기본 키 는 object 형식 이기 때문에 IEnumerable 인터페이스의 Contains 방법 을 호출 했 습 니 다. mscorlib] System. collections. Generic. IEnumerable ` 1 , !!0) 
(HashSet 은 IEnumerable 을 실현 했다) 즉, HashSet 의 모든 요 소 를 끊임없이 호출 하 는 Equals 방법 과 key 를 비교 하 는 것 이다.
어쩐지 그렇게 오래 운행 하 더 라 니.
수정 후
 1             IL_00a4: ldloc.s CS$5$0001

 2                 IL_00a6: callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()

 3                 IL_00ab: castclass [mscorlib]System.String

 4                 IL_00b0: stloc.s key

 5                 IL_00b2: nop

 6                 IL_00b3: ldloc.2

 7                 IL_00b4: ldloc.s key

 8                 IL_00b6: callvirt instance bool class [System.Core]System.Collections.Generic.HashSet`1<string>::Contains(!0)

 9                 IL_00bb: stloc.s CS$4$0000

10                 IL_00bd: ldloc.s CS$4$0000

11                 IL_00bf: brtrue.s IL_00d5
  
이때 서 야 정상 적 인 HashSet 의 Contains 를 호출 하여 [System. Core] System. Collections. Generic. HashSet ` 1 < string >: Contains (! 0)
시간 복잡 도 O (1)
곰 곰 이 생각해 보면 여기 또 하나의 함정 은 바로 HashSet. Contains (object a) 를 호출 하 는 것 이다.
첫 번 째 는 우리 가 평소에 알 고 있 는 IEnumerator 의 인 터 페 이 스 를 호출 하여 모든 요소 와 매개 변수 a 를 비교 (Equals 방법 을 호출) 하여 a 가 HashSet 에 있 는 지 판단 하 는 것 이다.
두 번 째 는 범 형 이 HashSet. Contains < T > (T a) 를 실현 하 는 것 입 니 다. T 는 우리 가 HashSet 을 정의 할 때 지정 한 유형 입 니 다. 이때 Contains 는 해시 표 형식 으로 a 를 찾 을 수 있 습 니 다.
우리 가 사용 할 때 유형 T 를 지정 하지 않 으 면  ,컴 파 일 러 는 자동 으로 최적화 되 고 컴 파 일 러 는 a 가 T 유형 인지 아 닌 지 를 판단 합 니 다.
T 타 입 이면 컴 파 일 러 는 두 번 째 구현 을 자동 으로 호출 하고, 그렇지 않 으 면 첫 번 째 구현 을 호출 합 니 다.