C/C++ 자료 구조

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

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

소개

해시 테이블(hash table)은 해시 함수(hash function)로 각 키를 저장 칸(bucket)의 인덱스로 바꾸기 때문에 검색, 삽입, 삭제가 아주 빠릅니다. 서로 다른 두 키가 같은 칸에 들어가는 것을 충돌이라고 하며, 해시 테이블은 체이닝(chaining)이나 개방 주소법(open addressing)으로 이를 처리해야 합니다.

핵심 정리

연산을 작성하기 전에 항상 참이어야 하는 조건(불변식)을 정하세요.
구조가 비어 있을 때, 가득 찼을 때, 메모리 할당에 실패했을 때를 처리하세요.
각 연산의 복잡도와 메모리 관리를 함께 따져 보세요.

동작 원리 보기

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

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은 노드를 스스로 관리하고, 필요하면 커지며, 어떤 문자열이든 키로 받습니다.

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

C++

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

연습 문제

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

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

챌린지로 연습하기

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

모든 챌린지