C와 C++의 해시 테이블(hash table)
이 레슨에서는 C로 직접 만든 해시 테이블과 C++의 std::unordered_map으로 각 단어가 몇 번 나오는지 셉니다.
소개
어떤 문제를 해결하나요
단어가 각각 몇 번 나오는지 세거나 이름으로 사용자를 찾으려면, 키로 데이터에 빠르게 접근할 수 있어야 합니다. 그때마다 리스트를 처음부터 뒤지면 데이터가 늘어날수록 느려집니다. 해시 테이블(hash table)은 찾는 자리로 거의 곧바로 갑니다.
일상 속 비유
해시 테이블은 ㄱ, ㄴ, ㄷ처럼 첫 글자 탭이 붙은 주소록과 같습니다. 이름만 보면 어느 탭을 펼칠지 알 수 있으므로 주소록 전체를 읽을 필요가 없습니다. 한 탭에 여러 이름이 있으니, 그 쪽만 읽으면서 정확한 이름을 찾습니다.
hash(text)🔤 키 자체로 탭을 계산합니다buckets[bucket]📑 그 탭 뒤의 쪽item->next📝 같은 쪽에 있는 다른 이름들 (체이닝)strcmp(item->key, ...)🔍 정확히 원하는 항목인지 확인합니다해시 테이블은 키와 값의 쌍을 버킷 배열에 저장합니다. 해시 함수로 각 키가 들어갈 버킷을 계산하기 때문에, 조회는 대개 상수 시간에 끝납니다.
핵심 정리
hash는 키의 문자들을 섞어 숫자 하나로 만든 다음, 버킷 인덱스인value % 5를 돌려줍니다.Item마다next포인터가 있어서, 같은 버킷에 들어간 키들은 체인으로 이어집니다.- 단어를 셀 때는 단어를 해시하고, 해당 버킷의 체인을 따라가며
strcmp로 키를 비교합니다. - C++의
std::unordered_map은 해싱, 체이닝, 크기 늘리기를 모두 대신 해 줍니다:++counts[word].
사용하면 좋은 경우
- 단어 빈도처럼 등장 횟수를 셀 때.
- 키로 빠르게 조회할 때: 캐시, 심볼 테이블, 사용자 레코드.
- 중복을 없애거나 어떤 값이 들어 있는지 확인할 때.
필요 없는 경우
- 키를 정렬된 순서로 다뤄야 할 때:
std::map을 쓰거나 키를 정렬하세요. - 아주 작은 데이터 묶음: 배열을 단순히 검색해도 충분히 빠릅니다.
동작 원리 보기
키를 입력하고 저장하거나 찾아보세요. 키는 해시로 버킷 번호가 되므로 프로그램은 올바른 버킷으로 바로 갑니다.
C와 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
#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에서 ==는 문자가 아니라 주소를 비교합니다.
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;
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지