핵심 정리
| 구조 | 저장 | 평균 조회 | 대표 용도 |
|---|---|---|---|
Dictionary<TKey,TValue> | 키와 값 | O(1) | 빈도, 매핑, 인덱스 찾기 |
HashSet<T> | 키만 | O(1) | 중복 제거, 포함 검사 |
| 배열 카운팅 | 정수 인덱스 | O(1) | 값 범위가 작을 때 |
csharp
var count = new Dictionary<string, int>();
foreach (string word in words)
{
count[word] = count.GetValueOrDefault(word) + 1;
}구조
해시 테이블은 키를 해시 함수에 넣어 정수값으로 바꾸고, 그 값을 내부 버킷 위치로 매핑합니다. 그래서 정렬 없이도 평균적으로 빠른 조회가 가능합니다.
text
key -> hash code -> bucket index -> stored entry서로 다른 키가 같은 버킷에 들어가는 상황을 충돌이라고 합니다. 충돌이 많아지면 한 버킷 안에서 추가 탐색이 필요해지고, 평균 O(1)에 가까운 장점이 줄어듭니다.
Dictionary와 HashSet
Dictionary<TKey,TValue>는 키로 값을 찾을 때 씁니다. HashSet<T>는 값이 존재하는지만 중요할 때 씁니다.
csharp
var indexByName = new Dictionary<string, int>();
indexByName["mina"] = 3;
var seen = new HashSet<int>();
seen.Add(10);
if (seen.Contains(10))
{
// 이미 본 값
}선택 기준
| 상황 | 적합한 선택 |
|---|---|
| 값의 등장 횟수 세기 | Dictionary<T, int> |
| 중복 여부 확인 | HashSet<T> |
| 키로 다른 값 찾기 | Dictionary<TKey,TValue> |
| 값 범위가 작고 정수 | 배열 카운팅 |
| 정렬 순서가 필요 | 정렬된 구조 또는 정렬 후 처리 |
해시는 “빠른 포함 검사”가 필요한 O(n²) 풀이를 O(n)에 가깝게 줄일 때 자주 등장합니다.
csharp
var seen = new HashSet<int>();
foreach (int x in nums)
{
int need = target - x;
if (seen.Contains(need)) return true;
seen.Add(x);
}주의할 점
해시 테이블의 O(1)은 평균 기대값입니다. 키의 해시 품질이 나쁘거나 충돌이 많으면 성능이 떨어질 수 있습니다.
또 Dictionary는 없는 키를 인덱서로 읽으면 예외가 납니다. TryGetValue, ContainsKey, GetValueOrDefault 중 하나로 없는 키 처리를 명확히 해야 합니다.
참고 링크
2 sources