C# 컬렉션 고르기: Dictionary·HashSet·FrozenDictionary 실측

2026년 11월 보강: 2021년 7월 19일에 쓴 이 글은 같은 달의 컬렉션 기초 글과 내용(ArrayList·Queue·Stack·Hashtable)이 거의 겹쳤고, 예제 세 개는 .NET 10에서 컴파일되지 않았습니다(2.3 f의 error CS1003, Colsole 오타의 error CS0103). 그래서 이 글은 범위를 바꿔 지금 쓰는 컬렉션 중 무엇을 고를지를 다룹니다. 레거시 네 클래스와 박싱 비용은 기초 글로, List<T> 내부 구조는 List 내부 동작 글로 옮겼습니다.

이 글은 List<T>와 Dictionary는 쓰지만 HashSet, SortedDictionary, PriorityQueue, FrozenDictionary, ImmutableArray 중 언제 무엇을 골라야 할지 헷갈리는 분을 위한 글입니다. 결론부터 말하면 키로 찾으면 Dictionary/HashSet, 시작 후 바뀌지 않으면 FrozenDictionary/FrozenSet, 키 순서가 계속 필요할 때만 SortedDictionary입니다. 문자열 키 1만 개로 조회 속도와 생성 비용을 재서 이 판단의 근거를 붙였습니다.

2021년 글에서 바로잡은 것

원문 예제 세 개(ArrayList, Queue, Stack)는 실수 리터럴과 접미사 사이에 공백이 있어 첫 단계에서 멈췄습니다.

Program.cs(11,32): error CS1003: 구문 오류입니다. ','이(가) 필요합니다.

2.3 f를 2.3f로 고치면 이번에는 Console의 오타가 드러납니다.

Program.cs(16,17): error CS0103: 'Colsole' 이름이 현재 컨텍스트에 없습니다.
Program.cs(17,17): error CS0103: 'Colsole' 이름이 현재 컨텍스트에 없습니다.

둘 다 고치면 원문 주석대로 동작했습니다. ArrayList는 10 / 2.3 / 30 / 여러분~ / 공부 열심히 하세요~~, Queue는 30 / 4.4 / ABC, Stack은 ABC / 4.4 / 10이 출력됐습니다. Hashtable 예제는 원래 컴파일됐고 사과 / 바나나 / 오렌지를 출력했습니다.

본문 설명도 세 곳을 고칩니다.

• "C#에서 제공하는 모든 컬렉션은 모든 타입의 변수를 담을 수 있다"는 System.Collections의 비제네릭 클래스에만 맞습니다. List<int>에 문자열을 넣으면 error CS1503으로 컴파일되지 않습니다.
• "해시 테이블의 키로 어떤 타입이든 쓸 수 있다"는 조건부입니다. null은 키가 될 수 없고(ArgumentNullException), 사용자 정의 타입은 Equals와 GetHashCode를 함께 재정의해야 같은 키로 인식됩니다.
• 끝의 "도움말"(C 언어의 스택·힙·데이터 영역)은 이 주제와 맞지 않아 뺐습니다. 거기서 "int i = 10; int array[i];는 컴파일러가 처리할 수 없다"고 했는데, C99부터는 가변 길이 배열로 컴파일됩니다(clang -std=c99에서 sizeof array가 40). C89로 컴파일해야 warning: variable length arrays are a C99 feature가 나옵니다.
• 원문의 큐·스택·해시 테이블·박싱 도식 네 장은 다른 자료에서 옮겨 온 것으로 보여 저작권 문제를 피하려고 뺐습니다. 큐·스택의 동작은 컬렉션 기초에서 실제 출력으로 보여 주고, 이 글의 그림은 모두 직접 그렸습니다.

Dictionary와 HashSet: 기본 선택

키로 값을 찾을 때는 Dictionary<TKey, TValue>, 값이 들어 있는지만 알면 될 때는 HashSet<T>가 기본입니다. 둘 다 해시 기반이라 개수가 늘어도 조회 시간이 거의 일정합니다.

HashSet<string> a = ["ios", "android", "web"];   // C# 12 컬렉션 식
HashSet<string> b = ["web", "desktop"];
a.IntersectWith(b);
Console.WriteLine("HashSet Add dup -> " + b.Add("web") + ", intersect: " + string.Join(",", a));

HashSet Add dup -> False, intersect: web

HashSet.Add는 이미 있으면 예외 없이 false를 돌려주므로 "처음 본 것만 처리" 같은 중복 제거에 그대로 쓸 수 있습니다. IntersectWith, UnionWith, ExceptWith 같은 집합 연산도 있습니다.

주의할 점은 열거 순서입니다. Dictionary는 지우지 않고 추가만 하면 넣은 순서대로 열거되는 것처럼 보이지만, 지운 자리가 재사용됩니다.

var d = new Dictionary<string, int> { ["a"] = 1, ["b"] = 2, ["c"] = 3 };
d.Remove("a"); d["d"] = 4;
Console.WriteLine(string.Join(",", d.Keys));

d,b,c

d가 맨 앞에 나왔습니다. 문서상 순서는 정의되지 않으므로, 순서가 필요하면 아래의 SortedDictionary나 정렬을 명시해야 합니다.

SortedDictionary, LinkedList, PriorityQueue

SortedDictionary<TKey, TValue>는 키를 항상 정렬된 상태로 유지합니다(내부는 이진 탐색 트리).

SortedDictionary: apple,fig,pear

("pear", "apple", "fig") 순서로 넣어도 키 순서로 나옵니다. 대신 조회가 해시 조회보다 느립니다(아래 실측).

LinkedList<T>는 이미 가지고 있는 노드(LinkedListNode<T>) 앞뒤에 넣고 빼는 작업이 상수 시간인 이중 연결 리스트입니다. 값으로 찾는 Find는 처음부터 훑으므로, 노드 참조를 들고 다니는 경우(LRU 캐시 구현 등)가 아니면 List<T>가 낫습니다.

var ll = new LinkedList<int>([1, 2, 4]);
ll.AddAfter(ll.Find(2)!, 3);   // 1,2,3,4

PriorityQueue<TElement, TPriority>는 .NET 6에 추가됐습니다. 2021년 7월 당시의 .NET 5에는 없었습니다. 우선순위 값이 작은 것부터 나옵니다.

var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 5); pq.Enqueue("urgent", 1); pq.Enqueue("normal", 3);
while (pq.TryDequeue(out var job, out var pri)) Console.Write($"{job}({pri}) ");

urgent(1) normal(3) low(5) 

Microsoft Learn 문서에 따르면 우선순위가 같은 요소끼리의 순서는 보장되지 않고, UnorderedItems로 열거해도 우선순위 순서가 아닙니다. 작업 예약, 다익스트라 최단 경로처럼 "다음에 가장 급한 것"을 반복해서 꺼내는 곳에 씁니다.

FrozenDictionary·FrozenSet과 ImmutableArray

FrozenDictionary/FrozenSet(.NET 8, System.Collections.Frozen)은 만든 뒤 바꿀 수 없는 대신 조회에 최적화된 구조를 만들 때 고릅니다. 실제로 만든 객체의 형식을 찍어 보면 키 특성에 따라 다른 구현이 선택됩니다.

Frozen: 2 True LengthBucketsFrozenDictionary`1

키가 "ko", "ja", "en"처럼 짧을 때는 길이별 버킷 구현이, 아래 측정의 user-000123-… 같은 키에서는 OrdinalStringFrozenDictionary_LeftJustifiedSubstring이 골라졌습니다. 키의 일부 문자만 해시해서 시간을 줄이는 방식입니다. 인터페이스를 통해 Add를 부르면 NotSupportedException이 납니다.

ImmutableArray<T>(System.Collections.Immutable)는 바꿀 수 없는 배열입니다. Add는 원본을 그대로 두고 새 배열을 돌려줍니다.

ImmutableArray<int> ia = [1, 2, 3];
var ib = ia.Add(4);   // ia=1,2,3  ib=1,2,3,4

ImmutableArray는 구조체라서 default로 두면 내부 배열이 없습니다. IsDefault가 True이고, 이 상태에서 Length를 읽으면 NullReferenceException이 났습니다. 필드로 둘 때는 []나 ImmutableArray<int>.Empty로 초기화해 두세요.

자주 헷갈리는 것이 읽기 전용 래퍼입니다.

var src = new List<int> { 1, 2 };
IReadOnlyList<int> ro = src.AsReadOnly();
src.Add(3);
Console.WriteLine(ro.Count);   // 3

AsReadOnly()는 원본을 보는 창일 뿐이라 원본이 바뀌면 같이 바뀝니다. "받는 쪽이 못 고치게"는 래퍼로 충분하고, "누구도 못 고치게"는 Immutable·Frozen이 필요합니다.

조회 속도 실측: 문자열 키 1만 개

문자열 키 1만 개(user-000123-1a2b3c4d 형태)를 각 컬렉션에 넣고, 미리 뽑아 둔 무작위 키 500만 개(전부 존재하는 키)를 조회했습니다. 모든 방식을 같은 람다로 감싸 호출해서 람다 호출 비용은 똑같이 들어가 있습니다. .NET 10.0.14, Release 빌드, Apple Silicon Mac, 워밍업 후 3회 측정의 마지막 값입니다.

Dictionary는 실행마다 18~33ns로 흔들렸고, 나머지는 회차 간 차이가 작았습니다. 읽어낼 점은 세 가지입니다.

• Frozen은 조회가 약 1.5배 빠르지만 생성이 약 8배 비쌉니다. 1만 개 기준 1.8ms라 시작할 때 한 번이면 문제없지만, 요청마다 만들면 손해입니다.
• ImmutableDictionary는 조회가 Dictionary의 4배 이상 느렸습니다. 내부가 트리라서입니다. 조금씩 바꾼 버전을 여러 개 들고 있어야 할 때(스냅숏 공유) 쓰고, 단순히 "바뀌지 않는 표"라면 FrozenDictionary가 맞습니다.
• List.IndexOf는 약 11μs로 Dictionary의 500배였습니다. 1만 개를 처음부터 비교하기 때문입니다. 리스트에서 Contains를 반복하는 코드는 가장 먼저 HashSet으로 바꿀 후보입니다.

판단 그림: 언제 무엇을 쓸까

레거시 ArrayList·Hashtable을 이 표의 형식으로 옮기는 방법은 컬렉션 기초에서, 이 컬렉션들을 거르고 묶는 방법은 LINQ 기초에서 이어집니다.

확인 환경: .NET SDK 10.0.403 / 런타임 10.0.14, C# 14(net10.0 기본값), macOS(Apple Silicon Mac). C 예제는 Apple clang.