C Academy · 강의

크기 조정과 적재율

성능을 조정합니다

크기 조정과 적재율은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

적재율이란

적재율은 저장된 항목 수를 버킷 수로 나눈 비율입니다: alpha = size / capacity. 테이블이 얼마나 가득 찼는지를 나타내며 성능에 직접적인 영향을 줍니다.

적재율이 중요한 이유

적재율이 높아지면 버킷에 더 긴 연결 리스트가 저장되거나 탐사가 군집화되므로 연산이 느려집니다.

낮은 alpha: 빠르지만 메모리를 낭비합니다
높은 alpha: 메모리 효율은 좋지만 느립니다

연결법에서 흔히 사용하는 목표값은 0.75입니다.

적재율 계산하기

임계값과 비교할 수 있도록 부동 소수점 비율로 계산합니다.

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

크기를 조정할 시점

삽입할 때마다 적재율이 임계값을 초과하는지 확인합니다. 초과하면 테이블을 확장하고(보통 용량을 두 배로 늘림) 다시 해싱합니다.

#include <stdio.h>

int should_grow(unsigned size, unsigned cap) {
    return (double)size / cap > 0.75;
}

int main(void) {
    printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
    printf("%d\n", should_grow(10, 16)); /* 0.625  -> 0 */
    return 0;
}

재해싱 설명

각 키의 인덱스는 용량에 따라 달라지므로 버킷을 그대로 복사할 수 없습니다. 재해싱은 새 용량을 기준으로 모든 키의 버킷을 다시 계산한 뒤 키를 다시 삽입합니다.

크기 조정 함수

더 큰 새 버킷 배열을 할당하고, 기존의 모든 노드를 순회하며 새 용량을 사용해 새 배열로 옮긴 다음 배열을 교체합니다. 다음은 인덱스를 다시 계산하는 핵심 코드입니다.

#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;}

int main(void) {
    const char *key = "session";
    unsigned old_cap = 8, new_cap = 16;
    printf("old slot = %lu\n", djb2(key) % old_cap);
    printf("new slot = %lu\n", djb2(key) % new_cap);
    return 0;
}

재할당 없이 노드 이동하기

연결법에서는 새 노드를 할당하는 대신 기존 노드를 새 배열로 이동할 수 있습니다. 각 노드를 분리하고 버킷을 다시 계산한 뒤 앞에 삽입합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; 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;}

int main(void) {
    Node *old[2] = {0};
    Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
    Node *new_b[4] = {0};
    /* move node a */
    unsigned i = djb2(a->key) % 4;
    a->next = new_b[i]; new_b[i] = a;
    printf("moved to slot %u\n", i);
    return 0;
}

확장 전략

용량을 두 배로 늘리면 분할 상환 삽입 비용이 O(1)로 유지됩니다. 크기 조정 자체는 O(n)이지만 충분히 드물게 발생하므로 삽입 한 번당 평균 비용은 일정하게 유지됩니다.

용량을 2의 거듭제곱으로 설정하면 빠른 AND 마스크도 사용할 수 있습니다.

#include <stdio.h>

int main(void) {
    unsigned cap = 8;
    for (int i = 0; i < 4; i++) {
        printf("capacity = %u\n", cap);
        cap *= 2;
    }
    return 0;
}

축소

여러 번 삭제한 뒤 적재율이 지나치게 낮아지면(예: 0.1 미만) 선택적으로 테이블을 축소할 수 있습니다. 축소하면 메모리를 회수할 수 있지만 재해싱 비용이 추가되므로, 반복적인 확장과 축소를 피하도록 신중하게 수행해야 합니다.

개방 주소법과 적재율

개방 주소법 테이블은 적재율에 훨씬 더 민감합니다. alpha가 1에 가까워지면 성능이 급격히 떨어지므로, 일반적으로 연결법의 0.75보다 낮은 0.5~0.7에서 크기를 조정합니다.

분할 상환 비용 예제

적재율 0.75에서 용량을 두 배로 늘리는 삽입을 시뮬레이션하고 총 작업량을 계산하여 평균 비용이 낮게 유지되는 모습을 확인합니다.

#include <stdio.h>

int main(void) {
    unsigned cap = 4, size = 0;
    long work = 0;
    for (int i = 0; i < 100; i++) {
        size++; work++; /* the insert */
        if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
    }
    printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
    return 0;
}

빠른 확인

크기 조정에 대한 이해도를 확인해 보세요.

정리

해시 테이블의 성능을 조정하는 방법을 배웠습니다.

적재율 = 크기 / 용량
적재율이 임계값을 초과하면 크기를 조정합니다(연결법에서는 약 0.75)
인덱스가 용량에 따라 달라지므로 재해싱합니다
용량을 두 배로 늘리면 삽입의 분할 상환 비용이 O(1)이 됩니다

자주 묻는 질문

“크기 조정과 적재율” 강의는 무료인가요?

네 — “크기 조정과 적재율” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“크기 조정과 적재율”에서 뭘 배우나요?

성능을 조정합니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

C Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“크기 조정과 적재율” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← C Academy(으)로 돌아가기