C\#Dictionary 에서 매 거 진 효율 문 제 를 해결 합 니 다.

사전 사용 의 장점
System.collections.Generic 네 임 스페이스 의 Dictionary 는 기능 이 매우 좋 고 기능 이 현실 사전 과 같 습 니 다.
그것 역시 디 렉 터 리 와 본문 을 가지 고 있 으 며,디 렉 터 리 는 첫 번 째 대략적인 검색 을 하고,본문 은 두 번 째 정확 한 검색 을 한다.데 이 터 를 그룹 으로 나 누 어 디 렉 터 리 를 만 들 고 본문 은 그룹 을 나 눈 결과 입 니 다.그것 은 공간 을 시간 으로 바 꾸 는 방식 으로 큰 메모 리 를 희생 하여 효율 적 인 조회 효율 을 얻 는 것 이다.따라서 기능 사용률 조회>새로 추 가 될 때 사전 을 우선 고려 합 니 다.

        public static Tvalue DicTool<Tkey, Tvalue>(Tkey key, Dictionary<Tkey, Tvalue> dic)
        {
            return dic.TryGetValue(key, out Tvalue _value) ? _value : (Tvalue)default;
        }

           Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 1; i++)
            {
                DicTool(0, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);

실행 시간

            Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 10000; i++)
            {
                DicTool(0, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);

실행 시간
위 에서 알 수 있 듯 이 그것 은 대량의 조 회 를 할 때 사용 시간 이 매우 짧 고 조회 효율 이 매우 높다.그러나 사용 할 때 열 거 를 키워드 로 조회 하 는 것 을 피해 야 한다.그것 은 조회 효율 을 떨 어 뜨 릴 것 이다.
열 거 를 key 로 사용 할 때 조회 효율 이 낮 아 집 니 다.

 Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 10000; i++)
            {
                DicTool(MyEnum.one, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);

실행 시간
이곳 의 집행 시간 을 보면 조회 효율 이 크게 떨어진다 는 것 을 알 수 있다.
최적화 방안:enum 대신 int 를 사용 하고 enum 강제 전환 후 간접 조회 합 니 다.조회 효율 을 비 매 거 진 직접 조회 와 비슷 하 게 할 수 있다.(그리고 다른 최적화 방안 도 있 습 니 다.개인 은 이것 만 사용 한 적 이 있 습 니 다)

using System;
using System.Diagnostics;
using System.Collections.Generic;
namespace Test
{
    public class Program
    {
        public enum MyEnum : int
        {
            one,
            two,
            three
        }
        public static void Main(string[] args)
        {
            Dictionary<int, int> Dic = new Dictionary<int, int>()
            {
                { (int)MyEnum.one,1},
                { (int)MyEnum.two,2},
                { (int)MyEnum.three,3}
            };
            Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 10000; i++)
            {
                DicTool((int)MyEnum.one, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
        }
        public static Tvalue DicTool<Tkey, Tvalue>(Tkey key, Dictionary<Tkey, Tvalue> dic)
        {
            return dic.TryGetValue(key, out Tvalue _value) ? _value : (Tvalue)default;
        }
    }
}

실행 시간
왜 매 거 진 을 사용 하면 효율 이 떨 어 집 니까?
ILSpy 소프트웨어 를 사용 하여 원본 코드 를 역 컴 파일 하여 다음 과 같은 것 을 얻 을 수 있 습 니 다.

public bool TryGetValue(TKey key, out TValue value)
{
    int num = this.FindEntry(key);
    if (num >= 0)
    {
        value = this.entries[num].value;
        return true;
    }
    value = default(TValue);
    return false;
}
private int FindEntry(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (this.buckets != null)
    {
        int num = this.comparer.GetHashCode(key) & 2147483647;
        for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
        {
            if (this.entries[i].hashCode == num && this.comparer.Equals(this.entries[i].key, key))
            {
                return i;
            }
        }
    }
    return -1;
}

Dictionary 소스 코드 를 보면 효율 이 떨 어 지 는 것 은 this.com parer.GetHashCode(key)코드 에서 비롯 된 것 임 을 알 수 있 습 니 다.
comparer 는 일반적인 구성원 을 사 용 했 습 니 다.내부 에 int 형식 을 사용 하면 포장 이 발생 하지 않 지만 Enum 에 IEquatable 인터페이스 가 없 기 때문에 내부 운행 시 포장 행 위 를 일 으 킬 수 있 습 니 다.이 행 위 는 조회 의 효율 을 떨 어 뜨 렸 습 니 다.
IEquatable 소스 코드:

namespace System
{
 [__DynamicallyInvokable]
 public interface IEquatable<T>
 {
  [__DynamicallyInvokable]
  bool Equals(T other);
 }
}

포장:값 형식 을 인용 형식 으로 변환(암시 적 변환)
스 택 에서 위탁 관리 더미 로 데 이 터 를 복사 하고 스 택 에서 데이터 주 소 를 저장 합 니 다.
뜯 기:참조 형식 을 값 형식 으로 변환 합 니 다(명시 적 변환)
보충:C\#중 Dictionary중[]작업 의 효율 문제
오늘 어떤 친구 가 Dictionary에서 데이터 양 이 많 으 면[]조작 이 효율 적 이지 않 냐 고 물 었 다.
마이크로소프트 오픈 소스 C\#에 감 사 드 립 니 다.코드 를 통 해 자신의 추측 을 검증 할 수 있 습 니 다.
여 기 는 마이크로소프트 C\#의 소스 코드 주소 입 니 다.
먼저 결론:Dictionary의[]작업 시간=GetHashCode+n 차 호출 Key.Equals 의 시간 합.
중간 n 이 들 어 오 는 key 의 GetHash Code 의 중 복 률 에 영향 을 받 습 니 다.예 를 들 어 들 어 오 는 key 의 hash 값 은 5 이 고 Dictionary 에서 hash 값 은 5 의 값 은 100 개 입 니 다.이 100 값 은 링크 로 저장 하 는 것 과 같 습 니 다.20 번 째 값 을 찾 으 려 면 n 의 값 은 19 입 니 다.만약 GetHash Code 가 기본적으로 중 복 률 이 없다 면 n 은 시종 1 이 고 극단 적 인 상황 에서 n 은 매우 큰 숫자 일 수 있 습 니 다(테스트 코드 참조).
C\#의 키 코드 는 다음 과 같 습 니 다.

 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;

그리고 여기 서 Dictionary류 의 데이터 조직 구 조 를 말씀 드 리 고 싶 습 니 다.

        private struct Entry {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry
        } 
        private int[] buckets;
        private Entry[] entries;

중간 buckets 는 같은 hash 값 을 저장 하 는 Entry 의 체인 헤더 이 고 같은 hash 값 의 Entry 는 Entry.next 를 통 해 연 결 됩 니 다.새로 추 가 된 Value 에 같은 hash 값 이 존재 하면 buckets 의 값 을 업데이트 합 니 다.존재 하지 않 으 면 새로운 값 을 추가 합 니 다.핵심 코드 는 다음 과 같 습 니 다.

            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[targetBucket] = index;

마지막 문장 에 주의 하 세 요.새로 추 가 된 값 의 아래 표 시 된 inddex 의 값 을 buckets 에 할당 하면 링크 헤드 포인 터 를 업데이트 하 는 것 과 같 습 니 다.이 체인 시 계 는 바로 앞에서 n 이 생 긴 원인 이다.
다음은 제 가 테스트 결 과 를 넣 겠 습 니 다.
GetHashCode 의 소모 가 1ms 일 때:

GetHashCode 의 소모 가 100 ms 일 때:

증가 하 는 소 모 는 99ms,즉 GetHash Code 가 증가 하 는 소모 이 고 뒤의 꼬리 수 는 위의 공식 안의 n 이다.
테스트 코드 는 다음 과 같 습 니 다:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading; 
namespace ConsoleApplication1
{
    class Program
    {
        public class Test1
        {
            private ushort num = 0;
            public Test1(ushort a)
            {
                num = a;
            }
 
            public override int GetHashCode()
            {
                Thread.Sleep(1);
                return num / 100;
            }
 
            public override bool Equals(object obj)
            {
                Thread.Sleep(1);
                return num.Equals((obj as Test1).num);
            }
        }
 
        static void Main(string[] args)
        {
            Dictionary<Test1, string> testDic = new Dictionary<Test1, string>();
            for (ushort a = 0; a < 100; a++)
            {
                Test1 temp = new Test1(a);
                testDic.Add(temp, a.ToString());
            }
 
            Stopwatch stopWatch = new Stopwatch();
            string str = "";
 
            stopWatch.Start();
            str = testDic[new Test1(99)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str +" pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(1)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(50)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(98)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(97)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
        }
    }
}

이상 은 개인 적 인 경험 이 므 로 여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.만약 잘못 이 있 거나 완전히 고려 하지 않 은 부분 이 있다 면 아낌없이 가르침 을 주시 기 바 랍 니 다.