C/C++ 자료 구조

C와 C++의 해시 테이블(hash table)

이 레슨에서는 C로 직접 만든 해시 테이블과 C++의 std::unordered_map으로 각 단어가 몇 번 나오는지 셉니다.

  • 중급
  • 5분 분량
  • 실행 가능한 예제 2개

소개

어떤 문제를 해결하나요

단어가 각각 몇 번 나오는지 세거나 이름으로 사용자를 찾으려면, 키로 데이터에 빠르게 접근할 수 있어야 합니다. 그때마다 리스트를 처음부터 뒤지면 데이터가 늘어날수록 느려집니다. 해시 테이블(hash table)은 찾는 자리로 거의 곧바로 갑니다.

일상 속 비유

해시 테이블은 ㄱ, ㄴ, ㄷ처럼 첫 글자 탭이 붙은 주소록과 같습니다. 이름만 보면 어느 탭을 펼칠지 알 수 있으므로 주소록 전체를 읽을 필요가 없습니다. 한 탭에 여러 이름이 있으니, 그 쪽만 읽으면서 정확한 이름을 찾습니다.

주소록에서 코드로
hash(text)🔤 키 자체로 탭을 계산합니다
buckets[bucket]📑 그 탭 뒤의 쪽
item->next📝 같은 쪽에 있는 다른 이름들 (체이닝)
strcmp(item->key, ...)🔍 정확히 원하는 항목인지 확인합니다
키를 해시해 버킷을 정하고, 그 버킷 안에서만 찾습니다.
한 문장으로

해시 테이블은 키와 값의 쌍을 버킷 배열에 저장합니다. 해시 함수로 각 키가 들어갈 버킷을 계산하기 때문에, 조회는 대개 상수 시간에 끝납니다.

핵심 정리

  1. hash는 키의 문자들을 섞어 숫자 하나로 만든 다음, 버킷 인덱스인 value % 5를 돌려줍니다.
  2. Item마다 next 포인터가 있어서, 같은 버킷에 들어간 키들은 체인으로 이어집니다.
  3. 단어를 셀 때는 단어를 해시하고, 해당 버킷의 체인을 따라가며 strcmp로 키를 비교합니다.
  4. C++의 std::unordered_map은 해싱, 체이닝, 크기 늘리기를 모두 대신 해 줍니다: ++counts[word].

사용하면 좋은 경우

  • 단어 빈도처럼 등장 횟수를 셀 때.
  • 키로 빠르게 조회할 때: 캐시, 심볼 테이블, 사용자 레코드.
  • 중복을 없애거나 어떤 값이 들어 있는지 확인할 때.

필요 없는 경우

  • 키를 정렬된 순서로 다뤄야 할 때: std::map을 쓰거나 키를 정렬하세요.
  • 아주 작은 데이터 묶음: 배열을 단순히 검색해도 충분히 빠릅니다.

동작 원리 보기

키를 입력하고 저장하거나 찾아보세요. 키는 해시로 버킷 번호가 되므로 프로그램은 올바른 버킷으로 바로 갑니다.

C와 C++ 코드 예제

C
실행 →
main.c
#include <stdio.h>
#include <string.h>

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}
이 예제의 실행 버튼 만들기 실행 결과
c=2 cpp=1
C++
실행 →
main.cpp
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}
이 예제의 실행 버튼 만들기 실행 결과
c=2 cpp=1

C와 C++ 비교

C의 hash 함수는 문자열의 문자로 값을 계산한 뒤 5로 나눈 나머지로 5개의 bucket 중 하나를 고릅니다. 각 bucket은 연결 리스트이므로 충돌한 단어들은 같은 bucket 안에 이어집니다. C 예제는 bucket의 동작 원리에 집중하기 위해 고정된 단어 몇 개만 씁니다. C++의 std::unordered_map은 노드를 스스로 관리하고, 필요하면 커지며, 어떤 문자열이든 키로 받습니다.

C

데이터(struct)와 연산이 분리되어 있고, 메모리는 직접 할당하고 해제합니다.

C++

클래스와 컨테이너가 데이터의 일관성을 지키고 자원을 스스로 관리합니다.

연습 문제

두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.

  • 비어 있는 상태와 최대 용량에 이른 순간에 대한 테스트를 추가해 보세요.
  • 메모리 해제 코드를 작성하고 누수가 없는지 확인해 보세요.
  • 표준 라이브러리의 같은 역할을 하는 컨테이너와 복잡도를 비교해 보세요.

자주 하는 실수

문자열 키를 ==로 비교함

C에서 ==는 문자가 아니라 주소를 비교합니다.

문제
if (item->key == word)
수정
if (strcmp(item->key, word) == 0)

충돌을 무시함

서로 다른 두 키가 같은 버킷에 들어갈 수 있습니다. 그러니 버킷만 볼 것이 아니라 키도 확인해야 합니다.

문제
return buckets[hash(word)];
수정
for (Item *item = buckets[hash(word)]; item; item = item->next)
    if (strcmp(item->key, word) == 0) return item;

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

다음: C와 C++의 이진 탐색 →

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지