삽입, 조회, 삭제
핵심 연산을 알아봅니다
삽입, 조회, 삭제은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
세 가지 핵심 연산
모든 해시 테이블은 삽입, 조회, 삭제라는 세 가지 연산을 지원합니다. 좋은 해시 함수와 적절한 적재율을 사용하면 세 연산 모두 평균 O(1) 시간에 실행됩니다.
이제 연결법을 기반으로 한 테이블을 단계별로 구현하겠습니다.
테이블과 노드 형식
복사된 키 문자열과 정수 값을 보유하는 노드를 정의하고, 버킷 배열과 용량을 보유하는 테이블 구조체도 정의합니다.
#include <stdio.h>
typedef struct Node {
char *key;
int value;
struct Node *next;
} Node;
typedef struct {
Node **buckets;
unsigned capacity;
unsigned size;
} HashTable;
int main(void) {
printf("types defined\n");
return 0;
}테이블 생성하기
calloc으로 테이블과 0으로 초기화된 버킷 배열을 할당하므로, 모든 버킷은 처음에 NULL로 시작합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;
HashTable *ht_create(unsigned cap) {
HashTable *t = malloc(sizeof *t);
t->buckets = calloc(cap, sizeof(Node *));
t->capacity = cap; t->size = 0;
return t;
}
int main(void) {
HashTable *t = ht_create(16);
printf("capacity=%u size=%u\n", t->capacity, t->size);
return 0;
}해시 보조 함수
DJB2를 재사용하고 해시값을 버킷 인덱스로 축소합니다. 이 보조 함수는 세 가지 연산 모두에서 사용됩니다.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381; int c;
while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
return h;
}
unsigned bucket_of(const char *key, unsigned cap) {
return (unsigned)(djb2(key) % cap);
}
int main(void) {
printf("%u\n", bucket_of("name", 16));
return 0;
}삽입: 갱신 또는 앞에 삽입
삽입할 때는 먼저 버킷을 검색합니다. 키가 이미 있으면 값을 갱신합니다. 그렇지 않으면 새 노드를 할당하고(strdup으로 키를 복사하여) 리스트의 앞에 삽입합니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
Node *insert(Node *head, const char *key, int val) {
for (Node *p = head; p; p = p->next)
if (strcmp(p->key, key) == 0) { p->value = val; return head; }
Node *n = malloc(sizeof *n);
n->key = strdup(key); n->value = val; n->next = head;
return n;
}
int main(void) {
Node *b = NULL;
b = insert(b, "a", 1);
b = insert(b, "a", 99); /* update */
printf("%s=%d\n", b->key, b->value);
return 0;
}조회
조회는 키를 해싱한 다음 버킷 리스트를 순회하며 strcmp로 키를 비교합니다. 값에 대한 포인터를 반환하고, 키가 없으면 NULL을 반환합니다.
#include <stdio.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
int *lookup(Node *head, const char *key) {
for (Node *p = head; p; p = p->next)
if (strcmp(p->key, key) == 0) return &p->value;
return NULL;
}
int main(void) {
Node n2 = {"y", 20, NULL};
Node n1 = {"x", 10, &n2};
int *v = lookup(&n1, "y");
printf("%d\n", v ? *v : -1);
return 0;
}삭제: 리스트 다시 연결하기
삭제는 이전 노드에 대한 포인터를 유지하면서 버킷을 순회한 뒤, 대상 노드를 건너뛰도록 리스트를 다시 연결하고 대상 노드를 해제합니다(복사된 키와 노드 모두 해제).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
Node *delete_key(Node *head, const char *key) {
Node *prev = NULL, *cur = head;
while (cur) {
if (strcmp(cur->key, key) == 0) {
if (prev) prev->next = cur->next; else head = cur->next;
free(cur->key); free(cur);
return head;
}
prev = cur; cur = cur->next;
}
return head;
}
int main(void) {
Node *b = malloc(sizeof *b);
b->key = strdup("a"); b->value = 1; b->next = NULL;
b = delete_key(b, "a");
printf("%s\n", b ? "left" : "empty");
return 0;
}하나로 합치기
완성된 테이블은 버킷을 계산한 뒤 리스트 보조 함수에 작업을 위임하는 방식으로 이 기능들을 감쌉니다. 여기서는 작동하는 완전한 소형 테이블을 살펴봅니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
#define CAP 16
Node *table[CAP];
void put(const char *k, int v) {
unsigned i = djb2(k) % CAP;
Node *n = malloc(sizeof *n);
n->key = strdup(k); n->value = v; n->next = table[i];
table[i] = n;
}
int get(const char *k) {
for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
if (!strcmp(p->key, k)) return p->value;
return -1;
}
int main(void) {
put("age", 30); put("score", 95);
printf("age=%d score=%d\n", get("age"), get("score"));
return 0;
}키를 복사하는 이유
strdup으로 키를 저장하면 테이블이 자체 복사본을 소유하게 됩니다. 호출자의 포인터를 저장하면 호출자가 사용하는 동안 키가 변경되거나 해제되어 조회가 손상될 수 있습니다.
따라서 삭제할 때 복사된 키도 free해야 합니다.
시간 복잡도
해시값이 균일하게 분포하고 적재율을 0.75 근처로 유지하면 다음과 같습니다.
- 삽입: 평균 O(1)
- 조회: 평균 O(1)
- 삭제: 평균 O(1)
모든 키가 하나의 버킷에서 충돌하는 최악의 경우에는 O(n)입니다.
전체 테이블 해제하기
메모리 누수를 방지하려면 모든 버킷의 모든 노드를 해제한 다음 버킷 배열을 해제하고, 마지막으로 테이블 구조체를 해제합니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
void free_bucket(Node *head) {
while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}
int main(void) {
Node *b = malloc(sizeof *b);
b->key = strdup("k"); b->value = 1; b->next = NULL;
free_bucket(b);
printf("freed\n");
return 0;
}빠른 확인
핵심 연산에 대한 이해도를 확인해 보세요.
정리
연결법을 사용해 해시 테이블의 세 가지 핵심 연산을 구현했습니다.
- 삽입은 노드를 갱신하거나 앞에 삽입합니다
- 조회는
strcmp로 버킷 리스트를 순회합니다 - 삭제는 리스트를 다시 연결하고 키와 노드를 모두 해제합니다
strdup으로 키를 소유하고 종료할 때 모든 메모리를 해제합니다
자주 묻는 질문
“삽입, 조회, 삭제” 강의는 무료인가요?
네 — “삽입, 조회, 삭제” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“삽입, 조회, 삭제”에서 뭘 배우나요?
핵심 연산을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“삽입, 조회, 삭제” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 해시 함수
- 충돌 처리
- 삽입, 조회, 삭제
- 크기 조정과 적재율