충돌 처리
체이닝과 프로빙을 알아봅니다
충돌 처리은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
충돌 문제
충돌은 서로 다른 두 키가 같은 버킷으로 해시될 때 발생합니다. 충돌은 피할 수 없으므로 모든 해시 테이블에는 하나의 슬롯에 여러 키를 저장하기 위한 전략이 필요합니다.
두 가지 주요 방식은 체이닝과 개방 주소 지정입니다.
분리 연결법
분리 연결법에서는 각 버킷이 항목의 연결 리스트를 보유합니다. 충돌이 발생하면 해당 버킷의 리스트 뒤에 항목을 추가하거나 앞에 삽입하면 됩니다.
- 버킷에는 리스트의 선두가 저장됩니다
- 조회할 때 하나의 짧은 리스트만 순회합니다
연결 노드 구조
각 노드에는 키, 값, next 포인터가 저장됩니다. 테이블은 노드 포인터의 배열입니다.
#include <stdio.h>
typedef struct Node {
char *key;
int value;
struct Node *next;
} Node;
int main(void) {
Node *buckets[8] = {0};
printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
return 0;
}연결법으로 삽입하기
버킷 리스트의 앞에 삽입하는 작업은 O(1)입니다. 여기서는 작은 연결 구조를 직접 만들고 출력합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int key; struct Node *next; } Node;
Node *prepend(Node *head, int key) {
Node *n = malloc(sizeof *n);
n->key = key; n->next = head;
return n;
}
int main(void) {
Node *bucket = NULL;
bucket = prepend(bucket, 10);
bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
for (Node *p = bucket; p; p = p->next)
printf("%d ", p->key);
printf("\n");
return 0;
}개방 주소법
개방 주소법에서는 모든 항목이 버킷 배열에 직접 저장됩니다. 충돌이 발생하면 정해진 순서에 따라 다른 빈 슬롯을 탐색합니다.
추가 노드를 할당하지 않으므로 캐시 친화적입니다.
선형 탐사
선형 탐사는 다음 슬롯을 확인하고, 그다음 슬롯을 계속 확인하다가 배열의 끝에 도달하면 처음으로 돌아갑니다: (h + i) % capacity.
간단하고 캐시 친화적이지만 군집화가 발생하는 단점이 있습니다.
#include <stdio.h>
int main(void) {
int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
unsigned h = 2, cap = 8;
for (unsigned i = 0; i < cap; i++) {
unsigned idx = (h + i) % cap;
if (!slots[idx]) { printf("insert at %u\n", idx); break; }
}
return 0;
}이차 탐사
이차 탐사는 (h + i*i) % capacity를 사용해 탐사 위치를 분산시키고 1차 군집화를 줄입니다.
#include <stdio.h>
int main(void) {
unsigned h = 3, cap = 8;
for (unsigned i = 0; i < 4; i++)
printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
return 0;
}이중 해싱
이중 해싱은 두 번째 해시를 이동 간격으로 사용합니다: (h1 + i*h2) % capacity. 이를 통해 각 키가 고유한 탐사 순서를 갖게 되며, 세 방법 중 분포가 가장 좋습니다.
#include <stdio.h>
int main(void) {
unsigned h1 = 3, h2 = 5, cap = 8;
for (unsigned i = 0; i < 4; i++)
printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
return 0;
}개방 주소법에서의 삭제
개방 주소법에서는 슬롯을 그냥 비울 수 없습니다. 그러면 다른 키의 탐사 연결이 끊어지기 때문입니다. 대신 삭제 표시를 남겨 조회가 해당 위치를 지나 계속 탐사하도록 합니다.
연결법과 개방 주소법 비교
장단점은 다음과 같습니다.
- 연결법: 높은 적재율을 처리하고 삭제가 간단하지만, 포인터와 메모리 할당을 사용합니다
- 개방 주소법: 캐시 친화적이고 항목별 할당이 필요 없지만, 거의 가득 차면 성능이 급격히 저하되며 삭제 표시가 필요합니다
탐사 횟수 예제
슬롯이 군집화되면 선형 탐사에 여러 단계가 필요할 수 있습니다. 여기서는 빈 슬롯을 찾는 데 필요한 탐사 횟수를 셉니다.
#include <stdio.h>
int main(void) {
int slots[8] = {1,1,1,0,0,0,0,0};
unsigned h = 0, cap = 8, probes = 0;
for (unsigned i = 0; i < cap; i++) {
probes++;
if (!slots[(h + i) % cap]) break;
}
printf("probes used = %u\n", probes);
return 0;
}빠른 확인
충돌 처리에 대한 지식을 확인해 보세요.
정리
해시 테이블이 충돌을 해결하는 방법을 살펴보았습니다.
- 연결법은 버킷마다 연결 리스트를 저장합니다
- 개방 주소법은 빈 슬롯을 탐사합니다
- 탐사 방식에는 선형 탐사, 이차 탐사, 이중 해싱이 있습니다
- 개방 주소법에서는 삭제를 위해 삭제 표시가 필요합니다
자주 묻는 질문
“충돌 처리” 강의는 무료인가요?
네 — “충돌 처리” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“충돌 처리”에서 뭘 배우나요?
체이닝과 프로빙을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“충돌 처리” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.