C/C++ 자료 구조

Hash Table

Hash function은 key를 bucket에 매핑하며 collision 처리 전략이 필요합니다.

Hash Table이란?

Hash function은 key를 bucket에 매핑하며 collision 처리 전략이 필요합니다.

Chaining과 unordered_map으로 단어를 셉니다.

중요한 점

연산 전에 invariant를 정의하세요.
비어 있음, 가득 참, 할당 실패를 처리하세요.
시간 복잡도와 ownership을 함께 평가하세요.

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 예제는 bucket에 집중하도록 key를 고정합니다. std::unordered_map은 node를 소유하고 자동 성장하며 임의 string을 받습니다.

구조체와 연산이 분리되고 할당이 명시적입니다.

C++

Class와 container가 invariant와 resource를 관리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

빈 상태와 용량 경계를 테스트하세요.
Cleanup을 구현하고 leak을 확인하세요.
Standard container와 비교하세요.