학습 목표
이번 주차를 마치면 다음을 할 수 있습니다.
- 해시 함수가 문자열을 숫자로 바꾸는 과정을 손으로 따라가고, 좋은 해시와 나쁜 해시가 분포를 어떻게 다르게 만드는지 실험으로 확인할 수 있다
- 체이닝과 개방 주소법 두 방식으로 해시 테이블을 직접 구현하고, 각 연산이 메모리에서 무슨 일을 하는지 그림으로 설명할 수 있다
- 개방 주소법에서 삭제에 묘비(tombstone)가 필요한 이유를 버그를 직접 재현해서 설명할 수 있다
- 로드 팩터가 커질 때 조회 시간이 어떻게 변하는지 측정하고, 동적 리사이징으로 O(1)을 지키는 방법을 구현할 수 있다
- B-트리가 데이터베이스 인덱스의 표준인 이유를 디스크 관점에서 설명하고, 12주차의 편향 트리와 높이를 숫자로 비교할 수 있다
- 트라이로 접두사 검색(자동완성)을 구현할 수 있다
들어가며
파이썬에서 d["apple"] 이라고 치면 값이 바로 나옵니다. 딕셔너리에 항목이 열 개든 천만 개든 걸리는 시간이 거의 같습니다. 자바스크립트의 객체, 자바의 HashMap, Go의 map 도 마찬가지입니다. 현대 언어에서 가장 많이 쓰이는 자료구조가 전부 같은 원리로 돌아갑니다.
그런데 이상하지 않습니까? 12주차에서 우리는 “정렬된 데이터를 찾는 가장 빠른 방법은 O(log n)” 이라고 배웠습니다. 천만 개면 스물세 번은 비교해야 합니다. 그런데 딕셔너리는 몇 번 비교하지도 않고 찾아냅니다. 어떻게 그럴 수 있을까요?
답은 아예 찾지 않는 것입니다. 키를 보고 “이 키는 7번 칸에 있을 것” 이라고 계산해서 7번 칸으로 바로 갑니다. 이번 주의 주인공 해시 테이블이 하는 일이 그것입니다. 마법 같지만 공짜는 아닙니다. 이번 주에는 그 원리(해시 함수), 문제(충돌), 해결책(체이닝, 개방 주소법, 리사이징)을 전부 직접 만들면서 청구서까지 확인합니다.
후반부에는 트리의 고급편 두 가지를 봅니다. 데이터베이스의 심장인 B-트리, 그리고 자동완성의 비밀인 트라이입니다. 둘 다 “12주차의 이진 트리로는 안 되는 일”을 하려고 만들어진 트리입니다.
이번 주차 예제 코드는 모두 week13/examples/ 와 week13/projects/ 에 있습니다. 글에 나오는 코드는 그 파일의 전체 내용 그대로이고, 실행 결과도 글을 쓰면서 실제로 돌린 것입니다. 컴파일은 언제나처럼 합니다.
$ cd week13
$ make # 전부 한 번에 build/ 아래로
$ gcc -Wall -Wextra -std=c11 -g examples/hash_functions.c -o build/hash_functions # 하나만
이 글에는 “바꾸면 어떻게 될까” 실험이 많이 나옵니다. 실험 코드는 예제 파일을 한두 줄 고친 것이라 글에 그 부분만 보였습니다. 결과를 먼저 예상하고, 직접 고쳐서 돌려 보고, 예상과 비교하세요. 해시 테이블은 “동작은 하는데 틀린” 버그가 유난히 많은 자료구조라서, 버그를 일부러 내 보는 것이 가장 좋은 공부입니다.
1. 해시 함수: 마법의 출발점
1.1 아이디어: 키를 인덱스로 바꾸자
배열의 강점을 떠올려 보세요. arr[5] 는 배열에 요소가 10개든 1천만 개든 한 번에 접근합니다. 6주차에서 봤듯 “시작 주소 + 5 × 요소 크기” 라는 곱셈 한 번이면 주소가 나오기 때문입니다.
문제는 우리가 찾고 싶은 것이 인덱스가 아니라는 점입니다. "apple" 의 가격, "kim" 의 전화번호처럼 의미 있는 키로 찾고 싶습니다. 그래서 지금까지는 배열을 처음부터 훑거나(O(n)), 정렬해 두고 반씩 잘라 가거나, 트리를 타고 내려갔습니다(O(log n)).
해시 테이블의 아이디어는 놀랍도록 단순합니다. 키를 인덱스로 바꿔 주는 함수를 하나 끼워 넣습니다.
"apple" ──[해시 함수]──▶ 210706734647 ──[% 버킷 수 8]──▶ 7
│
table[7] 에 저장하거나 조회 ◀┘
키를 숫자로 바꾸고(해시), 배열 크기로 나눈 나머지(%)를 인덱스로 씁니다. 이제 저장도 조회도 배열 접근 한 번입니다. 배열의 O(1)을 문자열 키에도 쓸 수 있게 된 것입니다.
배열의 각 칸을 버킷(bucket) 이라고 부릅니다. 양동이에 물건을 던져 넣는 그림에서 온 이름입니다. 그리고 키를 숫자로 바꾸는 함수를 해시 함수(hash function) 라고 합니다. hash 는 “잘게 다지다” 라는 뜻으로, 해시 브라운(감자를 다져 부친 요리)의 그 해시입니다. 문자열을 잘게 다져 숫자 하나로 뭉친다는 뜻입니다.
1.2 손으로 계산해 보기: djb2
이번 주 내내 쓸 해시 함수는 djb2 입니다. 1991년에 Daniel J. Bernstein 이 발표한 것으로, 다섯 줄이 전부입니다.
unsigned long hash_djb2(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = (unsigned char)*key++)) {
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
return hash;
}
한 줄씩 봅시다.
unsigned long hash = 5381;: 시작값입니다. 0으로 시작하면 어떨까요? 첫 글자가'a'든'b'든0 * 33 + c = c라서, 첫 글자의 영향이 33배로 커지는 효과를 못 받습니다. 5381은 Bernstein 이 실험해서 분포가 좋았다고 밝힌 소수입니다. 왜 하필 5381이냐에 대한 수학적 증명은 없고, “잘 되더라” 가 답입니다. 실무 해시 함수에는 이런 경험적 상수가 많습니다.int c;와while ((c = (unsigned char)*key++)): 글자를 하나씩 꺼냅니다.*key++는 “지금 글자를 읽고 포인터를 다음으로” 입니다(6주차). 읽은 글자를c에 대입하고, 그 대입 결과가 0(문자열 끝의\0)이면 반복이 끝납니다. 괄호를 두 겹 쓴 것은 “비교==가 아니라 대입=이 맞다” 고 컴파일러에게 알려 경고를 끄기 위해서입니다. 3주차의if (a = 5)경고를 기억하시죠.(unsigned char): 이 캐스팅을 빼면 한글이나 특수문자에서 문제가 생깁니다. x86 리눅스의char는 부호가 있어서 128 이상인 바이트(한글은 전부 그렇습니다)가 음수로 읽힙니다.c가 음수면hash + c가 줄어들고, 플랫폼마다 결과가 달라집니다.(unsigned char)로 먼저 바꾸면 항상 0~255 입니다. 4주차에isalpha에(unsigned char)를 넘기던 것과 같은 이유입니다.hash = ((hash << 5) + hash) + c;:hash << 5는hash * 32이고(3주차 비트 연산), 거기에hash를 더하면hash * 33입니다. 곱셈이 느리던 시절의 최적화이고, 요즘 컴파일러는hash * 33이라고 써도 같은 기계어를 만듭니다. 원문 모양을 존중해 그대로 두었습니다.unsigned long: 64비트라서 곱셈을 거듭하면 금방 넘칩니다. 2주차에서 부호 있는 정수의 오버플로는 정의되지 않은 동작이라고 배웠습니다. 하지만 부호 없는 정수의 오버플로는 정의된 동작입니다. 2⁶⁴ 으로 나눈 나머지가 됩니다. 해시 함수가unsigned를 쓰는 이유가 바로 이것입니다. 넘쳐도 되고, 오히려 넘치면서 비트가 잘 섞입니다.
이 다섯 줄이 정말로 문자열을 숫자로 바꾸는지 손으로 따라가 봅시다. "cat" 입니다. 'c' 는 아스키 99, 'a' 는 97, 't' 는 116 입니다.
| 단계 | 글자 | 계산 | hash |
|---|---|---|---|
| 시작 | 5,381 | ||
| 1 | 'c' (99) |
5,381 × 33 + 99 | 177,672 |
| 2 | 'a' (97) |
177,672 × 33 + 97 | 5,863,273 |
| 3 | 't' (116) |
5,863,273 × 33 + 116 | 193,488,125 |
djb2("cat") = 193488125 입니다. 버킷이 8개라면 193488125 % 8 = 5, 5번 칸입니다. 계산기로 직접 확인해 보세요. 세 글자에 벌써 1억 9천만이 됐습니다. 다섯 글자 "apple" 은 2,107억이 되고, 여섯 글자부터는 조 단위입니다.
여기서 중요한 성질 하나가 보입니다. 첫 글자가 결과에 미치는 영향이 가장 큽니다. 'c' 는 그 뒤에 33이 두 번 더 곱해지니까요. 그래서 시작값이 0이면 안 됩니다. 5381 이 33³ 만큼 곱해져 모든 글자 앞에 깔리기 때문에, 짧은 문자열도 큰 숫자가 됩니다.
1.3 좋은 해시, 나쁜 해시
이 마법의 성패는 전적으로 해시 함수에 달렸습니다. 좋은 해시 함수의 조건은 세 가지입니다.
- 결정적(deterministic): 같은 키는 항상 같은 값이어야 합니다. 저장할 때 7번, 찾을 때 3번이면 영영 못 찾습니다. 그래서 해시 함수 안에 난수나 현재 시각이 끼어들면 안 됩니다.
- 균등 분포(uniform): 다른 키는 최대한 다른 값이 나와야 합니다. 한 버킷에 몰리면 그 버킷이 긴 줄이 되어 O(1)이 무너집니다.
- 빠름: 조회할 때마다 호출되는 함수라서, 해시 계산이 느리면 배보다 배꼽이 큽니다.
1번과 3번은 코드만 봐도 알 수 있습니다. djb2 는 난수를 안 쓰고, 글자 수만큼만 반복합니다. 문제는 2번입니다. 분포가 좋은지는 돌려 봐야 압니다. 그래서 다음 예제는 네 가지 해시 함수로 과일 이름 32개를 버킷 16개에 나눠 담고, 어느 버킷에 몇 개씩 들어갔는지 세어 봅니다.
examples/hash_functions.c:
/*
* hash_functions.c - 해시 함수의 품질 비교
* 13주차: 해시 테이블과 고급 트리
*
* 해시 함수: 임의 크기의 키(문자열 등)를 고정 범위의 숫자로 바꾸는 함수.
* 좋은 해시 함수의 조건:
* 1. 같은 키 -> 항상 같은 값 (결정적)
* 2. 다른 키 -> 최대한 다른 값 (골고루 분포)
* 3. 빠르다
*
* 나쁜 해시와 좋은 해시가 실제로 어떻게 다른지
* 같은 데이터로 분포를 비교해 봅니다.
*/
#include <stdio.h>
#include <string.h>
#define BUCKETS 16 /* 분포를 관찰할 버킷 수 */
/* 나쁜 해시 1: 첫 글자만 사용
* "apple", "avocado", "apricot" 전부 같은 버킷! */
unsigned long hash_first_char(const char *key) {
return (unsigned long)key[0];
}
/* 나쁜 해시 2: 글자 합
* "abc"와 "cba"가 같은 값 (순서 무시) */
unsigned long hash_sum(const char *key) {
unsigned long sum = 0;
while (*key) sum += (unsigned char)*key++;
return sum;
}
/* 좋은 해시 1: djb2 (Daniel J. Bernstein)
* hash * 33 + c 를 반복. 단순한데 분포가 훌륭해서 실무에서 널리 사용 */
unsigned long hash_djb2(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = (unsigned char)*key++)) {
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
return hash;
}
/* 좋은 해시 2: FNV-1a
* XOR 후 소수 곱하기. 짧은 키에 특히 강하다 */
unsigned long hash_fnv1a(const char *key) {
unsigned long hash = 14695981039346656037UL; /* FNV offset basis */
while (*key) {
hash ^= (unsigned char)*key++;
hash *= 1099511628211UL; /* FNV prime */
}
return hash;
}
/* 분포 실험: 단어들을 버킷에 나눠 담고 히스토그램 출력 */
void analyze(const char *name,
unsigned long (*hash)(const char *),
const char *words[], int count) {
int bucket[BUCKETS] = {0};
for (int i = 0; i < count; i++) {
bucket[hash(words[i]) % BUCKETS]++;
}
/* 충돌 정도 측정: 이상적이면 모든 버킷에 count/BUCKETS개씩 */
int max = 0, empty = 0;
for (int i = 0; i < BUCKETS; i++) {
if (bucket[i] > max) max = bucket[i];
if (bucket[i] == 0) empty++;
}
printf("%-16s", name);
for (int i = 0; i < BUCKETS; i++) {
printf("%2d ", bucket[i]);
}
printf("| 최대 %2d, 빈 버킷 %2d\n", max, empty);
}
int main(void) {
/* 실험 데이터: 과일 이름 32개 (a로 시작하는 것이 많다 - 현실적 편향) */
const char *words[] = {
"apple", "apricot", "avocado", "banana", "blueberry", "blackberry",
"cherry", "coconut", "cranberry", "date", "dragonfruit", "durian",
"elderberry", "fig", "grape", "grapefruit", "guava", "kiwi",
"lemon", "lime", "lychee", "mango", "melon", "nectarine",
"orange", "papaya", "peach", "pear", "pineapple", "plum",
"raspberry", "strawberry",
};
int count = sizeof(words) / sizeof(words[0]);
printf("단어 %d개를 버킷 %d개에 분배 (이상적: 버킷당 %d개)\n\n",
count, BUCKETS, count / BUCKETS);
printf("%-16s", "해시 함수");
for (int i = 0; i < BUCKETS; i++) printf("%2d ", i);
printf("\n");
printf("--------------------------------------------------"
"--------------------------\n");
analyze("첫 글자만", hash_first_char, words, count);
analyze("글자 합", hash_sum, words, count);
analyze("djb2", hash_djb2, words, count);
analyze("FNV-1a", hash_fnv1a, words, count);
printf("\n관찰:\n");
printf("1. '첫 글자만': a로 시작하는 단어들이 한 버킷에 몰린다\n");
printf("2. '글자 합': 좀 낫지만 비슷한 길이 단어끼리 뭉친다\n");
printf("3. djb2/FNV-1a: 골고루 퍼진다 -> 충돌이 적다 -> 빠르다\n");
printf("\n해시값 자체도 확인:\n");
printf("djb2(\"apple\") = %lu\n", hash_djb2("apple"));
printf("djb2(\"apples\") = %lu (한 글자 차이로 완전히 다른 값)\n",
hash_djb2("apples"));
printf("djb2(\"apple\") = %lu (같은 키는 항상 같은 값)\n",
hash_djb2("apple"));
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/hash_functions.c -o build/hash_functions
$ ./build/hash_functions
단어 32개를 버킷 16개에 분배 (이상적: 버킷당 2개)
해시 함수 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
----------------------------------------------------------------------------
첫 글자만 5 3 4 4 3 1 1 3 0 0 0 1 3 2 1 1 | 최대 5, 빈 버킷 3
글자 합 1 3 3 1 2 2 1 1 2 2 2 3 3 2 3 1 | 최대 3, 빈 버킷 0
djb2 3 3 2 3 1 1 3 3 1 2 2 1 1 2 2 2 | 최대 3, 빈 버킷 0
FNV-1a 4 5 1 0 2 2 1 2 1 2 1 2 4 2 1 2 | 최대 5, 빈 버킷 1
관찰:
1. '첫 글자만': a로 시작하는 단어들이 한 버킷에 몰린다
2. '글자 합': 좀 낫지만 비슷한 길이 단어끼리 뭉친다
3. djb2/FNV-1a: 골고루 퍼진다 -> 충돌이 적다 -> 빠르다
해시값 자체도 확인:
djb2("apple") = 210706734647
djb2("apples") = 6953322243466 (한 글자 차이로 완전히 다른 값)
djb2("apple") = 210706734647 (같은 키는 항상 같은 값)
해시 함수 비교
1.4 결과 읽기
표의 각 열은 버킷 번호이고, 칸의 숫자는 그 버킷에 떨어진 단어 수입니다. 32개를 16칸에 나누니 이상적으로는 칸마다 2개입니다.
“첫 글자만” 해시부터 보겠습니다. key[0] 을 그대로 돌려주니, 'a'(97)로 시작하는 apple, apricot, avocado 는 전부 97 % 16 = 1 번 버킷입니다. 그런데 표에서는 0번 버킷이 5개로 가장 많습니다. 'p' 는 112 이고 112 % 16 = 0 이라서, papaya, peach, pear, pineapple, plum 다섯 개가 0번에 몰린 것입니다. 빈 버킷도 3개입니다. 8, 9, 10번인데, 아스키로 치면 'h'(104), 'i'(105), 'j'(106) 로 시작하는 단어가 목록에 없기 때문입니다.
중요한 것은 이게 현실적인 실패라는 점입니다. 실제 데이터는 늘 편향돼 있습니다. 사람 이름, URL, 파일 경로, 상품 코드 모두 특정 글자로 시작하는 것이 훨씬 많습니다. 해시 함수의 임무는 그 편향을 부숴 주는 것입니다.
“글자 합” 해시는 최대 3, 빈 버킷 0으로 표만 보면 나쁘지 않습니다. 하지만 이 함수에는 표에 안 보이는 결함이 있습니다. 덧셈은 순서를 잊습니다.
글자합: abc=294 cba=294 bac=294
djb2: abc=193485963 cba=193488139
"abc", "cba", "bac" 가 전부 294 입니다(97 + 98 + 99). 애너그램(글자 순서만 바꾼 단어)이 무조건 충돌합니다. "listen" 과 "silent", "post" 와 "stop" 이 같은 버킷에 떨어집니다. djb2 는 곱셈이 끼어 있어 순서가 바뀌면 값이 달라집니다.
또 하나, 값의 범위가 좁습니다. 영어 소문자는 97~122 이니 5글자 단어의 합은 485~610 사이입니다. 가능한 값이 126가지뿐이라 단어가 조금만 많아져도 뭉칩니다.
djb2 는 최대 3, 빈 버킷 0으로 고르게 퍼졌습니다. 그리고 출력 마지막 세 줄을 보세요. "apple" 과 "apples" 는 한 글자 차이인데 값이 완전히 다릅니다(2,107억 대 6조). 한 글자의 차이가 이후 모든 곱셈에 눈덩이처럼 번지기 때문입니다. 이것을 눈사태 효과(avalanche effect) 라고 부르고, 좋은 해시 함수의 표식입니다. 그리고 "apple" 을 두 번 계산해서 같은 값이 나오는 것으로 1번 조건(결정적)도 확인했습니다.
FNV-1a 는 XOR 을 한 뒤 큰 소수를 곱하는 방식입니다. 이 실험에서는 최대 5로 djb2 보다 나빠 보이지만, 표본이 32개뿐이라 생긴 우연입니다. 단어를 3,200개로 늘리면 둘의 차이는 사라집니다. 둘 다 실무에서 검증된 해시라 어느 쪽을 써도 좋고, 이번 주는 더 짧은 djb2 로 갑니다.
함수 포인터가 또 나왔습니다.
analyze함수는unsigned long (*hash)(const char *)매개변수로 해시 함수를 받습니다. 덕분에 해시 함수 네 개를 똑같은 실험 코드로 비교할 수 있었습니다. 7주차에서 배운 “동작을 인자로 넘기기” 가 실험 도구로 쓰인 장면입니다.
1.5 실험: 버킷 수도 분포를 바꾼다
해시 함수만 좋으면 끝일까요? % 버킷 수 도 분포에 관여합니다. 현실에서 아주 흔한 키인 순차적인 ID 로 실험해 봅시다. user0001 부터 user0064 까지 64개를 djb2 로 해시한 뒤, 버킷 수를 16, 17, 32 로 바꿔 가며 나눠 담습니다.
user0001..user0064, 64개
djb2 % 16 : 3 2 1 0 0 2 3 4 5 6 7 7 7 7 6 4
djb2 % 17 : 4 5 5 5 6 6 6 6 5 4 3 2 1 0 1 2 3
djb2 % 32 : 0 0 0 0 0 2 3 4 5 6 7 7 7 7 6 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0
글자합 % 16: 2 3 4 5 6 7 7 7 7 6 4 3 2 1 0 0
% 16 은 3번, 4번 버킷이 비고 11~13번에 7개씩 몰렸습니다. % 32 는 더 심해서 32칸 중 17칸이 비었습니다. 그런데 % 17 은 훨씬 고릅니다. 왜일까요?
16과 32는 2의 거듭제곱입니다. x % 16 은 x 의 아래쪽 4비트만 보는 것과 같습니다(3주차에서 배운 비트 AND 로 쓰면 x & 15 입니다). 그런데 user0001, user0002, … 는 마지막 한 글자만 다르고, 마지막 글자는 곱셈을 한 번도 안 거친 채 그냥 더해집니다(1.2절의 표를 떠올리세요. 마지막 글자는 + 116 처럼 그대로 붙습니다). 그래서 이 키들의 해시값은 아래쪽 비트가 단조롭게 변하고, 2의 거듭제곱으로 나누면 그 단조로움이 그대로 드러납니다. 17 같은 소수로 나누면 모든 비트가 나머지에 관여해서 섞입니다.
그래서 교과서는 “버킷 수는 소수로” 라고 가르치고, C++ 표준 라이브러리의 unordered_map 이 실제로 그렇게 합니다. 반면 파이썬의 dict 나 자바의 HashMap 은 2의 거듭제곱을 씁니다. % 16 대신 & 15 라는 비트 연산 한 번으로 끝나서 훨씬 빠르기 때문인데, 대신 위와 같은 문제를 막으려고 해시값의 위쪽 비트를 아래로 한 번 더 섞어 줍니다(자바의 hash ^ (hash >>> 16) 이 그 코드입니다). 해시 함수와 버킷 수는 한 쌍이라는 것, 그리고 “잘 섞였다” 는 말이 아래쪽 비트까지 포함한다는 것을 기억해 두세요.
이번 주 예제들은 설명을 단순하게 하려고 2의 거듭제곱 버킷과 % 를 씁니다. 과일 이름처럼 서로 다른 키에서는 djb2 가 충분히 잘 섞어 주기 때문입니다.
2. 충돌 처리 1: 체이닝
2.1 충돌은 피할 수 없다
아무리 좋은 해시 함수를 써도 충돌(collision, 다른 키가 같은 버킷에 배정되는 것) 은 일어납니다. 함수의 품질 문제가 아니라 수학입니다. 가능한 문자열은 무한한데 버킷은 유한하니까요. 버킷이 16개면 17개째 키부터는 반드시 누군가와 겹칩니다. 비둘기 17마리를 집 16개에 넣으면 어느 집에는 두 마리가 들어가야 한다는 비둘기집 원리입니다.
게다가 우리 직관보다 훨씬 빨리 충돌합니다. 생일 역설을 떠올려 보세요. 1년은 365일인데, 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘습니다. 해시도 같습니다. 버킷 1,000개에 키를 넣을 때 “적어도 한 쌍은 충돌할 확률” 을 계산하면 이렇습니다.
| 키 개수 | 충돌 확률 |
|---|---|
| 10 | 4.4% |
| 20 | 17.4% |
| 30 | 35.6% |
| 39 | 52.8% |
| 50 | 71.2% |
버킷의 4%만 채워도 충돌 확률이 절반을 넘습니다. 계산은 “n개가 전부 다른 칸에 떨어질 확률” 을 1에서 뺀 것으로, 1,000개 중 1개를 고르고 나면 다음 키가 안 겹칠 확률은 999/1000, 그다음은 998/1000 을 계속 곱해 나가면 됩니다.
그러니 질문은 “충돌을 어떻게 막을까” 가 아니라 “충돌을 어떻게 처리할까” 입니다. 답은 크게 두 갈래이고, 먼저 볼 것이 체이닝입니다.
2.2 체이닝: 버킷마다 줄을 세운다
체이닝(chaining) 은 각 버킷을 연결 리스트로 만들어, 충돌한 항목들을 사슬(chain)처럼 매달아 두는 방식입니다. 10주차에 만든 연결 리스트가 여기서 또 일합니다.
이번 예제는 과일 일곱 개의 가격을 버킷 8개짜리 해시맵에 넣습니다. 충돌이 눈에 잘 보이도록 버킷을 일부러 적게 뒀습니다. 코드를 보기 전에 손으로 먼저 해 봅시다. 1.2절처럼 djb2 를 계산하고 8로 나눈 나머지를 구하면 이렇습니다.
| 순서 | 키 | djb2 | % 8 |
|---|---|---|---|
| 1 | apple | 210,706,734,647 | 7 |
| 2 | banana | 6,953,343,506,470 | 6 |
| 3 | cherry | 6,953,390,638,546 | 2 |
| 4 | grape | 210,713,905,844 | 4 |
| 5 | mango | 210,720,424,311 | 7 |
| 6 | orange | 6,953,871,973,985 | 1 |
| 7 | peach | 210,724,111,526 | 6 |
7개를 8칸에 넣는데 벌써 겹칩니다. apple 과 mango 가 7번, banana 와 peach 가 6번입니다. 이 순서대로 넣으면 테이블은 이렇게 자랍니다. 새 항목은 사슬의 머리에 끼우는 것으로 하겠습니다(이유는 곧 나옵니다).
apple 삽입 (7번) 버킷[7]: [apple=1500] → NULL
banana 삽입 (6번) 버킷[6]: [banana=3000] → NULL
cherry 삽입 (2번) 버킷[2]: [cherry=8000] → NULL
grape 삽입 (4번) 버킷[4]: [grape=5000] → NULL
mango 삽입 (7번) 충돌! 버킷[7]: [mango=4500] → [apple=1500] → NULL
orange 삽입 (1번) 버킷[1]: [orange=2000] → NULL
peach 삽입 (6번) 충돌! 버킷[6]: [peach=6000] → [banana=3000] → NULL
조회는 버킷에 도착한 뒤 사슬을 따라가며 키를 하나씩 비교합니다. mango 를 찾으면 7번 버킷의 첫 항목이 바로 mango 이니 비교 한 번, apple 은 mango 를 지나 두 번째에서 찾으니 비교 두 번입니다. 사슬이 짧으면(평균 1개 안팎) 사실상 O(1)입니다.
이제 이것을 코드로 봅니다.
examples/hash_chaining.c:
/*
* hash_chaining.c - 체이닝 해시 테이블
* 13주차: 해시 테이블과 고급 트리
*
* 충돌(다른 키가 같은 버킷에 배정)은 피할 수 없습니다.
* 체이닝: 각 버킷을 연결 리스트로 만들어 충돌한 키들을 매달아 둔다.
* (10주차 연결 리스트가 여기서 또 일합니다!)
*
* 문자열 키 -> 정수 값 해시맵을 구현합니다.
* insert / get / remove / 전체 출력
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKETS 8 /* 일부러 작게: 충돌을 관찰하기 위해 */
typedef struct Entry {
char *key; /* 동적 할당 복사본 */
int value;
struct Entry *next; /* 같은 버킷의 다음 항목 */
} Entry;
typedef struct {
Entry *bucket[BUCKETS];
size_t count; /* 전체 항목 수 */
} HashMap;
unsigned long hash_djb2(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = (unsigned char)*key++)) {
hash = ((hash << 5) + hash) + c;
}
return hash;
}
void map_init(HashMap *m) {
memset(m->bucket, 0, sizeof(m->bucket));
m->count = 0;
}
/* 삽입 또는 갱신. 성공 1, 실패 0 */
int map_put(HashMap *m, const char *key, int value) {
size_t idx = hash_djb2(key) % BUCKETS;
/* 이미 있는 키면 값만 갱신 */
for (Entry *e = m->bucket[idx]; e != NULL; e = e->next) {
if (strcmp(e->key, key) == 0) {
e->value = value;
return 1;
}
}
/* 새 항목을 버킷 리스트 머리에 삽입 (O(1)) */
Entry *e = malloc(sizeof(Entry));
if (e == NULL) return 0;
e->key = malloc(strlen(key) + 1);
if (e->key == NULL) {
free(e);
return 0;
}
strcpy(e->key, key);
e->value = value;
e->next = m->bucket[idx];
m->bucket[idx] = e;
m->count++;
return 1;
}
/* 조회. 찾으면 1과 *out, 없으면 0 */
int map_get(const HashMap *m, const char *key, int *out) {
size_t idx = hash_djb2(key) % BUCKETS;
for (Entry *e = m->bucket[idx]; e != NULL; e = e->next) {
if (strcmp(e->key, key) == 0) { /* 해시가 같아도 키 확인! */
if (out != NULL) *out = e->value;
return 1;
}
}
return 0;
}
/* 삭제: 리스트에서 빼고 key와 Entry 모두 해제 */
int map_remove(HashMap *m, const char *key) {
size_t idx = hash_djb2(key) % BUCKETS;
Entry *prev = NULL;
for (Entry *e = m->bucket[idx]; e != NULL; prev = e, e = e->next) {
if (strcmp(e->key, key) == 0) {
if (prev == NULL) m->bucket[idx] = e->next;
else prev->next = e->next;
free(e->key);
free(e);
m->count--;
return 1;
}
}
return 0;
}
void map_free(HashMap *m) {
for (size_t i = 0; i < BUCKETS; i++) {
Entry *e = m->bucket[i];
while (e != NULL) {
Entry *next = e->next;
free(e->key);
free(e);
e = next;
}
}
map_init(m);
}
/* 내부 구조 출력: 어떤 키들이 충돌해서 사슬이 됐는지 보인다 */
void map_show(const HashMap *m) {
for (size_t i = 0; i < BUCKETS; i++) {
printf(" 버킷[%zu]: ", i);
if (m->bucket[i] == NULL) {
printf("(비어 있음)\n");
continue;
}
for (Entry *e = m->bucket[i]; e != NULL; e = e->next) {
printf("[%s=%d] -> ", e->key, e->value);
}
printf("NULL\n");
}
}
int main(void) {
HashMap m;
map_init(&m);
printf("=== 과일 가격표를 해시맵에 저장 (버킷 %d개) ===\n", BUCKETS);
map_put(&m, "apple", 1500);
map_put(&m, "banana", 3000);
map_put(&m, "cherry", 8000);
map_put(&m, "grape", 5000);
map_put(&m, "mango", 4500);
map_put(&m, "orange", 2000);
map_put(&m, "peach", 6000);
map_show(&m);
printf(" (같은 버킷에 여러 항목 = 충돌이 사슬로 매달린 것)\n");
printf("\n=== 조회 ===\n");
int price;
if (map_get(&m, "cherry", &price)) printf("cherry: %d원\n", price);
if (!map_get(&m, "durian", &price)) printf("durian: 없음\n");
printf("\n=== 갱신 (같은 키에 다시 put) ===\n");
map_put(&m, "apple", 1200);
map_get(&m, "apple", &price);
printf("apple 할인 후: %d원 (항목 수는 그대로 %zu)\n", price, m.count);
printf("\n=== 삭제 ===\n");
map_remove(&m, "banana");
printf("banana 삭제 후: %s\n",
map_get(&m, "banana", NULL) ? "아직 있음?!" : "없음 (정상)");
map_show(&m);
map_free(&m);
printf("\n전체 해제 완료 (누수 0)\n");
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/hash_chaining.c -o build/hash_chaining
$ ./build/hash_chaining
=== 과일 가격표를 해시맵에 저장 (버킷 8개) ===
버킷[0]: (비어 있음)
버킷[1]: [orange=2000] -> NULL
버킷[2]: [cherry=8000] -> NULL
버킷[3]: (비어 있음)
버킷[4]: [grape=5000] -> NULL
버킷[5]: (비어 있음)
버킷[6]: [peach=6000] -> [banana=3000] -> NULL
버킷[7]: [mango=4500] -> [apple=1500] -> NULL
(같은 버킷에 여러 항목 = 충돌이 사슬로 매달린 것)
=== 조회 ===
cherry: 8000원
durian: 없음
=== 갱신 (같은 키에 다시 put) ===
apple 할인 후: 1200원 (항목 수는 그대로 7)
=== 삭제 ===
banana 삭제 후: 없음 (정상)
버킷[0]: (비어 있음)
버킷[1]: [orange=2000] -> NULL
버킷[2]: [cherry=8000] -> NULL
버킷[3]: (비어 있음)
버킷[4]: [grape=5000] -> NULL
버킷[5]: (비어 있음)
버킷[6]: [peach=6000] -> NULL
버킷[7]: [mango=4500] -> [apple=1200] -> NULL
전체 해제 완료 (누수 0)
손으로 그린 그림과 정확히 같습니다. 버킷 6과 7에 사슬이 생겼고, 나중에 넣은 mango 와 peach 가 앞에 있습니다.
2.3 코드 해설
자료구조부터 봅시다.
typedef struct Entry {
char *key; /* 동적 할당 복사본 */
int value;
struct Entry *next; /* 같은 버킷의 다음 항목 */
} Entry;
typedef struct {
Entry *bucket[BUCKETS];
size_t count; /* 전체 항목 수 */
} HashMap;
Entry 는 10주차의 연결 리스트 노드와 똑같은 모양입니다. 다른 점은 key 를 함께 들고 다닌다는 것뿐입니다. HashMap 은 그 리스트의 머리(head) 포인터를 버킷 수만큼 가진 배열입니다. 즉 해시 테이블 = 연결 리스트 여러 개를 담은 배열입니다. Entry *bucket[BUCKETS] 를 7주차의 선언 읽기 규칙으로 읽으면 “Entry 를 가리키는 포인터 8개짜리 배열” 입니다.
초기화(map_init) 는 memset 으로 포인터 배열을 0으로 채웁니다. 6주차에서 말했듯 NULL 은 0이라서, 이 한 줄로 “모든 버킷이 비어 있음” 이 됩니다.
삽입(map_put) 에서 눈여겨볼 곳은 세 군데입니다.
/* 이미 있는 키면 값만 갱신 */
for (Entry *e = m->bucket[idx]; e != NULL; e = e->next) {
if (strcmp(e->key, key) == 0) {
e->value = value;
return 1;
}
}
먼저 사슬을 훑어 같은 키가 있는지 확인합니다. 이 검사를 빼면 같은 키가 두 번 저장되어, 조회할 때마다 먼저 발견된 쪽이 나오는 유령 버그가 생깁니다. 해시맵은 “키 하나에 값 하나” 가 약속이니 반드시 필요한 단계입니다. 실행 결과의 “갱신” 부분에서 apple 을 1200원으로 다시 넣었는데 항목 수가 7 그대로인 것이 이 검사 덕분입니다.
e->key = malloc(strlen(key) + 1);
if (e->key == NULL) {
free(e); /* 앞서 할당한 Entry를 되돌린다 */
return 0;
}
strcpy(e->key, key);
키를 복사해서 저장합니다. 호출자가 넘긴 포인터를 그냥 e->key = key; 로 가리키면 어떻게 될까요? 잠시 뒤 실험에서 직접 봅니다. strlen(key) + 1 의 +1 은 4주차부터 계속 나온 \0 자리입니다.
할당 실패 처리도 눈여겨보세요. e->key 할당이 실패하면 이미 확보한 e 를 free 한 뒤 실패를 돌려줍니다. 중간에 실패했을 때 앞서 잡은 자원을 되돌리는 것, 이것이 C에서 메모리 누수를 막는 기본기입니다(7주차).
e->next = m->bucket[idx]; /* 새 항목이 기존 머리를 가리키고 */
m->bucket[idx] = e; /* 새 항목이 새 머리가 된다 */
새 항목을 사슬의 머리에 넣습니다. 꼬리에 넣으려면 끝까지 걸어가야 하지만 머리는 O(1)입니다. 대신 삽입 순서와 출력 순서가 반대가 됩니다. 2.2절 그림에서 mango 가 apple 앞에 온 이유입니다.
조회(map_get) 의 핵심은 딱 한 줄입니다.
if (strcmp(e->key, key) == 0) { /* 해시가 같아도 키 확인! */
버킷에 도착했다고 끝이 아닙니다. 같은 버킷 ≠ 같은 키입니다. 충돌한 다른 키일 수 있으니 반드시 strcmp 로 확인해야 합니다. 이것도 실험으로 확인합니다.
삭제(map_remove) 는 10주차 연결 리스트 삭제와 똑같습니다. 앞 노드(prev)를 따라다니다가 찾으면 연결을 건너뛰게 만들고, key 와 Entry 둘 다 해제합니다.
if (prev == NULL) m->bucket[idx] = e->next; /* 머리를 지우는 경우 */
else prev->next = e->next; /* 중간/꼬리를 지우는 경우 */
free(e->key); /* 할당한 것이 둘이니 해제도 둘 */
free(e);
malloc 을 두 번 했으면 free 도 두 번입니다. free(e) 만 하고 free(e->key) 를 잊는 실수가 흔한데, 그것이 전형적인 메모리 누수입니다. 게다가 free(e) 를 먼저 하면 e->key 를 읽을 수 없게 되니 순서도 중요합니다. 반드시 안쪽부터 해제하세요. map_free 에서 Entry *next = e->next; 로 다음 노드를 미리 저장하는 것도 같은 이유입니다. free(e) 뒤에 e->next 를 읽으면 7주차에서 본 해제 후 사용(use-after-free)입니다.
메모리 누수가 정말 없는지는 직접 확인합니다.
$ valgrind --leak-check=full ./build/hash_chaining
...
==12345== HEAP SUMMARY:
==12345== in use at exit: 0 bytes in 0 blocks
==12345== All heap blocks were freed -- no leaks are possible
==12345== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
malloc 을 14번(항목 7개 × 키와 노드) 했고 free 도 14번이라 남은 블록이 0입니다.
2.4 실험: 키 비교를 빼면?
“같은 버킷이면 같은 키겠지” 하고 strcmp 를 생략하면 어떻게 될까요? map_get 의 if (strcmp(e->key, key) == 0) 을 if (1) 로 바꾸고, 과일 일곱 개를 넣은 뒤 다섯 개를 조회해 봤습니다.
apple(버킷 7) 조회: 4500원
mango(버킷 7) 조회: 4500원
banana(버킷 6) 조회: 6000원
kiwi(버킷 1) 조회: 2000원
durian(버킷 0) 조회: 없음
apple 을 찾았는데 mango 의 가격 4500원이 나옵니다. 7번 버킷의 첫 항목이 mango 이기 때문입니다. banana 도 peach 의 가격을 돌려줍니다. 더 무서운 것은 넣은 적도 없는 kiwi 가 “2000원” 으로 나온다는 점입니다. kiwi 의 버킷 1에 orange 가 있어서, 사슬의 첫 항목을 그냥 돌려준 것입니다. durian 은 0번 버킷이 비어 있어서 우연히 “없음” 이 나왔을 뿐입니다.
이 버그의 무서운 점은 테스트 데이터가 적으면 통과한다는 것입니다. 키 3개를 버킷 64개에 넣으면 충돌이 없어서 모든 테스트가 성공합니다. 운영에 올라가서 데이터가 쌓인 뒤에야 엉뚱한 값이 나오기 시작합니다.
2.5 실험: 키를 복사하지 않으면?
이번에는 map_put 에서 malloc 과 strcpy 를 빼고 e->key = (char *)key; 로 호출자의 포인터를 그대로 저장해 봅니다. 그리고 호출하는 쪽에서 버퍼 하나를 재사용합니다. fgets 로 한 줄씩 읽어 넣는 프로그램이 딱 이 모양입니다.
char buf[32];
strcpy(buf, "apple"); map_put(&m, buf, 1500);
strcpy(buf, "banana"); map_put(&m, buf, 3000); /* 같은 버퍼를 재사용 */
map_show(&m);
버킷[6]: [banana=3000] -> NULL
버킷[7]: [banana=1500] -> NULL
apple 조회: 없음!
banana 조회: 발견
7번 버킷에 banana 가 1500원으로 들어 있습니다. apple 을 넣을 때 저장한 포인터가 buf 를 가리키는데, 그 뒤에 buf 의 내용을 “banana” 로 덮어썼으니 테이블 속 키도 함께 바뀐 것입니다. 해시값은 apple 기준으로 계산했으니 7번 버킷에 있는데, 키 문자열은 banana 라서 apple 을 찾으면 없다고 나옵니다. 데이터가 있는데 영영 못 찾는 상태입니다. 테이블이 키를 소유하려면 복사본을 가져야 합니다.
2.6 체이닝의 성능: 사슬 길이가 전부다
체이닝의 조회 비용은 사슬 길이가 정합니다. 사슬이 평균 1개면 O(1)이고, 모든 키가 한 버킷에 몰리면 그냥 연결 리스트라서 O(n)입니다. 그 사이는 어떨까요? 버킷 수를 1,024개로 고정하고 항목 수만 늘리면서 재 봅시다. 이 실험은 examples/chain_length.c 에 있습니다.
/*
* chain_length.c - 로드 팩터가 커지면 조회가 얼마나 느려지나
* 13주차: 해시 테이블과 고급 트리
*
* 버킷 수를 1,024개로 고정한 채 항목 수만 256개에서 65,536개까지
* 늘리면서, 최장 사슬 길이와 조회 10만 번의 시간을 잽니다.
* 리사이징을 하지 않으면 "평균 O(1)" 이 어떻게 무너지는지 보는 실험입니다.
* (load_factor.c 는 이것을 막으려고 2배 확장 + rehash 를 합니다)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define BUCKETS 1024
#define LOOKUPS 100000
typedef struct Entry {
char key[16];
struct Entry *next;
} Entry;
unsigned long hash_djb2(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = (unsigned char)*key++)) hash = ((hash << 5) + hash) + c;
return hash;
}
int main(void) {
int sizes[] = {256, 512, 1024, 4096, 16384, 65536};
int nsizes = sizeof(sizes) / sizeof(sizes[0]);
printf("버킷 %d개 고정, 조회 %d번\n\n", BUCKETS, LOOKUPS);
printf("%-9s %-10s %-10s %s\n", "항목 수", "로드 팩터", "최장 사슬", "조회 시간");
printf("------------------------------------------\n");
for (int t = 0; t < nsizes; t++) {
int n = sizes[t];
Entry **table = calloc(BUCKETS, sizeof(Entry *));
Entry *pool = malloc((size_t)n * sizeof(Entry)); /* 노드를 한 덩어리로 */
if (table == NULL || pool == NULL) return 1;
/* k0, k1, ... 을 체이닝으로 넣는다 (머리 삽입) */
for (int i = 0; i < n; i++) {
snprintf(pool[i].key, sizeof(pool[i].key), "k%d", i);
size_t idx = hash_djb2(pool[i].key) % BUCKETS;
pool[i].next = table[idx];
table[idx] = &pool[i];
}
int longest = 0;
for (int b = 0; b < BUCKETS; b++) {
int len = 0;
for (Entry *e = table[b]; e != NULL; e = e->next) len++;
if (len > longest) longest = len;
}
/* 있는 키를 골고루 조회 */
char query[16];
long found = 0;
clock_t t0 = clock();
for (int i = 0; i < LOOKUPS; i++) {
snprintf(query, sizeof(query), "k%d", (i * 7919) % n);
for (Entry *e = table[hash_djb2(query) % BUCKETS]; e != NULL; e = e->next) {
if (strcmp(e->key, query) == 0) { found++; break; }
}
}
double ms = (double)(clock() - t0) * 1000.0 / CLOCKS_PER_SEC;
printf("%-9d %-10.2f %-10d %.1f ms\n", n, (double)n / BUCKETS, longest, ms);
if (found != LOOKUPS) printf(" (조회 실패 %ld건?!)\n", LOOKUPS - found);
free(pool);
free(table);
}
printf("\n로드 팩터가 커질수록 사슬이 길어지고 조회가 느려집니다.\n");
printf("해시 테이블이 O(1)인 것은 로드 팩터를 낮게 유지할 때뿐입니다.\n");
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/chain_length.c -o build/chain_length
$ ./build/chain_length
버킷 1024개 고정, 조회 100000번
항목 수 로드 팩터 최장 사슬 조회 시간
------------------------------------------
256 0.25 2 5.5 ms
512 0.50 5 4.8 ms
1024 1.00 6 5.1 ms
4096 4.00 17 7.2 ms
16384 16.00 38 12.0 ms
65536 64.00 176 49.1 ms
로드 팩터가 커질수록 사슬이 길어지고 조회가 느려집니다.
해시 테이블이 O(1)인 것은 로드 팩터를 낮게 유지할 때뿐입니다.
두 번째 열의 로드 팩터(load factor) 는 항목 수 ÷ 버킷 수, 즉 “버킷당 평균 사슬 길이” 입니다. 이 수치가 이번 주 후반의 핵심 개념이니 여기서 잘 봐 두세요.
- 로드 팩터 1 이하에서는 조회 시간이 거의 변하지 않습니다(5ms 안팎). 이때는 실제로 O(1)입니다.
- 4를 넘으면 늘기 시작하고, 64에서는 10배 가까이 느려졌습니다. 최장 사슬이 176개라 운 나쁜 키는 176번 비교합니다.
- 항목이 256배로 늘었는데 시간은 10배만 늘었습니다. 완전한 O(n)은 아니고 “사슬 길이에 비례” 입니다. 그래도 O(1)이라고 부르기는 어렵습니다.
측정값은 이 컴퓨터 기준이고 실행할 때마다 조금씩 다릅니다. 앞뒤 몇 번 돌려도 경향은 같았습니다. 표를 읽을 때 “256개일 때보다 512개일 때가 더 빠르다” 같은 작은 역전은 노이즈입니다. 배속을 보세요.
여기서 두 가지 결론이 나옵니다. 첫째, 해시 테이블이 O(1)인 것은 로드 팩터를 낮게 유지할 때뿐입니다. 항목이 늘면 버킷도 늘려야 하고, 그것이 4절의 리사이징입니다. 둘째, 최악의 경우는 언제나 남아 있습니다. 모든 키가 한 버킷에 몰리면 O(n)이고, 이것을 악용하는 공격이 실제로 있습니다. 해시 충돌 공격(HashDoS) 은 공격자가 같은 버킷에 떨어지는 키를 수만 개 만들어 서버에 보내는 수법입니다. djb2 처럼 공개된 해시 함수는 충돌하는 키를 미리 계산할 수 있어서 위험합니다. 그래서 요즘 언어들은 프로세스를 시작할 때 무작위 시드를 뽑아 해시에 섞습니다(파이썬은 SipHash 를 씁니다). 1.3절에서 “해시 함수는 결정적이어야 한다” 고 했는데, “프로그램 한 번 실행 안에서” 결정적이면 충분하다는 뜻입니다.
3. 충돌 처리 2: 개방 주소법
3.1 옆 칸으로 밀려나기
체이닝에는 눈에 잘 안 띄는 비용이 있습니다. 항목마다 next 포인터 8바이트를 들고 다녀야 하고, 노드가 malloc 으로 힙 여기저기에 흩어져 있어서 사슬을 따라갈 때마다 캐시 미스가 납니다. 10주차에서 배열과 연결 리스트를 비교하며 본 그 이야기입니다. 빅오가 같아도 메모리가 흩어지면 느립니다.
개방 주소법(open addressing) 은 아예 리스트를 쓰지 않습니다. 모든 항목을 배열 안에 직접 넣고, 충돌하면 옆 칸을 찾아갑니다. 가장 단순한 전략이 선형 탐사(linear probing) 로, h, h+1, h+2, … 순서로 빈 칸을 찾습니다. 마지막 칸 다음은 0번 칸으로 돌아옵니다(wrap-around).
이번에도 손으로 먼저 해 봅시다. 용량 8인 테이블에 다섯 키를 넣습니다. % 8 값은 이렇습니다.
| 순서 | 키 | % 8 (원래 자리) |
|---|---|---|
| 1 | apple | 7 |
| 2 | grape | 4 |
| 3 | mango | 7 |
| 4 | peach | 6 |
| 5 | lemon | 0 |
apple → 7번 비었다 → [7] 에 저장 탐사 1번
grape → 4번 비었다 → [4] 에 저장 탐사 1번
mango → 7번은 apple 자리 → 8번? 없다, 0번으로 감김
→ 0번 비었다 → [0] 에 저장 탐사 2번
peach → 6번 비었다 → [6] 에 저장 탐사 1번
lemon → 0번은 mango 자리 → 1번 비었다 → [1] 에 저장 탐사 2번
[0] [1] [2] [3] [4] [5] [6] [7]
mango lemon - - grape - peach apple
(원래7) (원래0) (원래4) (원래6) (원래7)
mango 는 원래 7번인데 apple 에 밀려 0번까지 왔고, lemon 은 원래 0번인데 그 mango 에 밀려 1번으로 갔습니다. 한 번 밀려난 키가 다른 키를 또 밀어내는 연쇄가 벌써 보입니다.
포인터 오버헤드가 0이고, 옆 칸은 대체로 같은 캐시 라인에 있어 매우 빠릅니다. 파이썬의 dict 와 러스트의 HashMap 이 이 계열입니다. 대신 두 가지 대가가 있습니다. 첫째, 테이블이 가득 차면 더 넣을 수 없습니다(체이닝은 사슬이 길어질 뿐 계속 들어갑니다). 둘째, 삭제가 까다롭습니다. 이 두 번째가 이번 절의 주인공입니다.
examples/hash_open_addr.c:
/*
* hash_open_addr.c - 개방 주소법 (선형 탐사)
* 13주차: 해시 테이블과 고급 트리
*
* 체이닝의 대안: 충돌하면 "옆 칸"을 찾아간다.
* 리스트가 없으니 포인터 오버헤드 0, 캐시 친화적입니다.
* (파이썬 dict, 러스트 HashMap이 이 계열)
*
* 선형 탐사: h, h+1, h+2, ... 순서로 빈 칸을 찾는다.
*
* 최대 함정은 삭제입니다. 그냥 비우면 탐사 사슬이 끊어져
* 뒤에 있던 키를 못 찾게 됩니다. 해법: 묘비(tombstone) 표시.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define CAPACITY 8
typedef enum { SLOT_EMPTY, SLOT_USED, SLOT_TOMBSTONE } SlotState;
typedef struct {
SlotState state;
char key[16];
int value;
} Slot;
typedef struct {
Slot slot[CAPACITY];
size_t count;
} OpenMap;
unsigned long hash_djb2(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = (unsigned char)*key++)) hash = ((hash << 5) + hash) + c;
return hash;
}
void map_init(OpenMap *m) {
memset(m, 0, sizeof(*m)); /* SLOT_EMPTY == 0 */
}
/* 삽입: 빈 칸 또는 묘비 칸을 찾을 때까지 선형 탐사 */
int map_put(OpenMap *m, const char *key, int value) {
if (m->count >= CAPACITY - 1) return 0; /* 가득 (한 칸은 남긴다) */
size_t idx = hash_djb2(key) % CAPACITY;
size_t first_tomb = CAPACITY; /* 재사용할 묘비 위치 */
for (size_t probe = 0; probe < CAPACITY; probe++) {
Slot *s = &m->slot[(idx + probe) % CAPACITY];
if (s->state == SLOT_USED) {
if (strcmp(s->key, key) == 0) { /* 이미 있는 키: 갱신 */
s->value = value;
return 1;
}
continue; /* 남의 자리: 다음 칸 */
}
if (s->state == SLOT_TOMBSTONE) {
if (first_tomb == CAPACITY) {
first_tomb = (idx + probe) % CAPACITY;
}
continue; /* 묘비는 기억만 하고 계속 탐사 (뒤에 같은 키가 있을 수 있다!) */
}
/* SLOT_EMPTY: 이 키는 확실히 없다. 삽입 위치 결정 */
size_t target = (first_tomb != CAPACITY)
? first_tomb /* 묘비 재사용 */
: (idx + probe) % CAPACITY;
Slot *t = &m->slot[target];
t->state = SLOT_USED;
snprintf(t->key, sizeof(t->key), "%s", key);
t->value = value;
m->count++;
return 1;
}
if (first_tomb != CAPACITY) { /* 전부 USED/묘비인데 묘비가 있으면 */
Slot *t = &m->slot[first_tomb];
t->state = SLOT_USED;
snprintf(t->key, sizeof(t->key), "%s", key);
t->value = value;
m->count++;
return 1;
}
return 0;
}
/* 조회: EMPTY를 만날 때까지 탐사 (묘비는 건너뛰고 계속!) */
int map_get(const OpenMap *m, const char *key, int *out, int *probes) {
size_t idx = hash_djb2(key) % CAPACITY;
for (size_t probe = 0; probe < CAPACITY; probe++) {
const Slot *s = &m->slot[(idx + probe) % CAPACITY];
if (probes != NULL) *probes = (int)probe + 1;
if (s->state == SLOT_EMPTY) return 0; /* 여기까지 비었으면 없다 */
if (s->state == SLOT_USED && strcmp(s->key, key) == 0) {
if (out != NULL) *out = s->value;
return 1;
}
/* USED(다른 키)나 TOMBSTONE이면 계속 */
}
return 0;
}
/* 삭제: 묘비로 표시 (EMPTY로 만들면 탐사 사슬이 끊긴다!) */
int map_remove(OpenMap *m, const char *key) {
size_t idx = hash_djb2(key) % CAPACITY;
for (size_t probe = 0; probe < CAPACITY; probe++) {
Slot *s = &m->slot[(idx + probe) % CAPACITY];
if (s->state == SLOT_EMPTY) return 0;
if (s->state == SLOT_USED && strcmp(s->key, key) == 0) {
s->state = SLOT_TOMBSTONE; /* 지웠다는 흔적을 남긴다 */
m->count--;
return 1;
}
}
return 0;
}
void map_show(const OpenMap *m) {
for (size_t i = 0; i < CAPACITY; i++) {
const Slot *s = &m->slot[i];
switch (s->state) {
case SLOT_EMPTY: printf(" [%zu] (빈 칸)\n", i); break;
case SLOT_TOMBSTONE: printf(" [%zu] +++ 묘비 +++\n", i); break;
case SLOT_USED:
printf(" [%zu] %s=%d (원래 자리: %zu)\n",
i, s->key, s->value, hash_djb2(s->key) % CAPACITY);
break;
}
}
}
int main(void) {
OpenMap m;
map_init(&m);
printf("=== 선형 탐사: 충돌하면 옆 칸으로 ===\n");
map_put(&m, "apple", 1);
map_put(&m, "grape", 2);
map_put(&m, "mango", 3);
map_put(&m, "peach", 4);
map_put(&m, "lemon", 5);
map_show(&m);
printf(" ('원래 자리'와 실제 위치가 다르면 충돌로 밀려난 것)\n");
printf("\n=== 조회 탐사 횟수 ===\n");
int value, probes;
const char *keys[] = {"apple", "grape", "mango", "peach", "lemon"};
for (int i = 0; i < 5; i++) {
map_get(&m, keys[i], &value, &probes);
printf("%s: %d번 탐사\n", keys[i], probes);
}
printf("\n=== 삭제의 함정: 묘비가 필요한 이유 ===\n");
printf("grape를 삭제한다:\n");
map_remove(&m, "grape");
map_show(&m);
printf("\ngrape 자리를 그냥 EMPTY로 만들었다면?\n");
printf("grape에 밀려났던 키를 찾을 때 EMPTY를 만나 '없음'으로 오판!\n");
printf("묘비는 '지나가라'는 표지판입니다.\n");
printf("\n삭제 후에도 다른 키 조회 정상:\n");
for (int i = 0; i < 5; i++) {
int found = map_get(&m, keys[i], &value, &probes);
printf("%s: %s\n", keys[i], found ? "발견" : "없음");
}
printf("\n=== 묘비 재사용 ===\n");
map_put(&m, "melon", 6); /* 묘비 자리를 재사용할 수 있다 */
map_show(&m);
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/hash_open_addr.c -o build/hash_open_addr
$ ./build/hash_open_addr
=== 선형 탐사: 충돌하면 옆 칸으로 ===
[0] mango=3 (원래 자리: 7)
[1] lemon=5 (원래 자리: 0)
[2] (빈 칸)
[3] (빈 칸)
[4] grape=2 (원래 자리: 4)
[5] (빈 칸)
[6] peach=4 (원래 자리: 6)
[7] apple=1 (원래 자리: 7)
('원래 자리'와 실제 위치가 다르면 충돌로 밀려난 것)
=== 조회 탐사 횟수 ===
apple: 1번 탐사
grape: 1번 탐사
mango: 2번 탐사
peach: 1번 탐사
lemon: 2번 탐사
=== 삭제의 함정: 묘비가 필요한 이유 ===
grape를 삭제한다:
[0] mango=3 (원래 자리: 7)
[1] lemon=5 (원래 자리: 0)
[2] (빈 칸)
[3] (빈 칸)
[4] +++ 묘비 +++
[5] (빈 칸)
[6] peach=4 (원래 자리: 6)
[7] apple=1 (원래 자리: 7)
grape 자리를 그냥 EMPTY로 만들었다면?
grape에 밀려났던 키를 찾을 때 EMPTY를 만나 '없음'으로 오판!
묘비는 '지나가라'는 표지판입니다.
삭제 후에도 다른 키 조회 정상:
apple: 발견
grape: 없음
mango: 발견
peach: 발견
lemon: 발견
=== 묘비 재사용 ===
[0] mango=3 (원래 자리: 7)
[1] lemon=5 (원래 자리: 0)
[2] melon=6 (원래 자리: 0)
[3] (빈 칸)
[4] +++ 묘비 +++
[5] (빈 칸)
[6] peach=4 (원래 자리: 6)
[7] apple=1 (원래 자리: 7)
첫 번째 표가 손으로 그린 그림과 같습니다. (원래 자리: N) 이 이 예제의 핵심 장치입니다. 실제 위치와 원래 자리가 다르면 충돌로 밀려났다는 뜻이고, 조회 탐사 횟수도 손으로 센 것과 같습니다.
3.2 칸의 세 가지 상태
이 구현의 출발점은 자료구조입니다.
typedef enum { SLOT_EMPTY, SLOT_USED, SLOT_TOMBSTONE } SlotState;
typedef struct {
SlotState state;
char key[16];
int value;
} Slot;
칸(slot)의 상태가 둘이 아니라 셋이라는 점이 개방 주소법의 전부라고 해도 과언이 아닙니다. 비었거나(EMPTY), 쓰고 있거나(USED), 그리고 쓰다가 지웠거나(TOMBSTONE) 입니다. 세 번째 상태가 왜 필요한지는 3.4절에서 버그를 직접 내 보며 확인합니다.
map_init 의 memset(m, 0, sizeof(*m)); 한 줄이 테이블 전체를 EMPTY 로 만듭니다. 이게 성립하는 이유는 8주차에서 배운 대로 enum 의 첫 상수가 0이기 때문입니다(SLOT_EMPTY == 0). “0이 곧 초기 상태” 가 되도록 열거형 순서를 정하는 것은 C에서 아주 흔한 설계입니다.
키는 char key[16] 고정 배열에 담았습니다. 체이닝 예제에서 malloc 으로 복사한 것과 대조됩니다. 개방 주소법은 항목을 배열 안에 직접 두는 방식이라, 키가 구조체 안에 통째로 들어 있어야 캐시의 이점을 살릴 수 있습니다. 대신 16자를 넘는 키는 잘립니다. snprintf(t->key, sizeof(t->key), "%s", key); 를 쓴 이유가 바로 그 잘림을 안전하게 처리하기 위해서입니다. strcpy 였다면 4주차에서 본 버퍼 오버플로입니다.
3.3 조회: EMPTY 를 만나면 끝
if (s->state == SLOT_EMPTY) return 0; /* 여기까지 비었으면 없다 */
if (s->state == SLOT_USED && strcmp(s->key, key) == 0) { ... 발견 ... }
/* USED(다른 키)나 TOMBSTONE이면 계속 */
조회 논리가 왜 이런지 생각해 보세요. 삽입은 “빈 칸이 나올 때까지 오른쪽으로 이동” 이므로, 어떤 키가 테이블에 있다면 그 키는 원래 자리부터 첫 EMPTY 칸 사이에 반드시 있습니다. 그러니 EMPTY 를 만났다는 것은 “없다” 는 증명입니다. 이 덕분에 없는 키를 찾을 때도 테이블 전체를 훑지 않고 일찍 끝납니다.
없는 키를 실제로 조회해 보면 그렇습니다.
zzz(원래 자리 3): 없음, 탐사 1번
durian(원래 자리 0): 없음, 탐사 3번
zzz 는 원래 자리 3번이 비어 있어서 한 번 보고 끝났습니다. durian 은 원래 자리 0번에 mango, 1번에 lemon 이 있어서 두 칸을 지나 2번의 EMPTY 를 보고서야 “없다” 고 답했습니다. 테이블이 붐빌수록 없는 키를 찾는 비용이 커진다는 것도 기억해 두세요.
그리고 바로 이 논리 때문에 다음 함정이 생깁니다.
3.4 삭제의 함정과 묘비
개방 주소법 최대의 함정은 삭제입니다. 조회는 “EMPTY 를 만나면 없는 것” 으로 판단하는데, 중간 칸을 그냥 비워 버리면 탐사 사슬이 끊어집니다. 말로만 들으면 와닿지 않으니 버그를 직접 내 봅시다.
map_remove 에서 s->state = SLOT_TOMBSTONE; 을 s->state = SLOT_EMPTY; 로 바꿉니다. 그리고 다섯 키를 넣은 뒤 apple 을 지우고 나머지를 조회합니다. 예제의 main 이 지우는 grape 대신 apple 을 고른 이유가 있습니다. apple 은 mango 를 밀어낸 장본인이기 때문입니다.
apple 삭제 (묘비 대신 EMPTY로 비움)
[0] mango=3 (원래 자리: 7)
[1] lemon=5 (원래 자리: 0)
[2] (빈 칸)
[3] (빈 칸)
[4] grape=2 (원래 자리: 4)
[5] (빈 칸)
[6] peach=4 (원래 자리: 6)
[7] (빈 칸)
남은 키 조회:
grape: 발견 (탐사 1번)
mango: 없음!! (탐사 1번)
peach: 발견 (탐사 1번)
lemon: 발견 (탐사 2번)
mango 가 사라졌습니다. 0번 칸에 멀쩡히 있는데도요. mango 의 원래 자리 7번이 EMPTY 라서, 조회가 첫 칸에서 “없다” 고 결론 내린 것입니다. 데이터는 있는데 영영 못 찾는 상태입니다. 이 버그는 “밀어낸 키를 지운 뒤 밀려난 키를 찾을 때” 만 나타나기 때문에, 삭제 순서에 따라 나왔다 안 나왔다 해서 디버깅이 지독하게 어렵습니다.
해법이 묘비(tombstone) 입니다. 삭제한 칸에 “여기 뭔가 있었으니 계속 지나가라” 는 표지판을 세우는 것입니다.
if (s->state == SLOT_USED && strcmp(s->key, key) == 0) {
s->state = SLOT_TOMBSTONE; /* 지웠다는 흔적을 남긴다 */
m->count--;
return 1;
}
묘비가 생기면 세 연산이 각각 이렇게 동작합니다.
| 연산 | 묘비를 만나면 |
|---|---|
| 조회 | 건너뛰고 계속 탐사한다 (사슬이 이어진다) |
| 삽입 | 재사용할 수 있다. 단, 조건이 있다 |
| 삭제 | 찾은 칸을 묘비로 바꾼다 |
삽입의 “조건” 이 미묘해서 코드를 다시 봅니다.
if (s->state == SLOT_TOMBSTONE) {
if (first_tomb == CAPACITY) {
first_tomb = (idx + probe) % CAPACITY;
}
continue; /* 묘비는 기억만 하고 계속 탐사 (뒤에 같은 키가 있을 수 있다!) */
}
묘비를 만났다고 즉시 거기에 넣으면 안 됩니다. 뒤쪽에 같은 키가 이미 있을 수 있기 때문입니다. 예를 들어 mango 가 0번에 있는 상태에서 7번이 묘비라면, mango 를 다시 넣을 때 7번 묘비에 넣어 버리면 mango 가 두 개가 됩니다. 그래서 첫 묘비의 위치만 first_tomb 에 기억해 두고 탐사를 계속하다가, EMPTY 를 만나 “같은 키가 없다” 는 것이 확정되면 그제야 기억해 둔 묘비 자리에 넣습니다.
size_t target = (first_tomb != CAPACITY)
? first_tomb /* 묘비 재사용 */
: (idx + probe) % CAPACITY;
실행 결과의 마지막 “묘비 재사용” 부분을 보세요. grape 를 지워 4번이 묘비가 된 상태에서 melon(원래 자리 0)을 넣었더니 2번에 들어갔습니다. 0번 mango, 1번 lemon 을 지나 2번 EMPTY 를 만났고, 그 경로에 묘비가 없었으니 2번에 그대로 들어간 것입니다. 4번 묘비는 melon 의 탐사 경로 밖이라 재사용 대상이 아니었습니다. 묘비 재사용은 “지나가는 길에 있을 때만” 입니다.
묘비에는 대가가 있습니다. 삭제가 잦으면 묘비가 쌓여 “논리적으로는 비었는데 탐사는 오래 걸리는” 테이블이 됩니다. 조회가 묘비를 전부 지나쳐야 하니까요. 그래서 실전 구현은 묘비가 일정 비율을 넘으면 테이블을 통째로 다시 만듭니다. 살아 있는 항목만 새 테이블에 옮기면 묘비가 전부 사라집니다.
3.5 실험: 테이블이 가득 차면?
map_put 첫 줄에 이런 검사가 있습니다.
if (m->count >= CAPACITY - 1) return 0; /* 가득 (한 칸은 남긴다) */
용량이 8인데 왜 7개에서 막을까요? 한 글자짜리 키 a 부터 i 까지 아홉 개를 넣어 보면 이렇습니다.
put a -> OK (count=0)
...
put g -> OK (count=6)
put h -> 실패 (count=7)
put i -> 실패 (count=7)
7개까지는 받고 8개째부터 거절합니다. 이 검사를 없애고 8개를 꽉 채우면 어떻게 될까요? 없는 키를 조회할 때 EMPTY 를 영영 못 만납니다. 이 구현은 probe < CAPACITY 로 한 바퀴만 돌고 포기하도록 돼 있어 무한 루프는 아니지만, 없는 키 하나 찾는 데 테이블 전체를 훑는 O(n)이 됩니다. 이 probe < CAPACITY 조건조차 없는 구현이라면 진짜 무한 루프입니다. 개방 주소법 테이블은 절대 가득 채우면 안 됩니다. 실전에서는 훨씬 전, 로드 팩터 0.7 정도에서 크기를 늘립니다.
3.6 탐사 전략 비교: 클러스터링과의 싸움
3.1절 그림에서 mango 가 apple 에 밀리고 lemon 이 그 mango 에 밀리는 연쇄를 봤습니다. 선형 탐사에는 이것이 커진 1차 클러스터링(primary clustering) 이라는 고질병이 있습니다. 찬 칸들이 덩어리지면, 그 덩어리 어디에 부딪히든 덩어리 끝까지 밀려나서 덩어리가 더 커지는 악순환입니다. 부익부 빈익빈이죠.
대안이 두 가지 있습니다.
- 이차 탐사(quadratic probing): h, h+1, h+4, h+9, … 제곱수 간격으로 점프해서 덩어리를 탈출합니다.
- 더블 해싱(double hashing): 두 번째 해시 함수가 키마다 다른 “보폭” 을 정해 줍니다. 키마다 걷는 간격이 다르니 애초에 뭉칠 일이 적습니다.
말보다 숫자가 설득력 있으니 측정합니다. 용량 1,024에 870개를 넣어 로드 팩터를 0.85까지 올린(일부러 혼잡하게 만든) 상태에서 세 전략을 비교합니다.
examples/probing_compare.c:
/*
* probing_compare.c - 탐사 전략 비교: 선형 vs 이차 vs 더블 해싱
* 13주차: 해시 테이블과 고급 트리
*
* 선형 탐사의 문제: 1차 클러스터링.
* 찬 칸들이 덩어리지면 그 덩어리에 부딪힌 키가 덩어리 끝까지
* 밀려나서 덩어리가 더 커지는 악순환입니다.
*
* 대안:
* - 이차 탐사: h, h+1, h+4, h+9, ... (제곱수 간격으로 점프)
* - 더블 해싱: 두 번째 해시 함수가 "개인별 보폭"을 정해준다
*
* 무작위 키 다수를 넣고 평균 탐사 횟수를 비교합니다.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define CAPACITY 1024 /* 2의 거듭제곱 */
#define LOAD_COUNT 870 /* 로드 팩터 약 0.85 (혼잡한 상태) */
typedef struct {
int used;
unsigned long key;
} Slot;
/* 정수 키를 섞는 해시 (SplitMix64 변형) */
unsigned long hash1(unsigned long x) {
x ^= x >> 30; x *= 0xbf58476d1ce4e5b9UL;
x ^= x >> 27; x *= 0x94d049bb133111ebUL;
x ^= x >> 31;
return x;
}
/* 더블 해싱용 두 번째 해시: 반드시 홀수 보폭 (테이블 크기와 서로소) */
unsigned long hash2(unsigned long x) {
return (hash1(x ^ 0x9e3779b97f4a7c15UL) | 1UL);
}
/* 탐사 전략별 삽입. 반환: 탐사 횟수 (실패 시 0) */
int insert_probe(Slot *table, unsigned long key, int strategy) {
unsigned long h = hash1(key) % CAPACITY;
unsigned long step = hash2(key) % CAPACITY;
for (unsigned long i = 0; i < CAPACITY; i++) {
unsigned long idx;
switch (strategy) {
case 0: idx = (h + i) % CAPACITY; break; /* 선형 */
case 1: idx = (h + i * i) % CAPACITY; break; /* 이차 */
default: idx = (h + i * step) % CAPACITY; break; /* 더블 */
}
if (!table[idx].used) {
table[idx].used = 1;
table[idx].key = key;
return (int)i + 1;
}
}
return 0;
}
/* 클러스터(연속으로 찬 칸 덩어리) 통계 */
void cluster_stats(const Slot *table, int *max_cluster, double *avg_cluster) {
int max = 0, current = 0, clusters = 0, total = 0;
for (int i = 0; i < CAPACITY; i++) {
if (table[i].used) {
current++;
} else if (current > 0) {
if (current > max) max = current;
clusters++;
total += current;
current = 0;
}
}
if (current > 0) { clusters++; total += current; if (current > max) max = current; }
*max_cluster = max;
*avg_cluster = clusters ? (double)total / clusters : 0;
}
int main(void) {
const char *names[] = {"선형 탐사", "이차 탐사", "더블 해싱"};
printf("용량 %d에 %d개 삽입 (로드 팩터 %.2f - 일부러 혼잡하게)\n\n",
CAPACITY, LOAD_COUNT, (double)LOAD_COUNT / CAPACITY);
printf("%-12s %-12s %-12s %-14s %s\n",
"전략", "평균 탐사", "최악 탐사", "최대 클러스터", "평균 클러스터");
printf("---------------------------------------------------------------\n");
for (int strategy = 0; strategy < 3; strategy++) {
Slot *table = calloc(CAPACITY, sizeof(Slot));
if (table == NULL) return 1;
/* 재현 가능한 유사 난수 키 */
unsigned long seed = 42;
long total_probes = 0;
int worst = 0;
for (int i = 0; i < LOAD_COUNT; i++) {
seed = seed * 6364136223846793005UL + 1442695040888963407UL;
int probes = insert_probe(table, seed, strategy);
total_probes += probes;
if (probes > worst) worst = probes;
}
int max_cluster;
double avg_cluster;
cluster_stats(table, &max_cluster, &avg_cluster);
printf("%-14s %8.2f %10d %12d %14.1f\n",
names[strategy],
(double)total_probes / LOAD_COUNT,
worst, max_cluster, avg_cluster);
free(table);
}
printf("\n관찰 포인트:\n");
printf("1. 선형 탐사: 클러스터가 크다 -> 최악 탐사가 길다\n");
printf(" (덩어리에 부딪히면 덩어리 끝까지 걸어야 하니까)\n");
printf("2. 이차 탐사: 제곱수 점프로 덩어리를 탈출 -> 개선\n");
printf("3. 더블 해싱: 키마다 보폭이 달라 뭉칠 일 자체가 적다 -> 최선\n");
printf("\n단, 선형 탐사는 캐시 친화적(옆 칸 = 같은 캐시 라인)이라\n");
printf("로드 팩터를 낮게 유지하면(<0.7) 실전에서 여전히 인기입니다.\n");
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/probing_compare.c -o build/probing_compare
$ ./build/probing_compare
용량 1024에 870개 삽입 (로드 팩터 0.85 - 일부러 혼잡하게)
전략 평균 탐사 최악 탐사 최대 클러스터 평균 클러스터
---------------------------------------------------------------
선형 탐사 3.68 63 89 9.7
이차 탐사 2.41 21 83 7.6
더블 해싱 2.29 20 35 6.9
관찰 포인트:
1. 선형 탐사: 클러스터가 크다 -> 최악 탐사가 길다
(덩어리에 부딪히면 덩어리 끝까지 걸어야 하니까)
2. 이차 탐사: 제곱수 점프로 덩어리를 탈출 -> 개선
3. 더블 해싱: 키마다 보폭이 달라 뭉칠 일 자체가 적다 -> 최선
단, 선형 탐사는 캐시 친화적(옆 칸 = 같은 캐시 라인)이라
로드 팩터를 낮게 유지하면(<0.7) 실전에서 여전히 인기입니다.
탐사 방식 비교
표의 열을 읽는 법입니다. 평균 탐사는 키 하나를 넣을 때 몇 칸을 봤는지의 평균, 최악 탐사는 그중 가장 많이 본 키의 칸 수, 최대 클러스터는 연속으로 찬 칸의 가장 긴 덩어리, 평균 클러스터는 덩어리들의 평균 길이입니다.
평균은 3.68 → 2.41 → 2.29 로 개선되지만, 더 극적인 것은 최악 탐사입니다. 선형 탐사에서는 한 번 넣는 데 63칸을 걸어야 하는 키가 있었습니다. 최대 클러스터가 89칸이니 그 덩어리 한가운데에 떨어진 키입니다. 평균은 괜찮은데 최악이 나쁘다는 것은, 서비스로 치면 “대부분 빠른데 가끔 응답이 멎는” 상태입니다. 실무에서는 평균보다 이 꼬리 지연(tail latency)이 더 문제가 되는 경우가 많습니다. 더블 해싱은 최대 클러스터가 35로 절반 이하입니다.
구현에서 눈여겨볼 부분은 세 군데입니다.
switch (strategy) {
case 0: idx = (h + i) % CAPACITY; break; /* 선형 */
case 1: idx = (h + i * i) % CAPACITY; break; /* 이차 */
default: idx = (h + i * step) % CAPACITY; break; /* 더블 */
}
세 전략의 차이가 이 세 줄이 전부입니다. 나머지 코드는 완전히 동일합니다. 비교 대상만 바꿔 가며 같은 실험을 돌리는 것이 성능 측정의 기본입니다. 5주차와 10주차의 벤치마크도 같은 모양이었습니다.
unsigned long hash2(unsigned long x) {
return (hash1(x ^ 0x9e3779b97f4a7c15UL) | 1UL);
}
더블 해싱의 두 번째 해시는 반드시 홀수를 돌려줘야 합니다. | 1UL 이 그 일을 합니다(3주차의 비트 OR 로 맨 아래 비트를 1로 켭니다). 테이블 크기가 2의 거듭제곱일 때 보폭이 짝수면 어떻게 될까요? 보폭 2로 1,024칸을 걸으면 짝수 칸만 512개 밟고 제자리로 돌아옵니다. 홀수 칸은 영영 못 가서, 빈 칸이 절반이나 있는데 “가득 찼다” 고 잘못 판단합니다. 보폭과 테이블 크기가 서로소(공약수가 1뿐)여야 모든 칸을 방문합니다. 작아 보이는 | 1 이 정확성을 지탱합니다.
unsigned long seed = 42;
for (int i = 0; i < LOAD_COUNT; i++) {
seed = seed * 6364136223846793005UL + 1442695040888963407UL;
rand() 대신 선형 합동 생성기(LCG)를 직접 썼습니다. 시드가 42로 고정이므로 몇 번을 실행해도 같은 키가 나옵니다. 성능을 비교할 때는 입력이 같아야 공정하고, 여러분의 컴퓨터에서도 위와 똑같은 표가 나와야 정상입니다. 이 표에는 시간이 없고 횟수만 있어서, 컴퓨터가 달라도 숫자가 같습니다. 두 상수는 Knuth 의 책에 실린 검증된 값입니다.
그런데 반전이 있습니다. 선형 탐사는 옆 칸 = 같은 캐시 라인이라 캐시 친화성은 최고입니다. 탐사 횟수가 많아도 메모리 접근 한 번의 비용이 싸다는 뜻입니다. 그래서 로드 팩터를 낮게(0.7 이하) 유지하기만 하면 실전에서 여전히 1등 후보이고, 파이썬 dict 와 러스트 HashMap 이 선형 계열을 쓰는 이유입니다. 10주차의 교훈(“빅오만큼 캐시가 중요하다”)이 또 나왔습니다.
“로드 팩터를 낮게 유지한다” 는 말은 자연스럽게 다음 주제로 이어집니다.
4. 로드 팩터와 리사이징
4.1 O(1)을 지키는 비용
2.6절의 표를 다시 떠올려 봅시다. 버킷 1,024개에 항목 65,536개를 넣었더니(로드 팩터 64) 조회가 10배 느려졌습니다. 항목이 늘어나는 것은 막을 수 없으니, 버킷도 같이 늘려야 합니다.
해법은 10주차 동적 배열과 같은 발상입니다. 임계값(보통 0.75)을 넘으면 버킷을 2배로 늘립니다. 단, 동적 배열과 결정적인 차이가 하나 있습니다.
모든 항목을 재배치(rehash)해야 합니다.
이유는 hash % bucket_count 에 있습니다. 분모가 8에서 16으로 바뀌면 나머지가 달라지므로 키의 자리가 바뀝니다. 1.2절의 "cat" 은 해시값이 193,488,125 라서 8칸일 때는 5번이지만 16칸일 때는 13번입니다. 절반쯤은 우연히 같은 자리에 남고 절반쯤은 옮겨 가는데, 어느 키가 옮겨 가는지는 계산해 봐야 아니 전부 다시 계산하는 수밖에 없습니다. 동적 배열은 memcpy 한 번으로 옮기면 그만이지만, 해시 테이블은 항목마다 해시를 다시 계산해서 새 자리를 찾아야 합니다.
examples/load_factor.c:
/*
* load_factor.c - 로드 팩터와 동적 리사이징
* 13주차: 해시 테이블과 고급 트리
*
* 로드 팩터 = 항목 수 / 버킷 수.
* 체이닝 기준 "버킷당 평균 사슬 길이"입니다.
*
* 로드 팩터가 커지면 사슬이 길어져 O(1)이 O(n)으로 퇴화합니다.
* 해법: 임계값(보통 0.75)을 넘으면 버킷을 2배로 늘리고 전부 재배치(rehash).
*
* 10주차 동적 배열의 "2배 확장"과 같은 발상입니다.
* 단, 재배치가 필요한 이유가 다릅니다: 버킷 수가 바뀌면
* `hash % buckets` 결과가 달라지므로 모든 키의 자리가 바뀝니다!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LOAD 0.75
typedef struct Entry {
char *key;
int value;
struct Entry *next;
} Entry;
typedef struct {
Entry **bucket; /* 버킷 배열 자체가 동적! */
size_t bucket_count;
size_t count;
int resize_count; /* 통계: 리사이징 몇 번 했나 */
} HashMap;
unsigned long hash_djb2(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = (unsigned char)*key++)) hash = ((hash << 5) + hash) + c;
return hash;
}
int map_init(HashMap *m, size_t initial_buckets) {
m->bucket = calloc(initial_buckets, sizeof(Entry *));
if (m->bucket == NULL) return 0;
m->bucket_count = initial_buckets;
m->count = 0;
m->resize_count = 0;
return 1;
}
double load_factor(const HashMap *m) {
return (double)m->count / m->bucket_count;
}
/* 리사이징: 버킷 2배 + 전체 재배치 */
int map_resize(HashMap *m) {
size_t new_count = m->bucket_count * 2;
Entry **new_bucket = calloc(new_count, sizeof(Entry *));
if (new_bucket == NULL) return 0;
/* 모든 항목을 새 버킷 배열로 옮긴다.
* 항목(Entry)은 재사용하고 연결만 바꾼다 - 재할당 없음! */
for (size_t i = 0; i < m->bucket_count; i++) {
Entry *e = m->bucket[i];
while (e != NULL) {
Entry *next = e->next;
size_t idx = hash_djb2(e->key) % new_count; /* 새 자리 계산 */
e->next = new_bucket[idx];
new_bucket[idx] = e;
e = next;
}
}
free(m->bucket);
m->bucket = new_bucket;
m->bucket_count = new_count;
m->resize_count++;
return 1;
}
int map_put(HashMap *m, const char *key, int value) {
/* 삽입 전에 로드 팩터 검사 */
if (load_factor(m) > MAX_LOAD) {
size_t old = m->bucket_count;
if (!map_resize(m)) return 0;
printf(" [리사이징] 로드 팩터 %.2f 초과 -> 버킷 %zu -> %zu\n",
MAX_LOAD, old, m->bucket_count);
}
size_t idx = hash_djb2(key) % m->bucket_count;
for (Entry *e = m->bucket[idx]; e != NULL; e = e->next) {
if (strcmp(e->key, key) == 0) {
e->value = value;
return 1;
}
}
Entry *e = malloc(sizeof(Entry));
if (e == NULL) return 0;
e->key = malloc(strlen(key) + 1);
if (e->key == NULL) { free(e); return 0; }
strcpy(e->key, key);
e->value = value;
e->next = m->bucket[idx];
m->bucket[idx] = e;
m->count++;
return 1;
}
/* 사슬 길이 통계 */
void map_stats(const HashMap *m) {
size_t max_chain = 0, used = 0;
for (size_t i = 0; i < m->bucket_count; i++) {
size_t len = 0;
for (Entry *e = m->bucket[i]; e != NULL; e = e->next) len++;
if (len > 0) used++;
if (len > max_chain) max_chain = len;
}
printf(" 항목 %zu / 버킷 %zu (로드 %.2f) | 사용 버킷 %zu, 최장 사슬 %zu\n",
m->count, m->bucket_count, load_factor(m), used, max_chain);
}
void map_free(HashMap *m) {
for (size_t i = 0; i < m->bucket_count; i++) {
Entry *e = m->bucket[i];
while (e != NULL) {
Entry *next = e->next;
free(e->key);
free(e);
e = next;
}
}
free(m->bucket);
memset(m, 0, sizeof(*m));
}
int main(void) {
HashMap m;
if (!map_init(&m, 4)) return 1; /* 아주 작게 시작 */
printf("버킷 4개로 시작, 로드 팩터 %.2f 초과 시 2배 확장\n\n", MAX_LOAD);
/* 키를 100개 넣으며 리사이징 과정을 관찰 */
char key[32];
for (int i = 1; i <= 100; i++) {
snprintf(key, sizeof(key), "user%04d", i);
if (!map_put(&m, key, i)) {
fprintf(stderr, "삽입 실패\n");
map_free(&m);
return 1;
}
if (i == 3 || i == 10 || i == 30 || i == 100) {
printf("%3d개 삽입 후: ", i);
map_stats(&m);
}
}
printf("\n총 리사이징 횟수: %d번 (4 -> %zu)\n",
m.resize_count, m.bucket_count);
printf("\n검증: 리사이징을 거쳐도 모든 키가 살아있나?\n");
int ok = 1, value;
for (int i = 1; i <= 100; i++) {
snprintf(key, sizeof(key), "user%04d", i);
Entry *e = m.bucket[hash_djb2(key) % m.bucket_count];
int found = 0;
for (; e != NULL; e = e->next) {
if (strcmp(e->key, key) == 0 && e->value == i) { found = 1; break; }
}
if (!found) { ok = 0; break; }
}
(void)value;
printf("%s\n", ok ? "100개 전부 정상!" : "데이터 유실!!");
printf("\n핵심:\n");
printf("1. 리사이징 후 재배치(rehash)는 필수 - %%의 분모가 바뀌니까\n");
printf("2. Entry는 재사용하고 연결만 바꾼다 (키 재할당 불필요)\n");
printf("3. 개별 삽입은 가끔 느리지만(리사이징 순간) 평균은 O(1)\n");
printf(" - 10주차 동적 배열의 분할 상환과 같은 원리\n");
map_free(&m);
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/load_factor.c -o build/load_factor
$ ./build/load_factor
버킷 4개로 시작, 로드 팩터 0.75 초과 시 2배 확장
3개 삽입 후: 항목 3 / 버킷 4 (로드 0.75) | 사용 버킷 3, 최장 사슬 1
[리사이징] 로드 팩터 0.75 초과 -> 버킷 4 -> 8
[리사이징] 로드 팩터 0.75 초과 -> 버킷 8 -> 16
10개 삽입 후: 항목 10 / 버킷 16 (로드 0.62) | 사용 버킷 9, 최장 사슬 2
[리사이징] 로드 팩터 0.75 초과 -> 버킷 16 -> 32
[리사이징] 로드 팩터 0.75 초과 -> 버킷 32 -> 64
30개 삽입 후: 항목 30 / 버킷 64 (로드 0.47) | 사용 버킷 21, 최장 사슬 2
[리사이징] 로드 팩터 0.75 초과 -> 버킷 64 -> 128
[리사이징] 로드 팩터 0.75 초과 -> 버킷 128 -> 256
100개 삽입 후: 항목 100 / 버킷 256 (로드 0.39) | 사용 버킷 96, 최장 사슬 2
총 리사이징 횟수: 6번 (4 -> 256)
검증: 리사이징을 거쳐도 모든 키가 살아있나?
100개 전부 정상!
핵심:
1. 리사이징 후 재배치(rehash)는 필수 - %의 분모가 바뀌니까
2. Entry는 재사용하고 연결만 바꾼다 (키 재할당 불필요)
3. 개별 삽입은 가끔 느리지만(리사이징 순간) 평균은 O(1)
- 10주차 동적 배열의 분할 상환과 같은 원리
적재율이 성능을 정한다
100개를 넣는 동안 리사이징이 6번만 일어났습니다. 4 → 8 → 16 → 32 → 64 → 128 → 256 이니까요. 그리고 최장 사슬이 끝까지 2를 넘지 않았습니다. 로드 팩터를 관리한다는 것이 곧 “O(1)을 지킨다” 는 뜻임을 숫자로 확인한 셈입니다. 마지막의 검증 루프는 100개 키를 전부 다시 찾아서, 여섯 번의 재배치를 거치는 동안 잃어버린 키가 없음을 확인합니다.
4.2 리사이징 코드 해설
체이닝 예제와 다른 점은 HashMap 의 첫 줄입니다.
Entry **bucket; /* 버킷 배열 자체가 동적! */
size_t bucket_count;
2절에서는 Entry *bucket[BUCKETS] 로 크기가 고정이었는데, 이제 버킷 배열을 calloc 으로 만듭니다. 크기를 바꿔야 하니까요. Entry ** 는 “Entry 포인터들의 배열을 가리키는 포인터”, 7주차의 이중 포인터입니다. calloc 을 쓴 이유는 10주차에서 배운 대로 0으로 채워 주기 때문입니다. 포인터 배열이 0이면 모든 버킷이 NULL, 즉 비어 있습니다.
핵심은 map_resize 안의 이 루프입니다.
for (size_t i = 0; i < m->bucket_count; i++) {
Entry *e = m->bucket[i];
while (e != NULL) {
Entry *next = e->next; /* 1) 다음을 미리 저장 */
size_t idx = hash_djb2(e->key) % new_count; /* 2) 새 자리 계산 */
e->next = new_bucket[idx]; /* 3) 새 사슬에 매달기 */
new_bucket[idx] = e;
e = next; /* 4) 다음으로 */
}
}
네 줄에 중요한 결정이 다 들어 있습니다.
1) next 를 미리 저장합니다. 3번 줄에서 e->next 를 덮어쓰기 때문입니다. 미리 저장하지 않으면 남은 사슬을 통째로 잃어버립니다. 연결 리스트를 재배치할 때 가장 흔한 버그이니 꼭 기억하세요.
2) 새 자리는 반드시 새 분모(new_count)로 계산합니다. 이 한 곳을 옛 분모 m->bucket_count 로 쓰면 어떻게 될까요? 새 배열에 옛 자리 기준으로 들어가니, 그 뒤 조회는 새 분모로 계산해서 엉뚱한 버킷을 봅니다. 못 찾는 키가 생기는데, 리사이징 직후가 아니라 한참 뒤에야 증상이 나타나 원인을 찾기 어렵습니다.
3) Entry 를 재사용합니다. 새 노드를 malloc 하고 키를 다시 복사하는 구현도 있지만 그럴 필요가 전혀 없습니다. 노드는 그대로 두고 연결만 바꾸면 됩니다. 덕분에 리사이징에서 새로 할당하는 것은 버킷 배열 하나뿐이고, 옛 배열은 free 합니다. 항목 100개를 옮기는 데 malloc 은 한 번입니다.
그리고 삽입 쪽에서는 검사를 삽입 전에 합니다.
if (load_factor(m) > MAX_LOAD) {
...
if (!map_resize(m)) return 0;
...
}
size_t idx = hash_djb2(key) % m->bucket_count; /* 리사이징 후의 분모! */
순서가 중요합니다. idx 를 먼저 계산해 놓고 리사이징을 하면, 그 idx 는 옛 분모 기준이라 엉뚱한 버킷에 들어갑니다. 리사이징이 끝난 뒤에 인덱스를 계산해야 합니다.
4.3 실험: 임계값을 4.0으로 올리면?
#define MAX_LOAD 0.75 를 4.0 으로 바꾸면 리사이징을 훨씬 미룹니다. 메모리는 아끼겠지만 사슬은 어떻게 될까요?
3개 삽입 후: 항목 3 / 버킷 4 (로드 0.75) | 사용 버킷 3, 최장 사슬 1
10개 삽입 후: 항목 10 / 버킷 4 (로드 2.50) | 사용 버킷 4, 최장 사슬 4
[리사이징] 로드 팩터 4.00 초과 -> 버킷 4 -> 8
30개 삽입 후: 항목 30 / 버킷 8 (로드 3.75) | 사용 버킷 8, 최장 사슬 5
[리사이징] 로드 팩터 4.00 초과 -> 버킷 8 -> 16
[리사이징] 로드 팩터 4.00 초과 -> 버킷 16 -> 32
100개 삽입 후: 항목 100 / 버킷 32 (로드 3.12) | 사용 버킷 18, 최장 사슬 10
리사이징은 6번에서 3번으로 줄고 버킷도 256개 대신 32개만 씁니다. 대신 최장 사슬이 2에서 10으로 늘었습니다. 운 나쁜 키는 조회에 10번 비교가 필요합니다. 0.75 라는 숫자는 “메모리 낭비(빈 버킷)와 사슬 길이 사이의 타협점” 으로 자바 HashMap 이 쓰는 기본값이고, 파이썬 dict 는 개방 주소법이라 더 보수적인 2/3 를 씁니다.
4.4 분할 상환: 가끔 느린데 평균은 빠르다
리사이징 자체는 O(n)입니다. 항목을 전부 옮겨야 하니까요. 그런데도 우리는 “삽입은 평균 O(1)” 이라고 말합니다. 왜일까요?
리사이징이 점점 드물게 일어나기 때문입니다. 버킷이 2배씩 늘어나므로 다음 리사이징까지 넣을 수 있는 항목 수도 2배가 됩니다. 100개를 넣는 데 6번, 10만 개를 넣어도 16번입니다(4 × 2¹⁶ = 262,144 개 버킷). 옮긴 항목 수를 전부 더하면 3 + 6 + 12 + … 으로 등비수열이라, 합이 마지막 항의 2배를 넘지 않습니다. 전체 비용을 삽입 횟수로 나누면 상수에 수렴합니다. 이것이 10주차에서 배운 분할 상환 분석(amortized analysis) 입니다.
다만 이 “평균” 에는 함정이 있습니다. 개별 삽입 하나가 튀는 순간이 분명히 존재합니다. 항목이 100만 개일 때 100만 1개째 삽입은 100만 개를 옮깁니다. 실시간성이 중요한 시스템(게임 서버의 프레임 루프, 25주차에서 다룰 리얼타임 시스템)에서는 이 순간의 지연이 문제가 됩니다. 그런 곳에서는 미리 충분한 크기로 만들어 두거나(예약), 리사이징을 여러 번에 나눠 조금씩 하는 점진적 리해싱을 씁니다. Redis 가 실제로 그렇게 동작합니다. 테이블을 두 개 들고 있다가, 요청이 올 때마다 옛 테이블의 버킷 하나씩만 옮깁니다.
5. 최종 대결: 선형 탐색 vs BST vs 해시
3주에 걸쳐 배운 탐색 방법의 결승전입니다. 같은 데이터 5만 건을 넣고 5만 번 조회합니다.
examples/hash_vs_search.c:
/*
* hash_vs_search.c - 탐색 대결: 선형 탐색 vs BST vs 해시 테이블
* 13주차: 해시 테이블과 고급 트리
*
* 3주에 걸쳐 배운 탐색 방법들의 최종 대결입니다.
* 같은 데이터 5만 건을 넣고 5만 번 조회합니다.
*
* 이론: 선형 O(n) / BST O(log n) / 해시 평균 O(1)
* 실측으로 확인해 봅시다.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define N 50000
#define BUCKETS 65536 /* 로드 팩터 약 0.76 */
/* ---------- 1. 선형 탐색 (배열) ---------- */
typedef struct { unsigned long key; int value; } Pair;
int linear_get(const Pair *arr, int n, unsigned long key) {
for (int i = 0; i < n; i++) {
if (arr[i].key == key) return arr[i].value;
}
return -1;
}
/* ---------- 2. BST (12주차) ---------- */
typedef struct TNode {
unsigned long key;
int value;
struct TNode *left, *right;
} TNode;
TNode *bst_insert(TNode *root, unsigned long key, int value) {
if (root == NULL) {
TNode *n = malloc(sizeof(TNode));
if (n == NULL) exit(1);
n->key = key; n->value = value;
n->left = n->right = NULL;
return n;
}
if (key < root->key) root->left = bst_insert(root->left, key, value);
else if (key > root->key) root->right = bst_insert(root->right, key, value);
return root;
}
int bst_get(const TNode *root, unsigned long key) {
while (root != NULL) {
if (key == root->key) return root->value;
root = (key < root->key) ? root->left : root->right;
}
return -1;
}
void bst_free(TNode *root) {
if (root == NULL) return;
bst_free(root->left);
bst_free(root->right);
free(root);
}
/* ---------- 3. 해시 테이블 (체이닝) ---------- */
typedef struct HEntry {
unsigned long key;
int value;
struct HEntry *next;
} HEntry;
unsigned long hash_int(unsigned long x) {
x ^= x >> 30; x *= 0xbf58476d1ce4e5b9UL;
x ^= x >> 27; x *= 0x94d049bb133111ebUL;
x ^= x >> 31;
return x;
}
void hash_put(HEntry **table, unsigned long key, int value) {
size_t idx = hash_int(key) % BUCKETS;
HEntry *e = malloc(sizeof(HEntry));
if (e == NULL) exit(1);
e->key = key; e->value = value;
e->next = table[idx];
table[idx] = e;
}
int hash_get(HEntry **table, unsigned long key) {
for (HEntry *e = table[hash_int(key) % BUCKETS]; e != NULL; e = e->next) {
if (e->key == key) return e->value;
}
return -1;
}
double ms(clock_t a, clock_t b) {
return (double)(b - a) * 1000.0 / CLOCKS_PER_SEC;
}
int main(void) {
printf("데이터 %d건 저장 후 %d번 조회 대결\n\n", N, N);
/* 무작위처럼 보이는 재현 가능한 키 (홀수 곱셈으로 섞기) */
unsigned long *keys = malloc(N * sizeof(unsigned long));
Pair *arr = malloc(N * sizeof(Pair));
if (keys == NULL || arr == NULL) return 1;
for (int i = 0; i < N; i++) {
keys[i] = (unsigned long)(i + 1) * 2654435761UL % 1000000007UL;
}
/* --- 구축 --- */
for (int i = 0; i < N; i++) { arr[i].key = keys[i]; arr[i].value = i; }
TNode *bst = NULL;
clock_t b0 = clock();
for (int i = 0; i < N; i++) bst = bst_insert(bst, keys[i], i);
clock_t b1 = clock();
HEntry **table = calloc(BUCKETS, sizeof(HEntry *));
if (table == NULL) return 1;
clock_t h0 = clock();
for (int i = 0; i < N; i++) hash_put(table, keys[i], i);
clock_t h1 = clock();
/* --- 조회 대결 --- */
long long sum = 0;
clock_t t0 = clock();
for (int i = 0; i < 2000; i++) { /* 선형은 2천 번만 (느려서) */
sum += linear_get(arr, N, keys[(i * 37) % N]);
}
clock_t t1 = clock();
double linear_time = ms(t0, t1) * (N / 2000.0); /* N번으로 환산 */
clock_t t2 = clock();
for (int i = 0; i < N; i++) sum += bst_get(bst, keys[(i * 37) % N]);
clock_t t3 = clock();
clock_t t4 = clock();
for (int i = 0; i < N; i++) sum += hash_get(table, keys[(i * 37) % N]);
clock_t t5 = clock();
printf("%-14s %-14s %s\n", "방법", "구축", "조회 5만 번");
printf("---------------------------------------------\n");
printf("%-14s %-14s %10.1f ms (환산)\n", "선형 탐색", "0 ms (배열 복사)", linear_time);
printf("%-14s %8.1f ms %10.1f ms\n", "BST", ms(b0, b1), ms(t2, t3));
printf("%-14s %8.1f ms %10.1f ms\n", "해시 테이블", ms(h0, h1), ms(t4, t5));
printf("\n(합계 검증용: %lld)\n", sum);
printf("\n결론:\n");
printf("- 선형 O(n): 조회마다 평균 %d번 비교. 논외.\n", N / 2);
printf("- BST O(log n): 약 %d번 비교. 훌륭하지만...\n", 17);
printf("- 해시 O(1): 사슬 평균 %.1f개만 확인. 압승!\n",
(double)N / BUCKETS);
printf("\n해시의 대가: 정렬 순회 불가, 메모리 추가 사용, 최악 O(n).\n");
printf("'키로 바로 찾기'만 필요하면 해시, 순서도 필요하면 트리.\n");
/* 정리 */
free(arr);
free(keys);
bst_free(bst);
for (size_t i = 0; i < BUCKETS; i++) {
HEntry *e = table[i];
while (e != NULL) { HEntry *next = e->next; free(e); e = next; }
}
free(table);
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/hash_vs_search.c -o build/hash_vs_search
$ ./build/hash_vs_search
데이터 50000건 저장 후 50000번 조회 대결
방법 구축 조회 5만 번
---------------------------------------------
선형 탐색 0 ms (배열 복사) 944.0 ms (환산)
BST 6.3 ms 5.5 ms
해시 테이블 1.8 ms 1.6 ms
(합계 검증용: 2541513000)
결론:
- 선형 O(n): 조회마다 평균 25000번 비교. 논외.
- BST O(log n): 약 17번 비교. 훌륭하지만...
- 해시 O(1): 사슬 평균 0.8개만 확인. 압승!
해시의 대가: 정렬 순회 불가, 메모리 추가 사용, 최악 O(n).
'키로 바로 찾기'만 필요하면 해시, 순서도 필요하면 트리.
시간이 나오는 벤치마크라 실행할 때마다 값이 다릅니다. 세 번 더 돌린 결과입니다.
| 실행 | 선형 (환산) | BST 조회 | 해시 조회 |
|---|---|---|---|
| 1 | 1019.2 ms | 7.0 ms | 1.8 ms |
| 2 | 1121.8 ms | 10.0 ms | 2.5 ms |
| 3 | 1543.4 ms | 6.6 ms | 1.6 ms |
절대값은 20~50% 씩 흔들리지만 순서와 배속은 그대로입니다. 선형 탐색은 해시보다 수백 배 느리고, BST 는 해시보다 3~4배 느립니다. 벤치마크 표를 읽을 때는 항상 이렇게 봐야 합니다.
-O2 로 컴파일하면 전부 빨라집니다.
선형 탐색 0 ms (배열 복사) 251.3 ms (환산)
BST 4.4 ms 2.6 ms
해시 테이블 1.7 ms 0.7 ms
선형 탐색이 4배 빨라진 것이 눈에 띕니다. 단순한 반복문이라 컴파일러가 잘 최적화하기 때문입니다. 그래도 순서는 같습니다.
이 측정 코드에서 배울 점이 두 가지 있습니다.
for (int i = 0; i < 2000; i++) { /* 선형은 2천 번만 (느려서) */
sum += linear_get(arr, N, keys[(i * 37) % N]);
}
double linear_time = ms(t0, t1) * (N / 2000.0); /* N번으로 환산 */
선형 탐색을 5만 번 다 돌리면 너무 오래 걸리므로 2천 번만 돌리고 25배로 환산했습니다. 출력에 (환산) 이라고 정직하게 표시한 점에 주목하세요. 측정값을 가공했다면 반드시 그 사실을 함께 적어야 합니다.
long long sum = 0;
...
printf("\n(합계 검증용: %lld)\n", sum);
조회 결과를 sum 에 더하고 마지막에 출력합니다. 왜 이런 쓸데없어 보이는 일을 할까요? 컴파일러가 결과를 안 쓰는 코드를 통째로 삭제해 버리기 때문입니다. 10주차의 perf_compare 가 정확히 이 문제로 -O2 에서 0.00ms 를 냈던 것을 기억하시죠. 결과를 어딘가에 쓰면 컴파일러가 코드를 지울 수 없습니다. 벤치마크를 작성할 때 반드시 챙겨야 하는 기법이고, 23주차 성능 최적화 편에서 다시 만납니다.
5.1 해시의 청구서
그럼 이제 모든 것을 해시로 하면 될까요? 아닙니다. 청구서를 확인할 차례입니다.
| 해시 테이블 | 균형 BST (12주차 AVL) | |
|---|---|---|
| 탐색 / 삽입 / 삭제 | 평균 O(1), 최악 O(n) | 항상 O(log n) |
| 정렬 순회 | 불가능 (섞여 있음) | 중위 순회로 공짜 |
| 범위 검색 (10~20 사이) | 불가능 (전수 조사뿐) | O(log n + k) |
| 최솟값 / 최댓값 | 불가능 (전수 조사뿐) | O(log n) |
| 메모리 | 여유 버킷 필요 (25% 이상 낭비) | 노드만큼만 |
| 최악 보장 | 없음 (공격 가능) | 있음 |
해시 함수가 키를 의도적으로 섞기 때문에 순서 정보가 통째로 사라진다는 점이 핵심입니다. 2.2절 그림에서 과일들이 버킷에 들어간 순서를 보세요. orange(1), cherry(2), grape(4), peach(6), apple(7) 로 알파벳순도, 가격순도 아닙니다. “가격이 5000원 이상인 과일” 을 찾으려면 해시 테이블은 전부 뒤져야 합니다. 트리라면 5000 위치로 내려간 뒤 오른쪽만 훑으면 됩니다.
“키로 바로 찾기” 만 필요하면 해시, 순서나 범위가 필요하면 트리. 이 한 줄이 이번 주의 결론입니다.
실무에서는 둘을 같이 쓰기도 합니다. 데이터베이스가 기본 인덱스로 B-트리를 쓰면서(범위 검색 때문에) 동등 비교 전용 해시 인덱스를 따로 제공하는 이유입니다. 그리고 그 B-트리가 바로 다음 주제입니다.
6. B-트리: 디스크를 위한 트리
6.1 왜 또 다른 트리인가
12주차에 AVL 트리로 균형 문제를 해결했습니다. 어떤 순서로 넣어도 높이가 log n 을 넘지 않으니 항상 O(log n)입니다. 그런데 왜 데이터베이스는 AVL 이 아니라 B-트리를 쓸까요?
답은 디스크에 있습니다. 지금까지 우리가 만든 자료구조는 전부 RAM 위에서 살았습니다. 노드 하나를 읽는 비용이 사실상 공짜라고 가정했습니다. 그런데 데이터가 RAM 에 다 안 들어가면 디스크에 둬야 하고, 디스크는 완전히 다른 세계입니다.
| 저장 장치 | 접근 시간 | RAM 을 1초로 치면 |
|---|---|---|
| CPU 캐시 | 약 1 ns | 0.01초 |
| RAM | 약 100 ns | 1초 |
| SSD | 약 100 µs | 약 17분 |
| HDD | 약 10 ms | 약 28시간 |
게다가 디스크는 바이트 단위로 읽지 않습니다. 블록(보통 4KB) 단위로 읽습니다. 9주차 파일 입출력에서 본 버퍼링과 같은 이유입니다. 4바이트짜리 정수 하나를 읽어도 4KB 를 통째로 가져옵니다.
여기서 이진 트리의 비효율이 드러납니다. 노드 하나(키 1개와 포인터 2개, 24바이트쯤)를 읽으려고 4KB 를 읽는 셈이니 99.4%를 버리는 것입니다. 게다가 높이가 log₂ n 이라 1,000만 건이면 23번 내려가야 하고, 그것이 곧 디스크 읽기 23번입니다. HDD 라면 조회 한 번에 0.23초입니다.
B-트리의 발상은 여기서 출발합니다. 노드 하나를 블록 하나에 꽉 채우자. 노드 하나에 키를 300개 담으면, 디스크 한 번 읽기로 300개를 비교할 수 있습니다. 그리고 자식이 301개이므로 트리 높이가 확 줄어듭니다.
높이 1: 300건
높이 2: 300 × 300 = 9만 건
높이 3: 300 × 300 × 300 = 2,700만 건 ← 디스크 읽기 단 3번
이진 트리로 2,700만 건이면 25번 읽어야 할 것을 3번에 끝냅니다. 디스크가 RAM 보다 10만 배 느리니 이 차이가 사실상 전부입니다. MySQL InnoDB, PostgreSQL, SQLite, 그리고 파일 시스템(ext4, NTFS)의 인덱스가 모두 B-트리 계열인 이유입니다.
트리 높이 = 디스크 읽기 횟수. B-트리를 이해하는 한 문장을 고르라면 이것입니다. 우리가 지금까지 세던 “비교 횟수” 가 아니라 “읽기 횟수” 가 비용이 되는 순간, 자료구조의 최적해가 바뀝니다.
6.2 규칙과 분할
다음 예제는 차수 4(노드당 키 1~3개)의 미니 B-트리입니다. 실제 DB 의 300개 대신 3개로 줄였을 뿐 원리는 똑같습니다.
B-트리의 규칙은 네 가지입니다.
- 노드 안의 키는 오름차순 정렬을 유지한다
- 자식 수 = 키 수 + 1 (키들이 자식 범위의 “칸막이” 역할)
- 모든 잎이 같은 깊이에 있다 (AVL 의 “높이 차 1 이하” 보다 강한 조건)
- 키가 넘치면 분할한다: 가운데 키가 부모로 승진
2번 규칙을 그림으로 보면 이렇습니다. 키가 [10 20] 인 노드는 자식이 셋입니다.
[10 20]
/ | \
10 미만 10~20 20 초과
examples/btree_basic.c:
/*
* btree_basic.c - B-트리 기초 (차수 4: 노드당 키 최대 3개)
* 13주차: 해시 테이블과 고급 트리
*
* "노드 하나 = 키 하나"인 BST와 달리, B-트리는 노드 하나에
* 키 여러 개를 담고 자식도 여러 개를 둡니다.
*
* 왜? 디스크 때문입니다. 디스크는 한 번 읽을 때 블록(4KB+) 단위로
* 읽으므로, 노드 하나를 블록 하나에 꽉 채우면 디스크 접근 한 번에
* 키 수백 개를 비교할 수 있습니다. 트리 높이 = 디스크 읽기 횟수!
* 그래서 모든 데이터베이스 인덱스(MySQL InnoDB 등)가 B-트리 계열입니다.
*
* 규칙 (차수 4 기준):
* - 노드당 키 1~3개, 오름차순 정렬 유지
* - 자식 수 = 키 수 + 1
* - 모든 잎이 같은 깊이 (완벽한 균형!)
* - 키가 4개가 되면 "분할": 가운데 키가 부모로 올라간다
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_KEYS 3 /* 차수 4 = 키 최대 3개 */
typedef struct BNode {
int keys[MAX_KEYS + 1]; /* 분할 직전 임시로 4개까지 */
struct BNode *child[MAX_KEYS + 2];
int nkeys;
int is_leaf;
} BNode;
BNode *bnode_create(int is_leaf) {
BNode *n = calloc(1, sizeof(BNode));
if (n == NULL) exit(1);
n->is_leaf = is_leaf;
return n;
}
/* 탐색: 노드 안에서는 선형으로, 노드 사이는 자식 포인터로 */
int btree_search(const BNode *node, int key, int *node_visits) {
if (node == NULL) return 0;
(*node_visits)++;
int i = 0;
while (i < node->nkeys && key > node->keys[i]) i++; /* 노드 내 탐색 */
if (i < node->nkeys && key == node->keys[i]) return 1;
if (node->is_leaf) return 0;
return btree_search(node->child[i], key, node_visits);
}
/* 자식 i가 가득 찼을 때 분할: 가운데 키를 부모로 올린다 */
void split_child(BNode *parent, int i) {
BNode *full = parent->child[i];
BNode *right = bnode_create(full->is_leaf);
int mid = MAX_KEYS / 2; /* 가운데 인덱스 (키 3개면 1) */
/* 가운데 오른쪽 키들을 새 노드로 */
right->nkeys = MAX_KEYS - mid - 1;
for (int j = 0; j < right->nkeys; j++) {
right->keys[j] = full->keys[mid + 1 + j];
}
if (!full->is_leaf) {
for (int j = 0; j <= right->nkeys; j++) {
right->child[j] = full->child[mid + 1 + j];
}
}
full->nkeys = mid; /* 왼쪽 노드는 가운데 앞까지만 */
/* 부모에 자리 만들기: i번째 뒤의 키/자식을 한 칸씩 밀기 */
for (int j = parent->nkeys; j > i; j--) {
parent->keys[j] = parent->keys[j - 1];
parent->child[j + 1] = parent->child[j];
}
parent->keys[i] = full->keys[mid]; /* 가운데 키 승진! */
parent->child[i + 1] = right;
parent->nkeys++;
}
/* 가득 차지 않은 노드에 삽입 (재귀) */
void insert_nonfull(BNode *node, int key) {
int i = node->nkeys - 1;
if (node->is_leaf) {
/* 정렬 위치에 끼워 넣기 (삽입 정렬 한 스텝) */
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->nkeys++;
return;
}
/* 내려갈 자식 선택 */
while (i >= 0 && key < node->keys[i]) i--;
i++;
if (node->child[i]->nkeys == MAX_KEYS) {
split_child(node, i); /* 내려가기 전에 미리 분할! */
if (key > node->keys[i]) i++;
}
insert_nonfull(node->child[i], key);
}
/* 삽입 진입점: 루트가 가득 찼으면 트리가 위로 자란다 */
BNode *btree_insert(BNode *root, int key) {
if (root == NULL) {
root = bnode_create(1);
root->keys[0] = key;
root->nkeys = 1;
return root;
}
if (root->nkeys == MAX_KEYS) {
/* 새 루트를 만들고 기존 루트를 분할
* B-트리는 아래가 아니라 "위로" 자란다! */
BNode *new_root = bnode_create(0);
new_root->child[0] = root;
split_child(new_root, 0);
insert_nonfull(new_root, key);
return new_root;
}
insert_nonfull(root, key);
return root;
}
/* 트리 출력 (들여쓰기 = 깊이) */
void btree_print(const BNode *node, int depth) {
if (node == NULL) return;
printf("%*s[", depth * 4, "");
for (int i = 0; i < node->nkeys; i++) {
printf("%d%s", node->keys[i], (i + 1 < node->nkeys) ? " " : "");
}
printf("]\n");
if (!node->is_leaf) {
for (int i = 0; i <= node->nkeys; i++) {
btree_print(node->child[i], depth + 1);
}
}
}
void btree_free(BNode *node) {
if (node == NULL) return;
if (!node->is_leaf) {
for (int i = 0; i <= node->nkeys; i++) btree_free(node->child[i]);
}
free(node);
}
int btree_height(const BNode *node) {
int h = 0;
while (node != NULL && !node->is_leaf) {
node = node->child[0];
h++;
}
return h;
}
int main(void) {
printf("B-트리 (차수 4: 노드당 키 1~3개)\n");
printf("=====================================\n\n");
BNode *root = NULL;
printf("=== 1~10을 순서대로 삽입 (BST라면 사슬이 될 입력!) ===\n");
for (int i = 1; i <= 10; i++) {
root = btree_insert(root, i);
if (i == 3 || i == 4 || i == 7 || i == 10) {
printf("\n%d까지 삽입 후:\n", i);
btree_print(root, 0);
}
}
printf("\n키 4개째가 들어갈 때 분할이 일어나 가운데 키가 위로 올라가고,\n");
printf("모든 잎은 항상 같은 깊이를 유지합니다 (자동 균형!).\n");
printf("\n=== 탐색: 방문한 노드 수 ===\n");
int targets[] = {1, 6, 10, 99};
for (int i = 0; i < 4; i++) {
int visits = 0;
int found = btree_search(root, targets[i], &visits);
printf("%2d 탐색: %s (노드 %d개 방문)\n",
targets[i], found ? "발견" : "없음", visits);
}
printf("\n=== 왜 데이터베이스는 B-트리인가 ===\n");
printf("현재 트리: 키 10개, 높이 %d\n", btree_height(root));
printf("실제 DB: 노드 하나에 키 ~300개(4KB 블록 기준)\n");
printf(" 높이 3이면 300^3 = 2,700만 건을 디스크 읽기 3번에 탐색!\n");
printf(" 이진 트리였다면 log2(2700만) = 25번 디스크 읽기.\n");
printf(" 디스크 접근이 RAM보다 10만 배 느리므로 이 차이가 전부입니다.\n");
btree_free(root);
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/btree_basic.c -o build/btree_basic
$ ./build/btree_basic
B-트리 (차수 4: 노드당 키 1~3개)
=====================================
=== 1~10을 순서대로 삽입 (BST라면 사슬이 될 입력!) ===
3까지 삽입 후:
[1 2 3]
4까지 삽입 후:
[2]
[1]
[3 4]
7까지 삽입 후:
[2 4]
[1]
[3]
[5 6 7]
10까지 삽입 후:
[4]
[2]
[1]
[3]
[6 8]
[5]
[7]
[9 10]
키 4개째가 들어갈 때 분할이 일어나 가운데 키가 위로 올라가고,
모든 잎은 항상 같은 깊이를 유지합니다 (자동 균형!).
=== 탐색: 방문한 노드 수 ===
1 탐색: 발견 (노드 3개 방문)
6 탐색: 발견 (노드 2개 방문)
10 탐색: 발견 (노드 3개 방문)
99 탐색: 없음 (노드 3개 방문)
=== 왜 데이터베이스는 B-트리인가 ===
현재 트리: 키 10개, 높이 2
실제 DB: 노드 하나에 키 ~300개(4KB 블록 기준)
높이 3이면 300^3 = 2,700만 건을 디스크 읽기 3번에 탐색!
이진 트리였다면 log2(2700만) = 25번 디스크 읽기.
디스크 접근이 RAM보다 10만 배 느리므로 이 차이가 전부입니다.
1부터 10까지 오름차순으로 넣었다는 점이 중요합니다. 12주차에서 이 입력은 BST 를 한쪽으로 늘어진 사슬(노드 10개가 한 줄, 높이 9)로 만들어 버리는 최악의 시나리오였습니다. B-트리는 같은 입력에서 높이 2를 유지합니다. 그것도 회전 없이, 분할만으로요.
탐색 결과의 “노드 N개 방문” 도 최종 트리 그림으로 따라가 봅시다. btree_search 는 노드에 들어갈 때마다 node_visits 를 하나 늘리고, 노드 안에서는 while (i < node->nkeys && key > node->keys[i]) i++; 로 키보다 큰 첫 칸을 찾습니다. 그 칸 번호 i 가 곧 내려갈 자식 번호입니다(규칙 2 의 “칸막이”).
1 탐색: [4] → 1 < 4 이니 child[0] → [2] → 1 < 2 이니 child[0] → [1] 발견 노드 3개
6 탐색: [4] → 6 > 4 이니 child[1] → [6 8] → keys[0] == 6 발견 노드 2개
10 탐색: [4] → child[1] → [6 8] → 10 > 8 이니 child[2] → [9 10] 발견 노드 3개
99 탐색: [4] → child[1] → [6 8] → child[2] → [9 10] 잎인데 없다 → 없음 노드 3개
어떤 키를 찾든 방문 노드 수가 높이 + 1 = 3 을 넘지 않습니다. 없는 키를 찾을 때도 마찬가지입니다. 노드 하나가 디스크 블록 하나라면, 이 트리에서는 어떤 조회도 디스크를 3번 넘게 읽지 않는다는 뜻입니다.
6.3 분할을 한 단계씩
핵심 함수는 split_child 입니다. 가득 찬 자식 노드를 둘로 쪼개고 가운데 키를 부모로 올립니다.
int mid = MAX_KEYS / 2; /* 가운데 인덱스 (키 3개면 1) */
/* 가운데 오른쪽 키들을 새 노드로 */
right->nkeys = MAX_KEYS - mid - 1;
for (int j = 0; j < right->nkeys; j++) {
right->keys[j] = full->keys[mid + 1 + j];
}
...
full->nkeys = mid; /* 왼쪽 노드는 가운데 앞까지만 */
...
parent->keys[i] = full->keys[mid]; /* 가운데 키 승진! */
parent->child[i + 1] = right;
[1 2 3] 에 4를 넣는 상황을 한 단계씩 따라가 봅시다. 실행 결과의 “3까지 삽입 후” 와 “4까지 삽입 후” 사이에 일어나는 일입니다.
① 루트 [1 2 3] 이 가득 찼다 (nkeys == MAX_KEYS)
② 새 루트를 만들고 옛 루트를 child[0] 으로 매단다
[ ] ← new_root (키 0개)
|
[1 2 3]
③ split_child(new_root, 0): mid = 1, 가운데 키는 2
- right 노드를 만들어 가운데 오른쪽 키 [3] 을 옮긴다
- full 노드는 nkeys = 1 로 줄여 [1] 만 남긴다
- 가운데 키 2 를 new_root 에 올리고, right 를 child[1] 로
[2]
/ \
[1] [3]
④ insert_nonfull(new_root, 4): 4 > 2 이니 오른쪽 자식으로
[3] 은 안 찼으니 그냥 끼운다
[2]
/ \
[1] [3 4]
실행 결과의 “4까지 삽입 후” 와 정확히 일치합니다. 키 하나를 올리고 노드 하나를 만들었을 뿐인데 트리의 높이가 0에서 1로 늘었습니다.
“7까지 삽입 후” 도 같은 원리입니다. 5 는 [3 4] 뒤에 붙어 [3 4 5] 가 됩니다. 6을 넣으려고 내려가다 보니 [3 4 5] 가 가득 차 있어 미리 분할합니다. 가운데 4가 부모로 올라가 [2 4] 가 되고, 아래는 [3] 과 [5] 로 나뉩니다. 6은 4보다 크니 [5] 쪽으로 가서 [5 6] 이 되고, 7이 [5 6 7] 로 들어갑니다.
선제적 분할(preemptive split) 이라는 기법도 눈여겨보세요.
if (node->child[i]->nkeys == MAX_KEYS) {
split_child(node, i); /* 내려가기 전에 미리 분할! */
if (key > node->keys[i]) i++;
}
내려가려는 자식이 가득 차 있으면, 아직 넘치지 않았는데도 미리 분할합니다. 왜 그럴까요? 만약 가득 찬 채로 내려갔다가 아래에서 분할이 일어나면 부모에게 키를 올려보내야 하는데, 그 부모도 가득 차 있으면 또 위로, 그 위도 가득 차 있으면 또 위로 연쇄가 일어납니다. 내려가는 길에 미리 자리를 만들어 두면 이 연쇄를 원천 차단할 수 있습니다. 한 번의 하향 경로로 삽입이 끝난다는 것은 디스크 기반 구조에서 특히 큰 장점입니다. 올라가면서 노드를 다시 쓰지 않아도 되니까요. 분할 직후 if (key > node->keys[i]) i++; 는 “올라온 키보다 크면 오른쪽 조각으로” 라는 뜻입니다.
마지막으로 트리가 자라는 방향입니다.
if (root->nkeys == MAX_KEYS) {
BNode *new_root = bnode_create(0);
new_root->child[0] = root;
split_child(new_root, 0);
insert_nonfull(new_root, key);
return new_root; /* 루트가 바뀐다! */
}
B-트리는 아래로 자라지 않고 루트가 분할되며 위로 자랍니다. 모든 잎이 동시에 한 단계씩 깊어지는 셈입니다. 이것이 “모든 잎이 같은 깊이” 라는 조건이 저절로 유지되는 이유입니다. 높이가 늘어나는 순간은 오직 루트가 분할될 때뿐입니다.
6.4 실험: 편향 트리와 높이 비교
12주차의 BST 는 1, 2, 3, … 을 순서대로 넣으면 노드 수만큼 높아졌습니다. 같은 입력으로 B-트리를 만들면 얼마나 낮을까요? 예제의 함수들을 그대로 쓰고 키 수만 늘려 재 봤습니다. 높이는 12주차와 같은 기준(루트에서 잎까지의 간선 수)입니다.
| 키 수 | BST 높이 (순차 삽입) | B-트리 높이 (차수 4) | B-트리 노드 수 | log₂ n |
|---|---|---|---|---|
| 10 | 9 | 2 | 8 | 3.3 |
| 100 | 99 | 5 | 96 | 6.6 |
| 1,000 | 999 | 8 | 992 | 10.0 |
| 10,000 | 9,999 | 12 | 9,992 | 13.3 |
| 100,000 | (스택이 넘쳐 측정 불가) | 15 | 99,990 | 16.6 |
BST 는 높이가 n 에 비례해 10만 개에서는 재귀 깊이 때문에 스택이 넘쳐 측정조차 못 했습니다. B-트리는 10만 개에 높이 15로, 차수 4 인데도 log₂ n 보다 낮습니다. 실제 DB 처럼 차수가 300이면 높이 2(세 층)에 2,700만 건이 들어갑니다.
그런데 표에서 이상한 점이 하나 보입니다. 키 100개인데 노드가 96개입니다. 노드당 키가 1개 남짓이라는 뜻입니다. 차수 4면 노드당 3개까지 담을 수 있는데 왜 이렇게 비어 있을까요? 순차 삽입 때문입니다. 항상 맨 오른쪽 잎에만 넣으니, 분할이 일어날 때마다 왼쪽 조각 [1] 은 키 하나만 갖고 영영 그대로 남습니다. 무작위 순서로 넣으면 노드가 평균 2/3 정도 찹니다. 실제 DB 가 자동 증가 ID 로 인덱스를 만들 때 겪는 문제이고, 그래서 B+트리 구현들은 순차 삽입을 감지해서 분할 비율을 조정하기도 합니다.
이번 주에는 삽입과 탐색까지만 구현합니다. 삭제는 “키가 너무 적어진 노드를 형제와 병합” 하는 과정이 필요해 분량이 크게 늘어납니다. 지금 목표는 “왜 DB 가 B-트리인가” 를 이해하는 것입니다. 궁금하면 연습 문제 9번으로 도전해 보세요.
B+트리 이야기: 실제 데이터베이스는 B-트리의 변형인 B+트리를 씁니다. 데이터를 잎에만 두고, 잎끼리 연결 리스트로 이어 놓은 구조입니다. 덕분에 범위 검색(“가격 5000~10000원”)이 잎을 따라 쭉 훑는 것으로 끝납니다. 22주차 파일 시스템 편에서 다시 만날 이름이니 기억해 두세요.
7. 트라이: 문자열의 전용 트리
7.1 글자 하나 = 간선 하나
검색창에 “pro” 까지 치면 “programming”, “process”, “project” 가 뜹니다. 해시 테이블로 이것을 할 수 있을까요? 없습니다. 해시는 “pro” 를 통째로 해시하니 “programming” 과는 아무 관계도 없는 버킷에 갑니다. 정렬된 배열에서 이진 탐색으로 “pro” 가 들어갈 자리를 찾고 그 뒤를 훑는 방법은 되지만, 단어가 추가될 때마다 정렬을 유지해야 합니다.
트라이(trie) 는 이 문제를 위해 만들어진 트리입니다. 이름은 retrieval(검색)에서 왔고, “트리” 와 헷갈리지 말라고 “트라이” 로 읽습니다. 일반 트리가 노드에 키를 통째로 저장하는 것과 달리, 트라이는 글자 하나가 간선 하나입니다.
(루트)
/ \
c d
| |
a o
/ \ |
t* r g* * = 단어 끝 표시
|
d* cat, car(경유), card, dog 를 저장한 상태
typedef struct TrieNode {
struct TrieNode *child[ALPHABET]; /* a~z */
int is_end; /* 여기서 끝나는 단어가 있는가 */
} TrieNode;
노드에는 글자가 저장돼 있지 않습니다. child[0] 이 'a' 로 가는 간선, child[2] 가 'c' 로 가는 간선입니다. 어느 칸에 있느냐가 곧 글자입니다. 그래서 “cat” 을 찾는 것은 루트에서 child['c' - 'a'], child['a' - 'a'], child['t' - 'a'] 를 차례로 따라가는 세 걸음입니다.
is_end 플래그가 대단히 중요합니다. “card” 를 넣으면 c-a-r-d 경로가 생기는데, 그러면 “car” 도 저장된 걸까요? 아닙니다. r 노드에 끝 도장이 찍혀 있지 않으면 “car” 는 경로일 뿐 단어가 아닙니다. 경로의 존재와 단어의 존재는 다릅니다.
examples/trie_basic.c:
/*
* trie_basic.c - 트라이(Trie): 문자열 특화 트리
* 13주차: 해시 테이블과 고급 트리
*
* 트라이는 "글자 하나 = 간선 하나"인 트리입니다.
* "cat"을 저장하면 루트 -> c -> a -> t 경로가 생깁니다.
*
* (루트)
* / \
* c d
* | |
* a o
* / \ |
* t* r g* (* = 단어의 끝 표시)
* |
* d* cat, card, dog 저장 상태 (card는 car 경유)
*
* 강점:
* - 탐색이 "단어 길이"에만 비례 O(L). 단어가 100만 개든 상관없다!
* - 접두사 검색이 공짜: "ca"로 시작하는 단어 전부 = ca 노드의 부분트리
* (해시로는 불가능한 재주 - 자동완성의 원리)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET 26 /* 소문자 a~z */
typedef struct TrieNode {
struct TrieNode *child[ALPHABET];
int is_end; /* 여기서 끝나는 단어가 있는가 */
} TrieNode;
TrieNode *trie_create(void) {
TrieNode *n = calloc(1, sizeof(TrieNode)); /* 자식 전부 NULL */
if (n == NULL) exit(1);
return n;
}
/* 소문자 a~z 로만 된 단어인가? 트라이의 자식 배열이 26칸뿐이므로
* 그 밖의 글자("Cat", "c++")는 넣을 수 없다. 예전에는 그런 글자를
* 조용히 건너뛰어서 "Cat" 이 "at" 으로 저장되는 문제가 있었다. */
int is_lowercase_word(const char *word) {
if (*word == '\0') return 0;
for (const char *p = word; *p; p++) {
if (*p < 'a' || *p > 'z') return 0;
}
return 1;
}
/* 삽입: 글자마다 한 칸씩 내려가며 없는 노드는 만든다.
* 성공 1, 소문자가 아닌 글자가 섞여 있으면 0 (아무것도 넣지 않는다) */
int trie_insert(TrieNode *root, const char *word) {
if (!is_lowercase_word(word)) return 0;
TrieNode *cur = root;
for (const char *p = word; *p; p++) {
int idx = *p - 'a';
if (cur->child[idx] == NULL) {
cur->child[idx] = trie_create();
}
cur = cur->child[idx];
}
cur->is_end = 1; /* 마지막 노드에 "단어 끝" 도장 */
return 1;
}
/* 완전 일치 검색: 경로가 있고 끝 도장이 있어야 발견 */
int trie_search(const TrieNode *root, const char *word) {
const TrieNode *cur = root;
for (const char *p = word; *p; p++) {
int idx = *p - 'a';
if (idx < 0 || idx >= ALPHABET || cur->child[idx] == NULL) return 0;
cur = cur->child[idx];
}
return cur->is_end; /* 경로만 있고 도장 없으면 접두사일 뿐 */
}
/* 접두사 노드까지 내려가기 (없으면 NULL) */
const TrieNode *trie_walk(const TrieNode *root, const char *prefix) {
const TrieNode *cur = root;
for (const char *p = prefix; *p; p++) {
int idx = *p - 'a';
if (idx < 0 || idx >= ALPHABET || cur->child[idx] == NULL) return NULL;
cur = cur->child[idx];
}
return cur;
}
/* 접두사로 시작하는 단어 모두 출력 (부분트리 DFS + 경로 문자열 조립) */
void collect(const TrieNode *node, char *buf, int depth, int *count) {
if (node->is_end) {
buf[depth] = '\0';
printf(" %s\n", buf);
(*count)++;
}
for (int i = 0; i < ALPHABET; i++) {
if (node->child[i] != NULL) {
buf[depth] = (char)('a' + i); /* 경로에 글자 추가 */
collect(node->child[i], buf, depth + 1, count);
} /* 돌아오면 자동 덮어씀 */
}
}
int trie_prefix_list(const TrieNode *root, const char *prefix) {
const TrieNode *start = trie_walk(root, prefix);
if (start == NULL) return 0;
char buf[64];
size_t plen = strlen(prefix);
memcpy(buf, prefix, plen); /* 접두사를 버퍼에 미리 채워두고 */
int count = 0;
collect(start, buf, (int)plen, &count);
return count;
}
void trie_free(TrieNode *node) {
if (node == NULL) return;
for (int i = 0; i < ALPHABET; i++) trie_free(node->child[i]);
free(node);
}
/* 노드 수 세기 (메모리 사용량 감각) */
int trie_count_nodes(const TrieNode *node) {
if (node == NULL) return 0;
int total = 1;
for (int i = 0; i < ALPHABET; i++) total += trie_count_nodes(node->child[i]);
return total;
}
int main(void) {
TrieNode *root = trie_create();
const char *words[] = {
"cat", "car", "card", "care", "cargo",
"dog", "dot", "do",
"apple", "app", "apply",
};
int n = sizeof(words) / sizeof(words[0]);
printf("=== 단어 %d개 삽입 ===\n", n);
for (int i = 0; i < n; i++) {
trie_insert(root, words[i]);
printf("%s ", words[i]);
}
printf("\n(공유되는 접두사는 노드를 공유: car/card/care/cargo)\n");
printf("\n=== 완전 일치 검색 ===\n");
const char *queries[] = {"car", "care", "ca", "do", "d"};
for (int i = 0; i < 5; i++) {
printf("%-6s: %s\n", queries[i],
trie_search(root, queries[i])
? "단어 있음"
: "없음 (경로는 있어도 끝 도장이 없으면 접두사일 뿐)");
}
printf("\n=== 접두사 검색 (자동완성의 원리!) ===\n");
const char *prefixes[] = {"ca", "app", "do", "z"};
for (int i = 0; i < 4; i++) {
printf("'%s'로 시작하는 단어:\n", prefixes[i]);
int count = trie_prefix_list(root, prefixes[i]);
if (count == 0) printf(" (없음)\n");
}
printf("\n=== 비용 감각 ===\n");
printf("노드 수: %d개 (노드당 포인터 26개 = %zu바이트)\n",
trie_count_nodes(root),
sizeof(TrieNode));
printf("트라이의 약점: 메모리를 많이 쓴다.\n");
printf("(자식 배열 대신 리스트/해시를 쓰거나 압축 트라이로 절약 가능)\n");
trie_free(root);
return 0;
}
$ gcc -Wall -Wextra -std=c11 -g examples/trie_basic.c -o build/trie_basic
$ ./build/trie_basic
=== 단어 11개 삽입 ===
cat car card care cargo dog dot do apple app apply
(공유되는 접두사는 노드를 공유: car/card/care/cargo)
=== 완전 일치 검색 ===
car : 단어 있음
care : 단어 있음
ca : 없음 (경로는 있어도 끝 도장이 없으면 접두사일 뿐)
do : 단어 있음
d : 없음 (경로는 있어도 끝 도장이 없으면 접두사일 뿐)
=== 접두사 검색 (자동완성의 원리!) ===
'ca'로 시작하는 단어:
car
card
care
cargo
cat
'app'로 시작하는 단어:
app
apple
apply
'do'로 시작하는 단어:
do
dog
dot
'z'로 시작하는 단어:
(없음)
=== 비용 감각 ===
노드 수: 19개 (노드당 포인터 26개 = 216바이트)
트라이의 약점: 메모리를 많이 쓴다.
(자식 배열 대신 리스트/해시를 쓰거나 압축 트라이로 절약 가능)
트라이
"ca" 는 없다고 나오는데 "car" 는 있다고 나오는 것, 그리고 "do" 는 단어이면서 동시에 dog, dot 의 접두사이기도 한 것. is_end 의 역할이 결과에 그대로 드러납니다.
7.2 코드 해설
삽입(trie_insert) 은 글자마다 한 칸씩 내려가며 없는 노드는 만듭니다.
for (const char *p = word; *p; p++) {
int idx = *p - 'a';
if (cur->child[idx] == NULL) {
cur->child[idx] = trie_create();
}
cur = cur->child[idx];
}
cur->is_end = 1; /* 마지막 노드에 "단어 끝" 도장 */
*p - 'a' 는 4주차에서 본 문자 산술입니다. 'c' - 'a' 는 99 − 97 = 2 입니다. 이 값이 child 배열의 인덱스가 됩니다. 이미 있는 경로는 그대로 타고 내려가므로 car, card, care, cargo 는 c-a-r 세 노드를 공유합니다. 실행 결과의 “노드 수 19개” 가 그 증거입니다. 단어 11개의 글자 수를 다 더하면 40인데 노드는 19개뿐입니다.
trie_create 가 calloc 을 쓰는 것도 눈여겨보세요. 자식 포인터 26개를 전부 NULL 로 초기화해야 하는데, calloc 은 0으로 채워 주니 한 줄로 끝납니다.
검색(trie_search) 은 경로를 따라간 뒤 끝 도장을 확인합니다.
return cur->is_end; /* 경로만 있고 도장 없으면 접두사일 뿐 */
이 한 줄을 return 1; 로 바꾸면 “ca” 도 단어로 판정됩니다. 트라이에서 가장 흔한 실수입니다.
7.3 트라이의 필살기: 접두사 검색
탐색 시간이 단어 길이에만 비례합니다. O(L) 입니다. 사전에 단어가 100만 개든 10억 개든 “cat” 을 찾는 데는 세 걸음입니다. 해시도 O(1)이지만 해시 계산 자체가 문자열 전체를 훑으므로 사실상 O(L)로 비슷합니다.
진짜 차이는 다른 데 있습니다. “ca” 로 시작하는 단어 전부 = ca 노드의 부분 트리입니다. 접두사 노드까지 내려간 뒤 그 아래를 DFS 로 훑으면 끝입니다.
void collect(const TrieNode *node, char *buf, int depth, int *count) {
if (node->is_end) {
buf[depth] = '\0'; /* 현재까지의 경로가 곧 단어 */
printf(" %s\n", buf);
(*count)++;
}
for (int i = 0; i < ALPHABET; i++) {
if (node->child[i] != NULL) {
buf[depth] = (char)('a' + i); /* 경로에 글자 추가 */
collect(node->child[i], buf, depth + 1, count);
} /* 돌아오면 자동 덮어씀 */
}
}
buf 가 현재 경로를 담는 배열입니다. 내려가면서 글자를 쌓고, 단어 끝을 만나면 \0 을 붙여 출력합니다. 'ca' 로 시작하는 단어를 찾을 때 buf 가 어떻게 변하는지 따라가 봅시다. 접두사 “ca” 가 미리 채워져 있고 depth 는 2에서 시작합니다.
depth 2, 노드 'a' (ca): is_end 아님. 자식 r(17), t(19) 순서로
depth 3, buf="car", 노드 r: is_end → "car" 출력
depth 4, buf="card", 노드 d: is_end → "card" 출력
depth 4, buf="care", 노드 e: is_end → "care" 출력
depth 4, buf="carg", 노드 g: 자식 o 로
depth 5, buf="cargo": is_end → "cargo" 출력
depth 3, buf="cat", 노드 t: is_end → "cat" 출력
되돌아 나올 때 명시적으로 지우지 않아도 되는 이유가 보입니다. buf[3] 에 'd' 를 썼다가 형제 'e' 로 갈 때 같은 자리 buf[3] 을 덮어쓰기 때문입니다. 12주차 file_tree 의 경로 출력에서 본 백트래킹 패턴입니다.
출력 순서가 알파벳순(car, card, care, cargo, cat)인 것도 공짜로 얻은 성질입니다. 자식을 0(a)부터 25(z)까지 순서대로 돌기 때문입니다. 해시 테이블로는 절대 얻을 수 없는 성질입니다.
trie_prefix_list 의 시작 부분도 눈여겨보세요.
char buf[64];
size_t plen = strlen(prefix);
memcpy(buf, prefix, plen); /* 접두사를 버퍼에 미리 채워두고 */
int count = 0;
collect(start, buf, (int)plen, &count);
접두사 노드부터 탐색을 시작하므로 버퍼 앞부분에는 접두사를 미리 채워 둡니다. depth 를 plen 부터 시작하는 이유도 같습니다. 이렇게 해야 출력이 “car” 이지 “r” 이 되지 않습니다. buf[64] 는 이 예제의 단어가 짧아서 충분하지만, 실제 사전이라면 가장 긴 단어 길이를 확인하고 잡아야 합니다.
7.4 실험: 대문자를 넣으면?
이 트라이는 자식 배열이 26칸이라 소문자 a~z 만 다룰 수 있습니다. 그러면 "Cat" 을 넣으면 어떻게 될까요? 이 글을 쓰기 전의 trie_insert 는 소문자가 아닌 글자를 continue 로 조용히 건너뛰었습니다. 그 버전으로 실험한 결과입니다.
"Cat" 삽입 후 검색: Cat=0 cat=0 at=1
“Cat” 을 넣었는데 “Cat” 도 “cat” 도 없고, “at” 이 있습니다. 'C' 를 건너뛰고 'a', 't' 만 넣은 것입니다. 오류도 없이 엉뚱한 단어가 저장되는 것은 최악의 동작입니다. 그래서 예제를 고쳤습니다. 지금 코드의 trie_insert 는 소문자가 아닌 글자가 하나라도 있으면 아무것도 넣지 않고 0을 돌려줍니다.
"Cat" 삽입: 거부
"cat" 삽입: 성공
검색 at=0 cat=1, 노드 수 4
대문자를 받고 싶다면 넣기 전에 tolower 로 바꾸거나, ALPHABET 을 늘리고 인덱스 계산을 바꾸면 됩니다. 어느 쪽이든 “조용히 다른 것을 저장” 하는 것보다 “거부” 가 낫습니다. 이번 주 예제들이 map_put 에서 실패를 0으로 돌려주는 것과 같은 원칙입니다.
7.5 트라이의 약점: 메모리
실행 결과의 마지막 줄이 트라이의 약점을 정직하게 보여 줍니다. 단어 11개를 저장하는 데 노드 19개, 노드 하나가 216바이트이니 약 4KB 입니다. 문자열 11개를 그냥 저장하면 100바이트도 안 되는데 말입니다. 216바이트는 8주차에서 배운 대로 계산할 수 있습니다. 포인터 26개 × 8바이트 = 208, int 4바이트, 그리고 8바이트 정렬을 맞추려는 패딩 4바이트입니다.
원인은 child[26] 배열입니다. 노드마다 포인터 26개를 들고 있는데, 대부분 NULL 입니다. 노드 19개 × 26 = 494 개의 포인터 중 실제로 쓰이는 것은 18개(간선 수 = 노드 수 − 1)뿐입니다. 실전에서는 이렇게 줄입니다.
- 자식을 연결 리스트나 해시로: 실제 존재하는 자식만 저장합니다. 메모리는 줄고 탐색은 살짝 느려집니다.
- 압축 트라이(radix tree): 자식이 하나뿐인 경로를 하나의 간선으로 압축합니다. c-a-r-g-o 처럼 갈림길 없는 구간을 “argo” 한 간선으로 만듭니다. 리눅스 커널의 라우팅 테이블이 이 방식입니다.
- 더블 어레이 트라이: 배열 두 개로 압축합니다. 한국어 형태소 분석기 같은 곳에서 씁니다.
연습 문제 10번으로 남겨 두겠습니다.
8. 실습 프로젝트
projects/ 폴더에는 이번 주에 배운 해시와 트라이를 종합한 세 프로그램이 있습니다. 아래에서는 각 프로그램의 구조와 핵심 함수, 그리고 실제로 돌려 본 화면을 정리합니다. 전체 코드는 해당 .c 파일을 열어 확인하세요. 세 개 모두 200~300줄이라 글에 다 싣기에는 깁니다.
$ cd week13
$ make # 전체 빌드
$ ./build/kv_store # 또는 doc_search, autocomplete
프로젝트 1: 키-값 저장소, Redis 스타일 (kv_store.c)
이번 주 해시 기술의 종합판입니다. djb2 해시 + 체이닝 + 로드 팩터 0.75 자동 리사이징에 파일 지속성까지 붙였습니다. 명령어는 Redis 와 같은 이름을 씁니다.
typedef struct Entry {
char *key;
char *value; /* 값도 동적 할당 문자열! */
struct Entry *next;
} Entry;
typedef struct {
Entry **bucket;
size_t bucket_count;
size_t count;
} Store;
char *dup_string(const char *s); /* strdup 직접 구현 */
int store_init(Store *st, size_t buckets);
int store_resize(Store *st); /* 2배 확장 + rehash */
int store_set(Store *st, const char *key, const char *value);
const char *store_get(const Store *st, const char *key);
int store_del(Store *st, const char *key);
void store_keys(const Store *st);
void store_stats(const Store *st); /* 로드 팩터, 최장 사슬 */
int store_save(const Store *st, const char *filename); /* 9주차 파일 I/O */
int store_load(Store *st, const char *filename);
void store_free(Store *st);
실제로 돌려 본 화면입니다. kv> 뒤가 입력한 명령입니다.
$ ./build/kv_store
키-값 저장소 (Redis 스타일)
명령: SET/GET/DEL/EXISTS/KEYS/STATS/SAVE/LOAD/QUIT
=====================================
kv> SET name kim
OK
kv> GET name
"kim"
kv> SET lang C
OK
kv> KEYS
1) "name"
2) "lang"
kv> STATS
keys=2, buckets=8, load=0.25, used_buckets=2, max_chain=1
kv> DEL name
1
kv> GET name
(nil)
kv> EXISTS lang
1
kv> SET name lee
OK
kv> SET name park
OK
kv> GET name
"park"
kv> SAVE kv.txt
OK: 2개 항목을 'kv.txt'에 저장
kv> QUIT
저장소 종료 (누수 0)
GET 이 없는 키에 (nil) 을, DEL 이 지운 개수 1 을 돌려주는 것까지 Redis 와 같습니다. 저장된 파일은 이렇게 생겼습니다.
$ od -c kv.txt
0000000 n a m e \t p a r k \n l a n g \t C
0000020 \n
한 줄에 키 탭 값 입니다. 9주차의 od -c 로 보면 탭(\t)과 줄바꿈(\n)이 구분자인 것이 보입니다. 탭을 쓴 이유는 값에 공백이 들어갈 수 있기 때문입니다. SET msg hello world 처럼요. 다시 실행해서 LOAD kv.txt 를 치면 두 항목이 살아 돌아옵니다. 프로그램을 껐다 켜도 데이터가 남는, 진짜 데이터베이스의 첫걸음입니다.
눈여겨볼 점 1: 덮어쓰기의 순서. 위 화면에서 name 을 lee 로, 다시 park 로 바꿨습니다. store_set 은 새 값을 먼저 확보하고, 성공한 뒤에 옛 값을 해제합니다.
char *nv = dup_string(value); /* 1) 새 값 먼저 확보 */
if (nv == NULL) return 0; /* 2) 실패하면 기존 데이터 그대로 */
free(e->value); /* 3) 성공했으니 옛 값 해제 */
e->value = nv;
순서를 뒤집어 free(e->value) 를 먼저 하면, 그다음 할당이 실패했을 때 데이터를 잃습니다. 게다가 e->value 가 해제된 주소를 그대로 가리키는 댕글링 포인터(7주차)가 됩니다. “실패해도 원래 상태는 지킨다” 는 원칙을 강한 예외 안전성이라고 부르는데, C++ 에서 나온 용어지만 C 에서도 그대로 통하는 좋은 습관입니다.
눈여겨볼 점 2: dup_string. POSIX 에는 strdup 이 있지만 C11 표준에는 없습니다(C23 에서야 표준이 됐습니다). -std=c11 로 컴파일하면 strdup 의 선언이 보이지 않아 1주차 10절에서 본 “implicit declaration” 경고가 납니다. 그래서 세 줄짜리 dup_string 을 직접 만들었습니다. 표준을 정확히 지키려 할 때 겪는 흔한 상황이고, 해결도 간단합니다.
눈여겨볼 점 3: 입력 파싱. 명령 한 줄은 fgets 로 읽고 sscanf(line, "%15s %255s %255[^\n]", cmd, arg1, arg2) 로 쪼갭니다. %15s 처럼 폭을 적는 것은 4주차에서 배운 버퍼 오버플로 방지이고, %255[^\n] 은 “줄바꿈이 아닌 글자를 255개까지” 라서 값에 공백이 있어도 통째로 받습니다. 입력이 끝나면(fgets 가 NULL) QUIT 없이도 정리하고 종료합니다.
확장 아이디어: TTL(유효 기간) 추가, 정수 값에 INCR 연산, 바이너리 저장 형식(9주차의 fwrite), 개방 주소법으로 바꿔 성능 비교
프로젝트 2: 문서 검색 엔진 (doc_search.c)
구글이 수십억 페이지를 순식간에 검색하는 비밀, 역색인(inverted index) 을 만듭니다.
일반 색인: 문서 → 단어들 (책의 목차)
역색인 : 단어 → 문서들 (책 뒤의 '찾아보기')
typedef struct Word {
char name[MAX_WORD];
unsigned doc_mask; /* i번 비트 = i번 문서에 등장 */
int freq[MAX_DOCS]; /* 문서별 등장 횟수 (랭킹용) */
struct Word *next;
} Word;
Word *index_find(Index *idx, const char *name);
void index_add(Index *idx, const char *name, int doc_id);
void index_build(Index *idx); /* 전체 문서를 단어로 쪼개 색인 */
void show_results(Index *idx, unsigned mask, const char *terms[], int nterms);
void search(Index *idx, const char *query); /* 공백으로 나눈 단어들의 AND 검색 */
이 프로그램은 입력 없이 문서 6개를 색인하고 검색 5개를 자동으로 돌립니다.
$ ./build/doc_search
문서 검색 엔진 (역색인)
=====================================
색인 대상 문서 6개:
[문서0] the quick brown fox jumps over the lazy dog
[문서1] a quick brown cat sleeps on the warm mat
[문서2] the lazy dog sleeps all day in the sun
[문서3] programming in c is fun and powerful
[문서4] the c language gives you power over memory
[문서5] a fox and a cat play in the sun
색인 완료: 고유 단어 30개
역색인 예시:
"the" -> 문서 { 0 1 2 4 5 }
"fox" -> 문서 { 0 5 }
"c" -> 문서 { 3 4 }
"sleeps" -> 문서 { 1 2 }
검색: "fox"
[문서0, 점수 1] the quick brown fox jumps over the lazy dog
[문서5, 점수 1] a fox and a cat play in the sun
검색: "quick brown"
[문서0, 점수 2] the quick brown fox jumps over the lazy dog
[문서1, 점수 2] a quick brown cat sleeps on the warm mat
검색: "the sun"
[문서2, 점수 3] the lazy dog sleeps all day in the sun
[문서5, 점수 2] a fox and a cat play in the sun
검색: "c memory"
[문서4, 점수 2] the c language gives you power over memory
검색: "elephant"
('elephant'는 어떤 문서에도 없음)
결과 없음
...
“the sun” 검색에서 문서2 가 점수 3인 이유를 따져 보세요. 문서2 에는 “the” 가 두 번, “sun” 이 한 번 나옵니다. 문서5 는 각각 한 번씩이라 2점입니다. 랭킹은 등장 횟수의 합(freq)입니다.
눈여겨볼 점: 비트마스크로 하는 교집합. 단어가 등장한 문서 집합을 unsigned doc_mask 의 비트로 표현합니다. 3번 비트가 켜져 있으면 3번 문서에 등장한다는 뜻입니다. “fox” 는 문서 0과 5에 있으니 doc_mask 는 2진수로 100001, 즉 33 입니다. 그러면 AND 검색(두 단어를 모두 포함한 문서)이 비트 연산 한 번으로 끝납니다.
mask &= w->doc_mask; /* 교집합 = 비트 AND! */
“quick” 의 마스크 000011(문서 0, 1)과 “brown” 의 마스크 000011 을 AND 하면 000011, 문서 0과 1입니다. 리스트 두 개를 순회하며 교집합을 구하는 코드가 CPU 명령 하나로 줄어듭니다. 3주차에서 배운 비트 연산이 이렇게 쓰입니다. 대신 문서 수가 unsigned 의 비트 수(32개)로 제한되니, 그 이상은 비트 배열이나 정렬된 문서 ID 리스트로 바꿔야 합니다.
색인을 만드는 흐름도 짚어 둡니다. index_build 는 문서 문자열을 strtok(copy, " ") 로 공백에서 자르고(4주차), 각 단어를 tolower 로 소문자로 바꾼 뒤 index_add 에 넘깁니다. 원본 문자열을 자르면 안 되니 snprintf 로 복사본을 먼저 만드는 것도 4주차에서 본 strtok 의 주의점입니다. index_add 는 해시 테이블에서 단어를 찾아 없으면 새 Word 를 만들고, 있든 없든 doc_mask |= (1U << doc_id) 로 이 문서의 비트를 켜고 freq[doc_id]++ 로 횟수를 셉니다. “the” 처럼 여러 문서에 나오는 단어는 Word 하나에 비트가 여러 개 켜집니다.
search 는 mask = ~0U(모든 비트가 1, 즉 전체 집합)에서 시작해서 검색어마다 &= 로 좁혀 갑니다. 3주차의 비트 반전이 “전체 집합” 을 만드는 데 쓰였습니다. 검색어 중 하나라도 색인에 없으면 교집합은 어차피 빈 집합이니 mask = 0 으로 두고 바로 멈춥니다. “elephant” 검색에서 그 문구가 나온 것입니다. 마지막의 mask &= (1U << NUM_DOCS) - 1; 은 ~0U 로 시작한 탓에 켜져 있는 6번 이상의 비트(존재하지 않는 문서)를 끄는 뒷정리입니다.
실제 검색 엔진은 랭킹에 “흔한 단어일수록 가치가 낮다” 는 보정을 넣습니다. “the” 는 거의 모든 문서에 있으니 점수를 깎고, “elephant” 처럼 드문 단어는 점수를 올립니다. 그것이 TF-IDF 입니다.
확장 아이디어: 파일에서 문서 읽기(9주차), OR/NOT 검색, TF-IDF 랭킹, 문서 수 제한 풀기(비트마스크 → 동적 배열), 구문 검색(“quick brown” 이 붙어 있는 경우만)
프로젝트 3: 자동 완성 시스템 (autocomplete.c)
트라이 + 빈도의 조합입니다. C 키워드와 함수 34개를 인기도와 함께 트라이에 담고, 접두사를 입력하면 빈도 높은 순 상위 5개를 제안합니다.
typedef struct TrieNode {
struct TrieNode *child[ALPHABET];
int freq; /* 0이면 단어 아님, >0이면 사용 빈도 */
} TrieNode;
typedef struct { char word[MAX_WORD]; int freq; } Suggestion;
typedef struct { Suggestion item[MAX_SUGGEST]; int count; } TopList;
void trie_insert(TrieNode *root, const char *word, int freq);
TrieNode *trie_walk(TrieNode *root, const char *prefix);
void top_add(TopList *top, const char *word, int freq); /* 상위 N 정렬 유지 삽입 */
void collect(TrieNode *node, char *buf, int depth, TopList *top);
void suggest(TrieNode *root, const char *prefix);
자동완성
is_end 대신 freq 를 쓴 점에 주목하세요. 0이면 단어가 아니고, 양수면 단어이면서 동시에 인기도입니다. 플래그 하나로 두 가지 일을 하는 셈입니다.
실제로 돌려 본 화면입니다. 입력> 뒤가 친 것입니다.
$ ./build/autocomplete
C 자동 완성 시스템 (사전: 34개 단어)
사용법: 접두사 입력 -> 제안 / !단어 -> 사용 기록(빈도+1) / q -> 종료
=====================================
입력> str
1. struct (빈도 80)
2. strlen (빈도 65)
3. strcmp (빈도 50)
4. strcpy (빈도 45)
5. string (빈도 40)
입력> !strtok
'strtok' 사용 기록(+10)! (다음 제안부터 순위 반영)
입력> !strtok
'strtok' 사용 기록(+10)! (다음 제안부터 순위 반영)
입력> !strtok
'strtok' 사용 기록(+10)! (다음 제안부터 순위 반영)
입력> str
1. struct (빈도 80)
2. strlen (빈도 65)
3. strtok (빈도 55)
4. strcmp (빈도 50)
5. strcpy (빈도 45)
입력> zz
'zz'로 시작하는 단어 없음
입력> q
종료 (트라이 해제 - 누수 0)
!단어 로 사용을 기록하면 빈도가 10씩 올라 다음 제안의 순위가 바뀝니다. 처음에 25로 순위 밖이던 strtok 이 세 번 사용 후 55가 되어 3위로 올라왔고, 5위였던 string 이 밀려났습니다. 검색 엔진이 여러분의 입력에서 학습하는 원리의 축소판입니다. 참고로 사전이 C 키워드와 표준 함수라서 pro 나 com 같은 접두사는 “없음” 이 나옵니다. str, pri, f, s 같은 것으로 시험해 보세요.
눈여겨볼 점: 규모에 맞는 자료구조. 상위 5개를 유지하는 데 top_add 는 정렬 유지 삽입을 씁니다. 11주차의 우선순위 큐나 12주차의 힙을 쓸 수도 있었지만, 원소가 5개뿐이라 힙은 과합니다. 삽입 정렬 한 스텝이 훨씬 단순하고, 이 규모에서는 더 빠르기까지 합니다.
int pos = top->count;
while (pos > 0 && top->item[pos - 1].freq < freq) pos--;
if (pos >= MAX_SUGGEST) return; /* 상위 N에 못 든다 -> 버림 */
str 을 입력했을 때 collect 가 트라이를 알파벳순으로 돌며 top_add 를 부르는 순서와, 그때마다 상위 5개 목록이 어떻게 변하는지 따라가 봅시다. str 아래의 단어는 사전에 여섯 개 있습니다.
| 순서 | 단어 (빈도) | 들어갈 자리 | 목록 |
|---|---|---|---|
| 1 | strcmp (50) | 0 | strcmp |
| 2 | strcpy (45) | 1 | strcmp, strcpy |
| 3 | string (40) | 2 | strcmp, strcpy, string |
| 4 | strlen (65) | 0 (셋을 밀어냄) | strlen, strcmp, strcpy, string |
| 5 | strtok (25) | 4 | strlen, strcmp, strcpy, string, strtok |
| 6 | struct (80) | 0 (strtok 탈락) | struct, strlen, strcmp, strcpy, string |
while (pos > 0 && top->item[pos - 1].freq < freq) pos--; 가 “나보다 빈도가 낮은 항목을 지나 앞으로” 자리를 찾고, 자리가 5번째(MAX_SUGGEST) 이상이면 그냥 버립니다. 이미 5개가 찬 상태에서 앞에 끼어들면 맨 뒤 항목이 밀려 떨어집니다. 6번 단계에서 strtok 이 그렇게 탈락했고, !strtok 세 번으로 55가 된 뒤에는 3번 자리에 끼어들며 string 이 대신 떨어졌습니다. 15주차에서 배울 삽입 정렬의 한 걸음과 같은 동작입니다.
빅오만 보면 힙이 우월하지만 n 이 5일 때는 상수가 지배합니다. 자료구조도 규모에 맞게 고르는 것이 엔지니어링입니다.
확장 아이디어: 파일에서 사전 로드, 오타 허용(레벤슈타인 거리, 16주차 예고), 한글 지원(유니코드 처리), 최근 사용 시각까지 반영한 랭킹
9. 자주 하는 실수와 함정
이번 주에 직접 재현해 본 것이 많습니다. 어느 절의 실험이었는지 함께 적었습니다.
1. 해시만 믿고 키 비교 생략 (2.4절). 같은 버킷 ≠ 같은 키. apple 을 찾았는데 mango 의 가격이 나오고, 넣은 적 없는 kiwi 가 “있다” 고 나옵니다. 테스트 데이터가 적으면 충돌이 안 나서 통과해 버리기 때문에, 운영에 올라간 뒤에야 터지는 무서운 버그입니다.
2. 키를 복사하지 않고 포인터만 저장 (2.5절). 호출자가 버퍼를 재사용하면 테이블 속 키가 바뀝니다. fgets 로 읽은 줄을 그대로 키로 넣는 코드가 특히 위험합니다.
3. 개방 주소법에서 삭제를 EMPTY 로 (3.4절). 탐사 사슬이 끊겨, 멀쩡히 들어 있는 mango 를 못 찾게 됩니다. 묘비는 선택이 아니라 필수입니다.
4. 묘비를 만나자마자 삽입 (3.4절). 뒤에 같은 키가 있을 수 있어 중복이 생깁니다. EMPTY 를 만나 “없다” 가 확정된 뒤에 첫 묘비 자리에 넣어야 합니다.
5. 리사이징 후 재배치 생략 (4.2절). % bucket_count 의 분모가 바뀌면 키의 자리가 달라집니다. rehash 없는 리사이징은 데이터 유실과 같습니다. 새 자리를 옛 분모로 계산하는 것도 같은 결과입니다.
6. 로드 팩터 방치 (2.6절, 3.5절). 체이닝은 사슬이 길어져 느려지고, 개방 주소법은 테이블이 완전히 차면 무한 루프까지 갑니다. 예제에서 CAPACITY - 1 로 한 칸을 남긴 이유입니다.
7. free 순서를 거꾸로 (2.3절). free(e) 를 먼저 하고 free(e->key) 를 하면 해제된 메모리 접근입니다. 항상 안쪽부터 해제하세요.
8. 연결 리스트 재배치 중 next 분실 (4.2절). e->next 를 덮어쓰기 전에 저장해야 합니다. 리사이징과 map_free 양쪽 모두에서 지켜야 하는 규칙입니다.
9. 트라이에서 경로 존재 = 단어 존재로 착각 (7.2절). is_end 확인을 잊으면 “ca” 도 단어로 판정됩니다.
10. 다룰 수 없는 입력을 조용히 변형 (7.4절). 옛 trie_insert 는 “Cat” 을 “at” 으로 저장했습니다. 받을 수 없는 입력은 거부하고 알리는 것이 낫습니다.
11. 해시 테이블에 정렬이나 범위 검색 기대 (5.1절). 해시는 순서를 파괴합니다. 그게 필요하면 트리로 가세요.
12. 벤치마크 결과를 쓰지 않아 최적화에 지워짐 (5절). sum 에 더해 마지막에 출력하세요. 10주차와 같은 함정입니다.
10. 연습 문제
기본 문제
- 해시 함수 실험:
hash_functions.c에 자신만의 해시 함수를 추가해 분포를 비교해 보세요. 예를 들어hash * 31 + c(자바의String.hashCode)는 djb2 와 얼마나 다른가요? 시작값을 0으로 바꾸면 짧은 단어에서 어떤 일이 생기나요? - 버킷 수 실험: 1.5절의 순차 키 실험을
hash_functions.c에 넣어,% 16과% 17의 분포 차이를 직접 확인하세요. - 단어 빈도 세기: 텍스트 파일을 읽어(9주차) 단어별 등장 횟수를 해시맵으로 세고, 상위 10개를 출력하세요.
- 중복 제거: 정수 배열에서 중복을 제거하세요. 해시를 쓰면 O(n), 정렬 후 제거하면 O(n log n)입니다. 둘 다 구현해 시간을 비교해 보세요.
- 애너그램 그룹: 단어 목록을 애너그램(구성 글자가 같은 단어)끼리 묶으세요. 힌트: 1.4절에서 “글자 합” 해시가 애너그램을 충돌시키던 성질을 거꾸로 이용하면 됩니다. 정렬한 글자열을 키로 쓰세요.
- 트라이 단어 수: 트라이에 저장된 단어의 총 개수를 세는 함수를 작성하세요.
is_end가 1인 노드를 세면 됩니다.
심화 문제
- 묘비 버그 재현: 3.4절 실험을 여러분 손으로 다시 해 보세요. 그리고 grape 를 지웠을 때는 왜 버그가 안 나는지 설명하세요.
- 개방 주소법 리사이징:
hash_open_addr.c에 로드 팩터 검사와 리사이징을 추가하세요. 리사이징할 때 묘비는 어떻게 처리해야 할까요? - B-트리 삭제:
btree_basic.c에 삭제를 추가하세요. 키가 최소 개수 아래로 떨어진 노드는 형제에게 빌리거나 형제와 병합해야 합니다. - 압축 트라이: 자식이 하나뿐인 경로를 하나의 간선으로 합친 radix tree 를 구현하고, 일반 트라이와 노드 수를 비교하세요.
- LRU 캐시: 해시맵 + 이중 연결 리스트로 “가장 오래 안 쓴 항목을 버리는” 캐시를 만드세요. 면접 단골 문제입니다.
마치며
이번 주에 배운 것을 정리합니다.
- 해시 함수: 키 → 숫자. 균등 분포가 생명이고, 버킷 수와 한 쌍입니다. djb2 면 충분히 훌륭합니다.
- 체이닝: 버킷 = 연결 리스트. 단순하고 견고하며 가득 차지 않습니다. 사슬 길이가 성능입니다.
- 개방 주소법: 옆 칸 탐사. 캐시 친화적이고, 삭제는 반드시 묘비로.
- 탐사 전략: 선형(캐시 최고) / 이차 / 더블 해싱(클러스터 최소)
- 로드 팩터: 0.75 넘으면 2배 + rehash. 평균 O(1)을 유지하는 비용입니다.
- B-트리: 노드 = 디스크 블록. 높이 = 디스크 읽기 횟수. 데이터베이스의 심장입니다.
- 트라이: 글자 = 간선. O(단어 길이) 탐색 + 접두사 검색이라는 필살기.
이것으로 탐색 자료구조 3부작(BST → AVL → 해시/B-트리/트라이)이 완성됐습니다. 이제 여러분은 “데이터를 어떻게 저장하고 찾을 것인가” 라는 질문 앞에서 상황별로 정답을 고를 수 있습니다. 순서가 필요 없으면 해시, 범위 검색이 필요하면 트리, 디스크에 있으면 B-트리, 접두사가 중요하면 트라이. 이 판단이 곧 실력입니다.
그리고 한 가지 더. 이번 주 코드를 보면서 눈치채셨을 텐데, 우리는 이전 주차의 부품을 계속 재사용했습니다. 체이닝에는 10주차의 연결 리스트가, 리사이징에는 10주차의 분할 상환이, 역색인에는 3주차의 비트 연산이, 자동완성 랭킹에는 11주차의 우선순위 큐 발상이, 저장 기능에는 9주차의 파일 입출력이 들어갔습니다. 자료구조 공부가 쌓이는 방식이 원래 이렇습니다.
다음 주는 자료구조의 마지막 관문, 그래프입니다. 트리가 “계층” 이었다면 그래프는 “관계” 입니다. 친구 관계, 도로망, 인터넷. 이번 주의 해시 테이블이 그래프의 인접 리스트에서 또 등장하니 기대하세요.
해시 테이블은 “배우고 나면 세상이 달라 보이는” 자료구조 중 하나입니다. 오늘부터 여러분이 쓰는 모든 언어의 딕셔너리 뒤에 무엇이 있는지 보일 겁니다.
체크리스트
- [ ] djb2 로
"cat"의 해시값을 손으로 계산할 수 있다 - [ ] 좋은 해시 함수의 세 조건(결정적, 균등, 빠름)을 말할 수 있다
- [ ] 글자 합 해시가 애너그램에서 충돌하는 이유를 안다
- [ ] 버킷 수가 2의 거듭제곱일 때 순차 키가 몰리는 이유를 설명할 수 있다
- [ ] 충돌이 왜 피할 수 없는지 비둘기집 원리와 생일 역설로 설명할 수 있다
- [ ] 체이닝 put/get/remove 를 직접 구현할 수 있다
- [ ] 같은 버킷에서도
strcmp로 키를 확인하지 않으면 무슨 일이 생기는지 봤다 - [ ] 키를 복사하지 않으면 무슨 일이 생기는지 봤다
- [ ] 로드 팩터가 커질 때 조회 시간이 어떻게 변하는지 측정했다
- [ ] 개방 주소법의 선형 탐사와 wrap-around 를 손으로 따라갈 수 있다
- [ ] 묘비 없이 삭제하면 어떤 키를 못 찾게 되는지 재현했다
- [ ] 삽입할 때 묘비를 만나도 바로 넣지 않고 계속 탐사하는 이유를 안다
- [ ] 1차 클러스터링과 이차 탐사, 더블 해싱의 해결 원리를 안다
- [ ] 로드 팩터 초과 시 리사이징 + rehash 를 구현할 수 있다
- [ ] 리사이징이 O(n)인데도 삽입이 평균 O(1)인 이유를 설명할 수 있다
- [ ] 해시 vs 트리 선택 기준(순서, 범위 필요 여부)을 말할 수 있다
- [ ] B-트리 노드가 큰 이유를 디스크 블록으로 설명할 수 있다
- [ ] B-트리 분할(가운데 키 승진)을 한 단계씩 그릴 수 있다
- [ ] 순차 삽입에서 BST 와 B-트리의 높이가 어떻게 다른지 숫자로 말할 수 있다
- [ ] 트라이의
is_end가 왜 필요한지 안다 - [ ] 접두사 검색을 DFS + 백트래킹으로 구현할 수 있다
- [ ] 세 프로젝트를 빌드하고 valgrind 로 누수 0을 확인했다
- [ ] (도전)
kv_store에 TTL 을,autocomplete에 파일 사전을 추가해 봤다
참고 자료
- CLRS(Introduction to Algorithms) Chapter 11 (Hash Tables), Chapter 18 (B-Trees)
- djb2 등 해시 함수 모음
- B-tree 시각화
- Trie (Wikipedia)
- Python dict 구현 해설 (CPython)
- 다음 주차: 14주차 그래프 자료구조와 탐색