C# 컬렉션 성능 비교와 선택 기준

개요

C# 컬렉션 선택은 성능에 직접적인 영향을 줍니다. List<T>를 모든 곳에 사용하거나, Dictionary가 필요한 자리에 List로 선형 탐색하는 패턴은 대규모 데이터에서 심각한 병목이 됩니다. 각 컬렉션의 내부 구조와 복잡도를 이해하면 올바른 선택을 할 수 있습니다.

---

1. 컬렉션별 시간 복잡도

컬렉션	접근	탐색	삽입	삭제
List<T>	O(1)	O(N)	O(1) 끝 / O(N) 중간	O(N)
Dictionary<K,V>	O(1)	O(1)	O(1)	O(1)
HashSet<T>	-	O(1)	O(1)	O(1)
SortedDictionary<K,V>	O(log N)	O(log N)	O(log N)	O(log N)
SortedList<K,V>	O(log N)	O(log N)	O(N)	O(N)
LinkedList<T>	O(N)	O(N)	O(1) 노드 있을 때	O(1) 노드 있을 때
Queue<T>	-	-	O(1)	O(1)
Stack<T>	O(1) top	-	O(1)	O(1)

---

2. List<T>

내부적으로 배열(T[])을 사용합니다. 용량이 초과되면 2배 크기로 재할당합니다.

var list = new List<int>(capacity: 100); // 미리 용량 할당

// 끝에 추가: O(1) amortized
list.Add(42);

// 중간 삽입: O(N) — 이후 원소를 모두 이동
list.Insert(0, 99); // 피해야 할 패턴

// 선형 탐색: O(N)
bool exists = list.Contains(42);

// 정렬 후 이진 탐색: O(log N)
list.Sort();
int idx = list.BinarySearch(42);

// Remove는 내부적으로 Contains + shift: O(N)
list.Remove(42);

// 순서가 중요 없으면 swap-and-pop으로 O(1) 삭제
void SwapRemove<T>(List<T> lst, int index)
{
    lst[index] = lst[lst.Count - 1];
    lst.RemoveAt(lst.Count - 1);
}

---

3. Dictionary<K,V>

해시 테이블 기반입니다. 해시 충돌이 없을 때 O(1)이지만, 나쁜 GetHashCode 구현은 성능을 O(N)으로 떨어뜨립니다.

var registry = new Dictionary<int, Enemy>(capacity: 256);

// 안전한 조회 패턴 (TryGetValue 권장)
if (registry.TryGetValue(enemyId, out Enemy? enemy))
    enemy.TakeDamage(10);

// ContainsKey + 인덱서 조회 → 2번 해시 계산 (비효율)
// if (registry.ContainsKey(id)) var e = registry[id]; // 비권장

// GetOrAdd 패턴 (없으면 추가)
if (!registry.TryGetValue(id, out var e))
{
    e = new Enemy(id);
    registry[id] = e;
}

// 컬렉션을 자주 지우고 재사용
registry.Clear(); // 내부 배열 유지, GC 없음 (재할당보다 효율적)

커스텀 키 타입

// struct 키는 박싱을 피하려면 IEquatable<T> 구현 필수
public readonly struct TileCoord : IEquatable<TileCoord>
{
    public readonly int X, Y;
    public TileCoord(int x, int y) { X = x; Y = y; }

    public bool Equals(TileCoord other) => X == other.X && Y == other.Y;
    public override bool Equals(object? obj) => obj is TileCoord t && Equals(t);
    public override int GetHashCode() => HashCode.Combine(X, Y);
}

var tileMap = new Dictionary<TileCoord, Tile>();

---

4. HashSet<T>

중복 없는 집합이 필요할 때 List.Contains(O(N)) 대신 사용합니다.

var visitedRooms = new HashSet<int>();

// 방문 체크: O(1)
if (visitedRooms.Add(roomId)) // 처음 방문이면 true 반환
    TriggerFirstVisit(roomId);

// 집합 연산
var playerItems  = new HashSet<string> { "sword", "shield" };
var requiredItems = new HashSet<string> { "sword", "key" };

bool hasAll = requiredItems.IsSubsetOf(playerItems); // false
playerItems.IntersectWith(requiredItems); // {"sword"}

---

5. Queue<T> / Stack<T>

// 이벤트 처리 큐 (FIFO)
var eventQueue = new Queue<GameEvent>();
eventQueue.Enqueue(new DamageEvent(10));
eventQueue.Enqueue(new HealEvent(5));

void ProcessEvents()
{
    while (eventQueue.TryDequeue(out var evt))
        evt.Process();
}

// 실행 취소 스택 (LIFO)
var undoStack = new Stack<ICommand>();
undoStack.Push(new MoveCommand(...));

if (undoStack.TryPop(out var cmd))
    cmd.Undo();

---

6. 게임 시나리오별 권장 컬렉션

6.1 ID로 오브젝트 빠르게 조회

// 나쁜 예: O(N) 탐색
Enemy FindEnemy(List<Enemy> enemies, int id)
    => enemies.FirstOrDefault(e => e.Id == id)!;

// 좋은 예: O(1) 조회
Dictionary<int, Enemy> _enemyRegistry = new();
Enemy FindEnemy(int id) => _enemyRegistry[id];

6.2 정렬된 순서로 순회 + 빠른 삽입/삭제

// 타임라인 이벤트 스케줄러
var timeline = new SortedDictionary<float, List<Action>>();

void Schedule(float time, Action callback)
{
    if (!timeline.TryGetValue(time, out var list))
        timeline[time] = list = new List<Action>();
    list.Add(callback);
}

void Tick(float currentTime)
{
    var keys = timeline.Keys.TakeWhile(t => t <= currentTime).ToList();
    foreach (var t in keys)
    {
        foreach (var cb in timeline[t]) cb();
        timeline.Remove(t);
    }
}

6.3 중복 없는 활성 오브젝트 집합

// 현재 활성 버프 목록 (중복 방지)
HashSet<BuffType> _activeBuffs = new();

void ApplyBuff(BuffType buff)
{
    if (_activeBuffs.Add(buff)) // 이미 있으면 false
        buff.OnApply(this);
}

---

7. GC 압력 줄이기

// ArrayPool: 임시 배열의 힙 할당 제거
using System.Buffers;

byte[] buffer = ArrayPool<byte>.Shared.Rent(1024);
try
{
    // buffer 사용
}
finally
{
    ArrayPool<byte>.Shared.Return(buffer);
}

// 고정 크기 버퍼가 필요하면 stackalloc
Span<int> tempBuffer = stackalloc int[64];

---

요약

• ID 기반 조회가 빈번하면 List 대신 Dictionary를 사용해 O(N) → O(1)로 개선한다.
• List.Contains / List.Remove가 핫 경로에 있으면 HashSet으로 교체한다.
• List에서 순서가 중요 없는 삭제는 swap-and-pop 패턴으로 O(N) → O(1)이 된다.
• Dictionary에 struct 키를 쓸 때는 IEquatable<T>를 구현해 박싱을 방지한다.
• 임시 배열이 자주 필요하면 ArrayPool<T>.Shared로 힙 할당을 제거한다.