[C#] 딕셔너리 (Dictionary)

딕셔너리란?

C#의 Dictionary<TKey, KValue> 자료구조는 키와 값의 쌍의 데이터를 저장하는 제네릭 컬렉션입니다.

이 자료구조는 System.Collections.Generic 네임스페이스에 포함되어 있으며, 키를 사용하여 값을 효율적으로 검색할 수 있습니다.

 

 

주요 특징 및 기능

1. 키-값 쌍 저장:

• 딕셔너리는 키와 값의 쌍을 저장합니다. 각 키는 고유하며, 중복될 수 없습니다.
• 값은 중복될 수 있지만, 키는 유일해야 합니다.

 

2. 빠른 검색 속도:

• 딕셔너리는 해시테이블을 사용하여 내부적으로 데이터를 저장하므로, 평균적으로 O(1)의 시간 복잡도로 키를 사용한 값 검색이 가능합니다.

 

3. 제네릭 타입 지원:

• Dictionary<TKey, TValue>는 제네릭 타입을 지원하여, 타입 안정성과 성능을 보장합니다.
• 예: Dictionary<int, string>, Dictionary<string, List<int>>

 

4.  메서드 및 프로퍼티:

• Add(TKey key, TValue value): 새로운 키-값 쌍을 추가합니다.
• Remove(TKey key): 특정 키를 제거합니다.
• ContainsKey(TKey, key): 특정 키가 존재하는지 확인합니다.
• TryGetValue(TKey, key, out TValue value): 키를 사용하여 값을 검색하며, 성공 여부를 반환합니다.
• Count: 딕셔너리 내의 키-값 쌍의 개수를 반환합니다.
• Keys: 모든 키를 반환합니다.
• Values: 모든 값을 반환합니다.

 

5. TryGetValue Vs ContainsKey 

딕셔너리에서 제공하는 TryGetValue 메서드와 ContainsKey 메서드는 모두 특정 키가 딕셔너리에 존재하는지 확인하는 데 사용합니다.

하지만 두 메서드의 탐색 속도에는 차이가 있으며, 그 이유는 내부 구현 방식에 있습니다.

TryGetValue:

• 해당 메서드는 키가 딕셔너리에 존재하는지 확인하고, 키가 존재하면 해당 키에 대한 값을 반환합니다.
• 반환값: 키가 존재하면 true, 존재하지 않으면 false
• 출력 매개변수: 키가 존재하면 해당 키에 대한 값을 out 매개변수로 반환

ContainsKey:

• 해당 메서드는 단순히 키가 딕셔너리에 존재하는지 여부만을 확인합니다.
• 반환값: 키가 존재하면 true, 존재하지 않으면 false

탐색 속도 차이와 그 이유

• TryGetValue의 속도: 딕셔너리의 내부 해시 테이블에서 키를 찾고 값을 검색하는 작업이 동시에 이루어지기 때문에, 한 번의 검색 연산으로 키가 존재하는지 확인하고 값을 얻을 수 있습니다.
• ContainsKey의 속도: 딕셔너리의 내부 해시 테이블에서 키의 존재 여부만 확인하는 데 촛점을 맞추고 있어, 값이 필요할 경우 추가적인 연산이 필요합니다.

 

 

예제 코드

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<int, string> dict = new Dictionary<int, string>();

        // 요소 추가
        dict.Add(1, "One");
        dict.Add(2, "Two");
        dict.Add(3, "Three");

        // 요소 출력
        Console.WriteLine(dict[1]); // Output: One

        // 해당 키가 딕셔너리 내에 존재하는지 확인
        if (dict.ContainsKey(2))
        {
            Console.WriteLine("Key 2 exists.");
        }

        // 요소 삭제
        dict.Remove(3);

        // 반복문 사용
        foreach (KeyValuePair<int, string> kvp in dict)
        {
            Console.WriteLine("Key: {0}, Value: {1}", kvp.Key, kvp.Value);
        }
    }
}

 

 

 

---

내부 작동 구조

1. 해시 함수 사용:

• 딕셔너리의 키는 GetHashCode() 메서드를 사용하여 해시 코드로 변환됩니다. 해시 코드는 정수 값이며, 키의 고유 식별자 역할을 합니다.
• 해시 코드는 해시 테이블의 인덱스로 사용되어, 해당 위치에 값을 저장하거나 검색할 수 있습니다.

 

2. 해시 테이블:

• 해시 테이블은 배열 구조로, 각 배열 요소는 버킷(Bucket)이라 불립니다. 각 버킷은 키-값 쌍을 저장합니다.
• 해시 함수는 키의 해시 코드를 해시 테이블의 크기로 나눈 나머지 값을 인덱스로 사용하여 버킷을 결정합니다.

 

3. 저장 및 검색 과정:

• 저장: 새로운 키-값 쌍을 추가할 때, 키의 해시 코드를 계산하고, 이를 통해 해시 테이블의 인덱스를 결정합니다. 해당 인덱스의 버킷에 키-값 쌍을 저장합니다.
• 검색: 키를 사용하여 값을 검색할 때, 키의 해시 코드를 계산하고, 해시 테이블의 인덱스를 결정하여 해당 버킷을 확인합니다. 버킷에 저장된 키와 검색 키를 비교하여 일치하는 값을 반환합니다.

 

 

해시 충돌

해시 충돌(Hash Collision)은 서로 다른 두 개 이상의 키가 동일한 해시 값을 가지는 상황을 말합니다. 해시 충돌은 해시 테이블과 같은 자료 구조에서 피할 수 없는 현상입니다. 그 이유는 다음과 같이 있습니다.

 

1. 유한한 해시 테이블 크기

해시 테이블의 크기는 유한합니다. 해시 함수는 임의 크기의 입력을 고정된 크기의 해시 값으로 변환합니다. 따라서 입력 가능한 키의 수는 무한할 수 있지만, 해시 값의 범위는 제한되어 있습니다.

 

2. 해시 함수의 설계 한계

이상적인 해시 함수는 서로 다른 모든 키에 대해 고유한 해시 값을 생성해야 하지만, 실제로는 이를 완벽하게 구현할 수 없습니다. 해시 함수는 입력 데이터를 압축된 해시 값으로 매핑하는 과정에서 정보 손실이 발생합니다.

이 과정에서 서로 다른 키가 동일한 해시 값을 가질 가능성이 존재하며, 이는 해시 충돌로 이어집니다.

 

3. 해시 테이블의 부적절한 크기 설정

해시 테이블의 크기를 너무 작게 설정하면 충돌의 빈도가 증가합니다. 반대로, 해시 테이블의 크기를 너무 크게 설정하면 메모리 낭비가 발생할 수 있습니다. 해시 테이블의 크기를 적절히 설정하지 않으면 해시 충돌은 피하기 어려워집니다.

 

 

예제: 해시 충돌의 발생

다음은 단순한 해시 함수를 사용하여 해시 충돌이 발생하는 예 입니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 해시 테이블의 크기를 10으로 설정
        int tableSize = 10;

        // 단순 해시 함수: 키를 10으로 나눈 나머지를 해시 값으로 사용
        Func<int, int> hashFunction = key => key % tableSize;

        // 예제 키들
        int[] keys = { 15, 25, 35, 45 };

        // 해시 값 출력
        foreach (var key in keys)
        {
            int hashValue = hashFunction(key);
            Console.WriteLine($"Key: {key}, Hash Value: {hashValue}");
        }
    }
}

 

이 예제는 키 15, 25, 35, 45 는 모두 해시 값 5를 가지게 됩니다. 이는 해시 충돌의 예로, 서로 다른 키들이 동일한 해시 값을 가지게 되는 상황을 보여줍니다.

 

 

해시 충돌 해결 방법 

1. 체이닝(Chaining)

• 각 버킷을 연결 리스트로 구성하여 충돌이 발생하면 해당 버킷에 여러 키-값 쌍을 저장하는 방법입니다.
• 동일한 해시 코드를 가진 키-값 쌍은 버킷의 연결 리스트에 추가됩니다.
• 검색 시, 버킷의 연결 리스트를 순회하여 키를 비교하고 일치하는 값을 찾습니다.

 

2. 개방 주소법(Open Addressing)

• 충돌이 발생하면 다른 빈 버킷을 찾아서 저장하는 방법입니다. 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing)등이 있습니다.
• 선형 탐사는 충돌이 발생하면 고정된 간격으로 다음 버킷을 탐색합니다.
• 이차 탐사는 탐색 간격이 제곱수로 증가합니다.
• 이중 해싱은 두 번째 해시 함수를 사용하여 탐색 간격을 결정합니다.

 

3. 해시 함수 개선

• 더 나은 해시 함수를 설계하여 충돌 가능성을 줄입니다. 해시 함수는 입력 키의 분포를 고려하여 고르게 해시 값을 생성해야 합니다.
• c#의 Dictionary는 기본적으로 키의 GetHashCode() 메서드를 사용하지만 필요에 따라 사용자 정의 해시 함수를 사용할 수 있습니다.

 

4. 해시 테이블 크기 조정

• 적절한 해시 테이블 크기를 선택하고 필요에 따라 동적으로 크기를 조정하여 충돌 빈도를 줄입니다.

 

 

 

---

시간 복잡도

1. 평균 시간 복잡도:

• 삽입, 삭제, 검색: O(1)
  • 해시 함수가 키를 해시 코드로 변환하는 데 걸리는 시간은 상수 시간입니다. 해시 코드에 기반하여 해시 테이블의 인덱스를 곗산하고 해당 위치에 접근하는 시간도 상수 시간입니다.
  • 해시 테이블에서 적절한 버킷에 접근하여 키-값 쌍을 추가, 삭제 또는 검색하는 작업은 평균적으로 상수 시간에 수행됩니다.

 

2. 최악 시간 복잡도:

• 삽입, 삭제, 검색: O(n)
  • 최악의 경우는 모든 키가 동일한 해시 값을 가지는 해시 충돌이 발생할 때입니다. 이 경우 모든 키가 단일 버킷에 저장되어야 하므로, 해당 버킷의 연결 리스트 또는 다른 충돌 해결 방식에 따라 검색해야 합니다.
    따라서 최악의 경우에는 n개의 키를 모두 순회해야 하므로 시간 복잡도는 O(n)이 됩니다.

 

 

 

---

핵심 정리

1. 기본 개념

• 딕셔너리는 C#의 제네릭 컬렉션으로, 키-값 쌍을 저장하는 자료 구조 입니다.
• 키는 고유하며, 이를 통해 값을 효율적으로 검색할 수 있습니다.

 

2. 해시 함수와 해시 테이블

• 해시 함수: 키를 해시 코드로 변환하여 해시 테이블의 인덱스를 계산합니다.
• 해시 테이블: 내부적으로 배열 구조를 가지며, 각 배열 요소(버킷)에 키-값 쌍을 저장합니다.

 

3. 시간 복잡도

• 평균 시간 복잡도: O(1)
  • 해시 함수를 사용하여 키의 해시 코드를 계산하고, 해시 테이블의 인덱스를 통해 빠르게 접근할 수 있습니다.

 

• 최악 시간 복잡도: O(n)
  •  해시 충돌이 발생할 경우, 동일한 해시 값을 가진 키들이 같은 버킷에 저장되어 검색 시간이 증가할 수 있습니다. 

 

• 시간 복잡도 정리
  • 해시 함수가 이상적이라는 가정하에 시간 복잡도는 O(1)입니다.

 

4. 해시 충돌과 해결 방법

• 해시 충돌: 서로 다른 키가 동일한 해시 값을 가지는 상황
• 해결 방법:
  • 체이닝(Chaining): 각 버킷을 연결 리스트로 구성하여 충돌된 키-값 쌍을 저장합니다.
  • 개방 주소법(Open Addressing): 충돌 발생 시 다른 빈 버킷을 찾아 저장합니다.
  • 해시 함수 개선: 더 나은 해시 함수를 설계하여 충돌 가능성을 줄입니다.
  • 해시 테이블 크기 조정: 적절한 크기의 해시 테이블을 사용하고 필요 시 크기를 조정합니다.

 

 

 

---

결론

C#의 딕셔너리는 효율적인 키-값 쌍 저장 및 검색을 위한 자료 구조로, 평균적으로 상수 시간 복잡도를 제공합니다. 해시 충돌이 발생할 경우 최악의 시간 복잡도가 O(n)으로 증가 할 수 있지만, 체이닝이나 개방 주소법 등의 충돌 해결 방법을 통해 성능 저하를 최소화할 수 있습니다. 해시 함수의 품질과  해시 테이블의 크기를 적절히 조정하는 것이 성능에 중요한 영향을 미칩니다.

 

 

 

---

지금까지 딕셔너리에 대해 알아보았습니다.

현재 글의 내용 중 틀린 부분이나, 지적하실 내용이 있으시다면 언제든지 알려주세요! 읽어주셔서 감사합니다.