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

// [주제] Dictionary<TKey,TValue> 의 내부 구조(buckets/entries)와 열거 순서
//
// 게임서버에서 "엔티티 ID -> 엔티티" 맵을 Dictionary 로 관리하고, 매 틱
// foreach 로 순회하며 갱신·브로드캐스트한다. 아래 코드는 삽입/삭제/재삽입을
// 섞은 뒤 열거 순서와 Count 를 출력한다. 실행 결과를 예측하고 내부 자료구조
// 수준에서 설명하라.
//
// [과제]
//  1) Phase1~Phase4 각 시점에서 foreach 가 어떤 순서로 키를 출력하는지 예측하고,
//     그 순서가 buckets[] / entries[] 중 무엇에 의해 결정되는지 설명하라.
//  2) Remove 로 비워진 슬롯이 이후 Add 에서 어떻게 재사용되는지
//     (freeList / freeCount) 서술하고, 왜 나중에 넣은 키가 "중간 자리"에
//     나타나는지 설명하라.
//  3) 용량을 넘겨 Resize 가 일어난 뒤 열거 순서는 어떻게 되는가?
//     "재해싱하면 순서가 섞인다"는 통념이 맞는지 근거를 대라.
//  4) Count 와 내부 _count(사용된 entries 슬롯 수)의 관계를 설명하라.
//     둘이 달라지는 시점은 언제인가?
//  5) Phase5 에서 열거 중 Add 와 열거 중 Remove 의 결과가 왜 다른가?
//     버전 토큰(_version)의 역할과 함께 설명하라.
//  6) TryGetValue 가 실패했을 때 out 변수에 무엇이 들어가는지,
//     값 형식일 때 이것이 왜 위험한지 설명하라.
//  7) 게임서버 맥락: "엔티티가 삽입 순서대로 순회될 것"을 가정한 틱 로직이
//     왜 위험한지, 순서가 필요하면 무엇을 써야 하는지 논하라.

using System;
using System.Collections.Generic;

public struct EntityState
{
    public int Hp;
    public int Level;
    public override string ToString() => $"(hp={Hp},lv={Level})";
}

public static class Program
{
    // 용량 7(소수)로 시작해 Resize 시점을 관찰 가능하게 만든다.
    private static readonly Dictionary<int, EntityState> Entities = new(7);

    private static void Add(int id, int hp)
        => Entities[id] = new EntityState { Hp = hp, Level = 1 };

    private static void Dump(string phase)
    {
        Console.Write($"{phase}: Count={Entities.Count} | ");
        foreach (var kv in Entities)
            Console.Write($"{kv.Key} ");
        Console.WriteLine();
    }

    public static void Main()
    {
        // ---- Phase1: 순차 삽입 ----
        Add(101, 10);
        Add(102, 20);
        Add(103, 30);
        Add(104, 40);
        Add(105, 50);
        Dump("Phase1");

        // ---- Phase2: 중간 두 개 제거 ----
        Entities.Remove(102);
        Entities.Remove(104);
        Dump("Phase2");

        // ---- Phase3: 두 개 재삽입 (새 ID) ----
        Add(106, 60);
        Add(107, 70);
        Dump("Phase3");

        // ---- Phase4: 용량을 넘겨 Resize 유발 ----
        Add(108, 80);
        Add(109, 90);
        Add(110, 100);   // 이 시점에 내부 배열이 커진다
        Dump("Phase4");

        // ---- Phase5: 열거 중 수정 ----
        try
        {
            foreach (var kv in Entities)
            {
                if (kv.Key == 103)
                    Entities[999] = new EntityState { Hp = 1, Level = 1 }; // 새 키 추가
            }
            Console.WriteLine("Phase5-Add: no exception");
        }
        catch (InvalidOperationException)
        {
            Console.WriteLine("Phase5-Add: InvalidOperationException");
        }

        try
        {
            foreach (var kv in Entities)
            {
                if (kv.Key == 103)
                    Entities.Remove(105);
            }
            Console.WriteLine("Phase5-Remove: no exception");
        }
        catch (InvalidOperationException)
        {
            Console.WriteLine("Phase5-Remove: InvalidOperationException");
        }

        // ---- Phase6: 조회 실패 시 out 값 ----
        if (!Entities.TryGetValue(4242, out EntityState missing))
            Console.WriteLine($"Phase6: missing={missing}");

        // ---- Phase7: "첫 번째 엔티티"를 순서에 의존해 고르는 코드 ----
        foreach (var kv in Entities)
        {
            Console.WriteLine($"Phase7: first={kv.Key}");
            break;
        }
    }
}