← 문제로

42. Dictionary<TKey,TValue> 의 내부 구조와 열거 순서

난이도 상
내 리뷰 · C#
해설 · C#

해설 — Dictionary<TKey,TValue> 의 내부 구조와 열거 순서

난이도: 상

요약

Dictionary<TKey,TValue> 의 열거 순서는 버킷 순서도 해시 순서도 아니고, entries[] 배열의 슬롯 인덱스 순서다. 삽입만 하면 결과적으로 삽입 순서와 같아 보이지만, Remove 가 만든 빈 슬롯을 free list 가 LIFO 로 재사용하기 때문에 나중에 넣은 키가 앞쪽 중간 자리에 꽂힌다. 그래서 "삽입 순서대로 순회된다"는 가정은 삭제가 한 번이라도 일어나는 순간 깨진다. 문서상으로도 열거 순서는 보장되지 않는다.

예상 출력(현대 .NET Core/.NET 5+ 기준):

Phase1: Count=5 | 101 102 103 104 105
Phase2: Count=3 | 101 103 105
Phase3: Count=5 | 101 107 103 106 105
Phase4: Count=8 | 101 107 103 106 105 108 109 110
Phase5-Add: InvalidOperationException
Phase5-Remove: no exception
Phase6: missing=(hp=0,lv=0)
Phase7: first=101

핵심은 Phase3 의 101 107 103 106 105 — 106 보다 나중에 넣은 107 이 더 앞에 나온다.

핵심 개념

내부 필드(대략):

private int[]   _buckets;    // 해시 -> entries 인덱스+1 (0 = 비어있음)
private Entry[] _entries;
private int _count;          // 지금까지 "사용된" entries 슬롯의 상한(high-water mark)
private int _freeList;       // 재사용 가능한 슬롯 체인의 머리
private int _freeCount;      // 그 체인의 길이
private int _version;        // 구조 변경 토큰

private struct Entry {
    public uint hashCode;    // 해시 코드를 캐싱해 둔다
    public int  next;        // 같은 버킷의 다음 엔트리 인덱스(-1 = 끝)
    public TKey key;
    public TValue value;
}
  • 분리 연쇄(separate chaining)를 배열로 구현한다. 연결 리스트 노드를 따로 할당하지 않고, 모든 엔트리를 _entries 한 배열에 넣은 뒤 next 로 인덱스를 이어 체인을 만든다. 캐시 지역성이 좋고 GC 압력이 낮다.
  • buckets[i] 에는 인덱스 + 1 이 들어간다(0 을 "비어 있음"으로 쓰기 위해).
  • hashCode 를 엔트리에 캐싱해 두므로, 충돌 체인을 따라갈 때 비싼 Equals 를 부르기 전에 32비트 비교로 대부분 걸러내고, Resize 때도 GetHashCode 를 다시 부르지 않는다.
  • Count 프로퍼티 = _count - _freeCount. 즉 _count 는 "몇 번째 슬롯까지 써봤나"이고 실제 원소 수는 거기서 빈 슬롯 수를 뺀 값이다.

단계별 내부 동작

1) Phase1 — 순차 삽입

_freeCount == 0 이므로 새 엔트리는 항상 index = _count++ 로 배열 끝에 붙는다. 그래서 entries = [101,102,103,104,105], _count=5, Count=5. 열거자는 for (i = 0; i < _count; i++) 로 슬롯 순서대로 훑으며 "살아있는 엔트리"만 내보낸다. 결과적으로 삽입 순서와 일치 — 우연이다.

버킷은 별개다. 키가 int 면 GetHashCode() 가 값 자체이므로 101%7=3, 102%7=4 … 로 흩어지지만, 열거는 버킷을 전혀 보지 않는다. 버킷은 조회 경로에서만 쓴다.

2) Phase2 — Remove 와 free list

Remove(key) 는 슬롯을 배열에서 빼내지 않는다. 대신:

  1. 버킷 체인에서 그 엔트리를 잇는 next 링크를 앞뒤로 이어붙여 떼어내고,
  2. 그 슬롯을 free list 의 새 머리로 만든다: entries[i].next = StartOfFreeList - _freeList; (StartOfFreeList = -3) _freeList = i; _freeCount++;
  3. 참조 타입 키·값이면 null 로 지워 GC 가 회수하게 한다.

next 에 -3 - prev 라는 음수 인코딩을 쓰는 이유는 살아있는 엔트리의 next(≥ -1)와 구분하기 위해서다. 열거자와 Resize 는 next < -1 인 슬롯을 "죽은 슬롯"으로 보고 건너뛴다.

  • Remove(102): entries[1].next = -3 - (-1) = -2, _freeList = 1, _freeCount = 1
  • Remove(104): entries[3].next = -3 - 1 = -4, _freeList = 3, _freeCount = 2

이제 free list 는 3 → 1 (LIFO, 나중에 지운 것이 먼저 재사용된다). _count 는 여전히 5, Count 는 5-2 = 3. 열거 결과 101 103 105.

3) Phase3 — 재사용이 순서를 깨뜨린다

_freeCount > 0 이면 새 삽입은 배열 끝이 아니라 free list 머리를 가져간다.

  • Add(106) → 슬롯 3 차지, _freeList = -3 - entries[3].next = -3 - (-4) = 1
  • Add(107) → 슬롯 1 차지, _freeCount = 0

entries = [101, 107, 103, 106, 105]. 열거 순서 101 107 103 106 105. 106 을 먼저 넣었는데 107 이 앞에 나온다. 이것이 이 문제의 핵심 현상이며, "Dictionary 는 삽입 순서를 유지한다"는 통념이 틀린 결정적 증거다.

4) Phase4 — Resize 는 순서를 섞지 않는다

Add(108) → 슬롯 5, Add(109) → 슬롯 6. 이제 _count == _entries.Length == 7. Add(110) 에서 Resize() 발생: 새 크기는 대략 2배 이상의 소수(7 → 17).

var newEntries = new Entry[newSize];
Array.Copy(_entries, newEntries, _count);   // 슬롯 인덱스 그대로 복사
_buckets = new int[newSize];                 // 버킷만 새로 만든다
for (int i = 0; i < _count; i++)
    if (newEntries[i].next >= -1) { /* 캐싱된 hashCode 로 버킷에 다시 매단다 */ }

즉 재해싱되는 것은 buckets 뿐이고 entries 의 인덱스는 보존된다. 따라서 "Resize 하면 열거 순서가 섞인다"는 통념은 틀렸다 — 순서는 그대로다. 게다가 hashCode 가 엔트리에 캐싱돼 있으므로 GetHashCode() 를 다시 부르지도 않는다(문자열 키가 충돌 폭주로 randomized comparer 로 전환되는 forceNewHashCodes 경로만 예외이며, 이때도 슬롯 순서는 유지된다).

최종 entries = [101,107,103,106,105,108,109,110], Count = 8.

그래도 순서에 의존하면 안 되는 이유는 Resize 가 아니라 (a) free list 재사용, (b) 런타임 버전·구현 변경 가능성, (c) 문서상 무보장 때문이다.

5) Phase5 — 버전 토큰과 "열거 중 수정"

_version 은 구조를 바꾸는 연산에서 증가하고, 열거자는 생성 시 스냅샷한 버전과 매 MoveNext() 에서 비교해 다르면 InvalidOperationException 을 던진다.

  • Add(999) 중 열거 → _version++ → 다음 MoveNext() 에서 예외. (배열이 커지며 열거자가 낡은 배열을 보게 되는 것을 막는 안전장치.)
  • Remove(105) 중 열거 → .NET Core 3.0 이후 Remove 는 의도적으로 _version 을 올리지 않는다(Clear 는 여전히 올린다). 삭제는 배열을 재할당하지 않고 슬롯만 죽은 것으로 표시하므로 열거자가 안전하게 계속 진행할 수 있기 때문이다. 그래서 예외 없이 진행되고, 이미 지나간 슬롯이면 이미 내보낸 뒤이고 아직 안 온 슬롯이면 그냥 건너뛴다. (.NET Framework 4.x 에서는 Remove 도 버전을 올려 예외가 난다 — 런타임에 따라 동작이 갈리는 대표적 지점이다.)
  • 값만 덮어쓰는 dict[existingKey] = v 는 구조 변경이 아니어서 버전을 올리지 않는다. 열거 중 값 갱신은 허용된다.
  • 버전 토큰은 동시성 보호 장치가 아니다. 멀티스레드에서 한쪽이 쓰는 동안 다른 쪽이 읽으면 예외가 아니라 무한 루프·손상된 체인이 될 수 있다.

6) Phase6 — TryGetValue 실패 시 out

실패하면 value = default! 로 채우고 false 를 돌려준다. EntityState 는 구조체라 default 는 (hp=0, lv=0) — null 이 아니라 "그럴듯한 유효값" 이다. 반환값을 무시하고 missing.Hp 를 쓰면 "HP 0 인 엔티티"로 오인해 사망 처리 같은 게임 로직 버그가 된다. 참조 타입이면 최소한 NullReferenceException 으로 즉시 터지지만 값 형식은 조용히 잘못 동작한다.

7) 게임서버 맥락

Dictionary<int, Entity> 를 매 틱 foreach 로 돌리는 코드에서 순서 의존은 이렇게 사고가 난다.

  • 결정성 파괴: 리플레이·서버 검증·롤백 넷코드에서 두 서버가 같은 입력에 같은 순서로 엔티티를 갱신해야 하는데, 엔티티 접속/퇴장(=Add/Remove) 이력이 다르면 free list 상태가 달라져 순회 순서가 갈린다. 물리 해결이나 데미지 적용 순서가 달라지면 시뮬레이션이 어긋난다.
  • "첫 번째 = 가장 먼저 들어온 플레이어" 같은 가정(Phase7): 방장 지정, 타깃 선정, 스폰 순서 등에서 조용히 틀린다.
  • 직렬화 스냅샷 diff: 순서가 달라져 실제 변화가 없는데도 diff 가 커진다.

대안:

  • 순서가 의미 있으면 List<T> + Dictionary<id, index> 로 순서와 조회를 분리하거나, ID 기준 정렬 후 순회(OrderBy(kv => kv.Key))로 결정성을 산다.
  • 밀집 정수 ID 라면 슬롯맵/densely packed array(id → index 간접 테이블 + 연속 배열) 가 순서·캐시 지역성·순회 성능 모두에서 낫다. ECS 가 쓰는 방식.
  • Remove 대신 tombstone 후 배치 압축을 쓰면 순회 중 삭제 문제와 순서 요동을 동시에 줄일 수 있다.

흔한 오해·함정

  • "Dictionary 는 삽입 순서를 유지한다" — 아니다. 삭제가 없을 때만 우연히 그렇게 보인다. Java 의 LinkedHashMap 같은 보장은 없다.
  • "Resize 하면 순서가 섞인다" — 아니다. 섞는 것은 free list 재사용이다. Array.Copy 로 entries 인덱스는 보존된다.
  • "Count 가 3이면 entries 도 3칸만 쓴다" — 아니다. _count 는 5 그대로이고 중간에 죽은 슬롯이 2개 있다. 대량 삭제 후에도 배열은 줄지 않으므로 메모리를 되찾으려면 TrimExcess() 가 필요하다(이때 슬롯이 압축되며 순서가 또 바뀐다).
  • "열거 중 Remove 는 항상 예외" — 런타임에 따라 다르다. .NET Core 3.0+ 는 허용, .NET Framework 는 예외. 이식성을 원하면 지울 키를 모았다가 루프 밖에서 지워라.
  • "버전 토큰이 있으니 스레드 안전 검사가 된다" — 아니다. 레이스 상황에서는 예외조차 안 나고 무한 루프/데이터 손상이 난다. 동시 접근이면 ConcurrentDictionary 또는 외부 락.
  • 키의 GetHashCode/Equals 불일치 — 가변 객체를 키로 쓰고 넣은 뒤 필드를 바꾸면 캐싱된 hashCode 와 실제 해시가 어긋나 영원히 찾지 못하는 엔트리가 된다(열거로는 보이는데 조회는 실패).
  • 해시 충돌 공격 — 문자열 키는 충돌 체인이 길어지면 런타임이 randomized hashing 으로 전환한다. 이것이 string 키 딕셔너리의 순회 순서가 프로세스마다 달라 보일 수 있는 또 다른 이유다.

면접 포인트

  • Dictionary 의 충돌 해결 방식(체이닝을 배열 인덱스로 구현)과 List 노드 할당이 없는 이유를 설명할 수 있는가.
  • _count, _freeCount, Count 세 값의 관계를 정확히 말할 수 있는가.
  • 열거 순서가 entries 슬롯 순서라는 점, 그리고 무엇이 그 순서를 흔드는지 (free list ≠ resize) 구분할 수 있는가.
  • _version 이 어떤 연산에서 올라가고 안 올라가는지, 런타임 버전 차이를 아는가.
  • 순서·결정성이 필요한 게임 로직에서 어떤 자료구조로 바꿀지 제안할 수 있는가.
  • TryGetValue 실패 시 값 형식 default 가 만드는 조용한 버그를 설명할 수 있는가.
← 문제로 돌아가기