string[] words = { "api", "cache", "api" };
var count = new Dictionary<string, int>();

foreach (string word in words)
{
    count[word] = count.GetValueOrDefault(word) + 1;
}

구조

해시 테이블은 키를 해시 함수에 넣어 정수값으로 바꾸고, 그 값을 내부 버킷 위치로 매핑합니다. 그래서 정렬 없이도 평균적으로 빠른 조회가 가능합니다.

key -> hash code -> bucket index -> stored entry

서로 다른 키가 같은 버킷에 들어가는 상황을 충돌이라고 합니다. 충돌이 많아지면 한 버킷 안에서 추가 탐색이 필요해지고, 평균 O(1)에 가까운 장점이 줄어듭니다.

Load factor는 원소 수와 bucket 수의 비율입니다. 구현이 임계치를 넘으면 bucket 배열을 키우고 기존 entry를 다시 배치하는 rehash를 수행할 수 있어 개별 삽입은 비싸질 수 있습니다. C++ std::unordered_map의 사용자 정의 key는 equality가 같은 값에 같은 hash를 반환해야 하며, 저장 중 hash에 쓰는 필드를 바꾸지 않습니다.

bucketIndex = hash(key) % bucketCount
bucket[bucketIndex] -> entry -> entry  // separate chaining 예시

Separate chaining은 같은 bucket의 entry를 연결하고, open addressing은 빈 slot을 probe합니다. 구현이 무엇인지에 따라 삭제, load factor와 iterator invalidation 계약이 달라집니다. C++에서 원소 수를 예상하면 reserve(n)으로 rehash 횟수를 줄일 수 있지만 reference·iterator 무효화 규칙은 container 문서를 확인합니다.

Dictionary와 HashSet

Dictionary<TKey,TValue>는 키로 값을 찾을 때 씁니다. HashSet<T>는 값이 존재하는지만 중요할 때 씁니다.

var indexByName = new Dictionary<string, int>();
indexByName["mina"] = 3;

var seen = new HashSet<int>();
seen.Add(10);

if (seen.Contains(10))
{
    // 이미 본 값
}

없는 키를 읽을 때 예외를 피하려면 TryGetValue가 키 존재와 값을 한 번에 확인합니다. 이미 있을 때만 거부하고 싶으면 TryAdd, 기본값이 자연스러우면 GetValueOrDefault를 고릅니다.

if (indexByName.TryGetValue("mina", out int index))
{
    Console.WriteLine(index);
}

bool added = indexByName.TryAdd("jisu", 4);
var caseInsensitive = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

StringComparer.OrdinalIgnoreCase처럼 비교 규칙을 생성 시점에 넘기면, 추가·조회·삭제가 같은 equality와 hash 규칙을 공유합니다. 중간에 비교 기준을 바꾸는 방법은 없습니다.

선택 기준

해시는 “빠른 포함 검사”가 필요한 O(n²) 풀이를 O(n)에 가깝게 줄일 때 자주 등장합니다.

var seen = new HashSet<int>();

foreach (int x in nums)
{
    int need = target - x;
    if (seen.Contains(need)) return true;
    seen.Add(x);
}

주의할 점