요약: C 프로그래밍 언어를 이용해 간단한 해시 테이블 자료구조를 구현하는 방법을 설명합니다. 선형 탐색과 이진 탐색을 간단히 살펴본 뒤, 해시 테이블을 설계하고 구현합니다. 이 글의 목표는 해시 테이블 내부가 무서운 것이 아니며, 일정한 제약 안에서는 처음부터 직접 만들어도 충분히 쉽다는 것을 보여주는 것입니다.

최근에 여러 언어로 단어 빈도를 세는 간단한 프로그램을 비교한 글을 썼는데, 그 과정에서 C 표준 라이브러리에는 해시 테이블 자료구조가 없다는 점이 언급됐습니다.

이 사실을 알게 되면 선택지는 여러 가지가 있습니다. 선형 탐색을 쓸 수도, 이진 탐색을 쓸 수도, 다른 사람이 만든 해시 테이블 구현을 가져다 쓸 수도, 직접 해시 테이블을 만들 수도 있습니다. 아니면 더 풍부한 기능을 갖춘 언어로 갈아탈 수도 있죠. 이 글에서는 선형 탐색과 이진 탐색을 간단히 살펴본 뒤, 직접 해시 테이블을 만드는 방법을 배워볼 것입니다. C에서는 이런 작업이 종종 필요하지만, 다른 언어를 쓰더라도 커스텀 해시 테이블이 필요한 경우에 유용할 수 있습니다.

선형 탐색

가장 간단한 방법은 선형 탐색으로 배열을 훑는 것입니다. 아이템이 몇 개 없을 때는 사실 나쁘지 않은 전략입니다. 문자열을 이용한 간단한 비교 실험에서는 약 7개까지는 해시 테이블 조회보다 더 빨랐고(프로그램 성능에 극도로 민감하지 않다면 20~30개 정도까지도 괜찮을 겁니다), 선형 탐색은 또 배열 끝에 새 아이템을 그냥 추가할 수 있다는 장점도 있습니다. 이 방식에서는 평균적으로 num_keys/2개의 아이템을 비교하게 됩니다.

다음 배열에서 키 bob을 찾는다고 해보겠습니다(각 아이템은 문자열 키와 그에 연결된 정수 값으로 이루어져 있습니다):

가장 앞(foo, 인덱스 0)부터 시작해 각 키를 차례로 비교하면 됩니다. 찾는 키와 일치하면 끝입니다. 일치하지 않으면 다음 칸으로 넘어갑니다. bob을 찾는 데는 다섯 단계가 필요합니다(인덱스 0부터 4까지).

이 알고리즘을 C로 표현하면 다음과 같습니다(배열의 각 아이템이 문자열 키와 정수 값이라고 가정합니다):

typedef struct {
    char* key;
    int value;
} item;

item* linear_search(item* items, size_t size, const char* key) {
    for (size_t i=0; i<size; i++) {
        if (strcmp(items[i].key, key) == 0) {
            return &items[i];
        }
    }
    return NULL;
}

int main(void) {
    item items[] = {
        {"foo", 10}, {"bar", 42}, {"bazz", 36}, {"buzz", 7},
        {"bob", 11}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item* found = linear_search(items, num_items, "bob");
    if (!found) {
        return 1;
    }
    printf("linear_search: value of 'bob' is %d\n", found->value);
    return 0;
}

이진 탐색

또 다른 간단한 방법은 아이템을 키 기준으로 정렬된 배열에 넣고 이진 탐색으로 비교 횟수를 줄이는 것입니다. 종이 사전을 찾는 방식과 비슷하다고 볼 수 있습니다.

C 표준 라이브러리에는 심지어 bsearch 함수도 있습니다. 이진 탐색은 수백 개 정도까지도 꽤 빠른 편입니다(해시 테이블만큼 빠르진 않지만). 평균적으로 log(num_keys)개 정도의 아이템만 비교하면 되기 때문입니다. 하지만 배열이 정렬된 상태를 유지해야 하므로, 나머지 요소들을 밀어내지 않고는 아이템을 삽입할 수 없어 삽입에는 여전히 평균 num_keys/2번의 연산이 필요합니다.

미리 정렬된 다음 배열에서 다시 bob을 찾는다고 해보겠습니다:

이진 탐색에서는 중간(buzz)에서 시작해, 그곳의 키가 찾으려는 키보다 크면 낮은 쪽 절반에서 같은 과정을 반복하고, 작으면 높은 쪽 절반에서 반복합니다. 이 경우 인덱스 3, 1, 2 순서로 세 단계 만에 찾을 수 있습니다. 선형 탐색의 다섯 단계 대신 세 단계인 셈이며, 아이템이 많을수록 선형 탐색 대비 개선 효과는 (지수적으로) 더 커집니다.

C에서는 다음과 같이 구현할 수 있습니다(bsearch를 쓰는 경우와 직접 구현하는 경우 모두). item 구조체 정의는 위와 동일합니다.

int cmp(const void* a, const void* b) {
    item* item_a = (item*)a;
    item* item_b = (item*)b;
    return strcmp(item_a->key, item_b->key);
}

item* binary_search(item* items, size_t size, const char* key) {
    if (size + size < size) {
        return NULL; // size too big; avoid overflow
    }
    size_t low = 0;
    size_t high = size;
    while (low < high) {
        size_t mid = (low + high) / 2;
        int c = strcmp(items[mid].key, key);
        if (c == 0) {
            return &items[mid];
        }
        if (c < 0) {
            low = mid + 1; // eliminate low half of array
        } else {
            high = mid;    // eliminate high half of array
        }
    }
    // Entire array has been eliminated, key not found.
    return NULL;
}

int main(void) {
    item items[] = {
        {"bar", 42}, {"bazz", 36}, {"bob", 11}, {"buzz", 7},
        {"foo", 10}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item key = {"bob", 0};
    item* found = bsearch(&key, items, num_items, sizeof(item), cmp);
    if (found == NULL) {
        return 1;
    }
    printf("bsearch: value of 'bob' is %d\n", found->value);

    found = binary_search(items, num_items, "bob");
    if (found == NULL) {
        return 1;
    }
    printf("binary_search: value of 'bob' is %d\n", found->value);
    return 0;
}

참고: binary_search에서는 애초에 “절반 크기 오버플로 검사”를 피하고 size_t의 전체 범위를 허용하는 편이 조금 더 낫습니다. 그러려면 mid 계산을 low + (high-low)/2로 바꾸면 됩니다. 다만 교육적인 목적으로 코드는 그대로 두려고 합니다. 앞부분에 오버플로 검사를 넣으면 버그는 없다고 생각하지만, size_t 범위의 절반만 허용한다는 점에서 이상적이지는 않습니다. 64비트 시스템에서 16엑사바이트짜리 배열을 탐색할 일은 당장은 없을 테니까요! 더 자세한 내용은 Nearly All Binary Searches and Mergesorts are Broken 글을 참고하세요. 피드백을 준 Seth Arnold와 Olaf Seibert에게 감사드립니다.

해시 테이블

해시 테이블은 꽤 어렵게 느껴질 수 있습니다. 종류도 많고 최적화 방법도 무수히 많기 때문입니다. 하지만 간단한 해시 함수와 이른바 “선형 탐사”를 함께 사용하면 꽤 쓸만한 해시 테이블을 아주 쉽게 만들 수 있습니다.

해시 테이블이 어떻게 동작하는지 모른다면 간단히 복습해보겠습니다. 해시 테이블은 키(대개 문자열)를 이용해 그에 대응하는 값(어떤 자료형이든 가능)을 빠르게 찾아주는 컨테이너 자료구조입니다. 내부적으로는 키의 해시 함수로 인덱싱된 배열입니다.

해시 함수는 키를 무작위처럼 보이는 숫자로 바꾸며, 같은 키에 대해서는 항상 같은 숫자를 반환해야 합니다. 예를 들어 우리가 사용할 해시 함수(64비트 FNV-1a)로 위 키들의 해시를 계산하면 다음과 같습니다:

해시 modulo 16을 함께 보여준 이유는 16개짜리 배열로 시작할 예정이라, 해시를 배열 크기에 맞게 제한해야 하기 때문입니다. modulo 연산은 16으로 나눈 나머지를 구해 배열 인덱스를 0부터 15까지로 제한합니다.

해시 테이블에 값을 넣을 때는 해시를 계산해 16으로 나눈 나머지를 배열 인덱스로 사용합니다. 따라서 크기가 16인 배열이라면 bar는 인덱스 10에, bazz는 8에, bob은 4에 넣는 식입니다. 해시 테이블 배열에 모든 아이템을 넣어보겠습니다(x는 잠시 뒤에 다룰 예정이라 제외합니다):

값을 조회할 때는 단순히 array[hash(key) % 16]을 가져오면 됩니다. 배열 크기가 2의 거듭제곱이라면 array[hash(key) & 15]를 쓸 수도 있습니다. 요소들의 순서가 더 이상 의미가 없다는 점에 주목하세요.

하지만 두 키가 (modulo 16 이후에) 같은 해시 값을 가지면 어떻게 될까요? 해시 함수와 배열 크기에 따라 이런 일은 꽤 흔합니다. 예를 들어 위 배열에 x를 추가하려고 하면, 그 해시 modulo 16은 7입니다. 하지만 인덱스 7에는 이미 foo가 있으므로 충돌이 발생합니다.

충돌을 처리하는 방법은 여러 가지가 있습니다. 전통적으로는 일정한 크기의 해시 배열을 만들고, 충돌이 발생하면 같은 인덱스로 해시된 값들을 연결 리스트로 저장했습니다. 하지만 연결 리스트는 아이템을 추가할 때 추가적인 메모리 할당을 필요로 하는 경우가 많고, 순회할 때 메모리에 흩어진 포인터를 따라가야 하므로 현대 CPU에서는 상대적으로 느립니다.

충돌을 처리하는 더 간단하고 빠른 방법은 선형 탐사입니다. 아이템을 넣으려는데 이미 다른 아이템이 있다면 그냥 다음 칸으로 이동하면 됩니다. 다음 칸도 차 있으면 다시 다음 칸으로 이동하고, 빈 칸을 찾을 때까지 반복합니다. 배열 끝에 도달하면 다시 처음으로 돌아옵니다. (다음 칸으로 이동하는 것 말고도 다른 탐사 방식이 있지만, 이 글의 범위를 벗어납니다.) 이 기법은 연결 리스트보다 훨씬 빠릅니다. CPU 캐시가 다음 아이템들을 이미 가져왔을 가능성이 높기 때문입니다.

충돌을 일으키는 x(값 200)를 추가한 뒤 해시 테이블 배열의 모습은 다음과 같습니다. 먼저 인덱스 7을 시도하지만 거기에는 foo가 있고, 인덱스 8로 이동하지만 거기에는 bazz가 있으므로, 다시 인덱스 9로 이동합니다. 거기는 비어 있으므로 거기에 넣습니다:

해시 테이블이 너무 꽉 차면 더 큰 배열을 할당하고 아이템들을 옮겨야 합니다. 해시 테이블의 아이템 수가 배열 크기에 도달하면 반드시 해야 하는 작업이지만, 보통은 테이블이 절반 또는 4분의 3 정도 찼을 때 미리 하는 것이 좋습니다. 충분히 일찍 크기를 늘리지 않으면 충돌이 점점 더 잦아지고 조회와 삽입이 점점 느려집니다. 거의 꽉 찰 때까지 기다리면 사실상 다시 선형 탐색으로 돌아간 것이나 다름없습니다.

좋은 해시 함수를 사용하면, 이런 종류의 해시 테이블은 조회당 평균 한 번 정도의 연산에 키를 해시하는 시간만 더하면 됩니다(키가 대개 비교적 짧은 문자열인 경우가 많습니다).

이게 전부입니다! 여기서 더 할 수 있는 일은 훨씬 많고, 이 글은 그저 표면을 살짝 긁은 수준입니다. big O 표기법이나 최적의 배열 크기, 다양한 탐사 방식 등에 대한 학술적인 분석까지는 다루지 않겠습니다. 그런 수준의 자세한 내용이 궁금하다면 Donald Knuth의 TAOCP를 읽어보세요!

해시 테이블 구현

이 구현의 코드는 GitHub의 benhoyt/ht 저장소에서 ht.h와 ht.c 파일로 확인할 수 있습니다. 참고로 모든 코드는 관대한 MIT 라이선스로 공개되어 있습니다.

Code Review Stack Exchange에서 좋은 피드백을 받아 몇 가지 날카로운 부분을 다듬을 수 있었습니다. 그중 하나는 ht_expand 단계에서 strdup을 호출하는 방식 때문에 발생한 메모리 누수였습니다(여기서 수정됐습니다). Valgrind를 이용해 누수를 확인했는데, 진작 실행해봤어야 했습니다. Seth Arnold도 이 글의 초안에 유용한 피드백을 주었습니다. 모두에게 감사드립니다!

API 설계

먼저 어떤 API가 필요한지 생각해보겠습니다. 해시 테이블을 생성하고 파괴하는 방법, 주어진 키에 대한 값을 가져오는 방법, 주어진 키에 값을 설정하는 방법, 아이템 개수를 가져오는 방법, 그리고 아이템들을 순회하는 방법이 필요합니다. 최대 효율을 노린 API가 아니라, 비교적 간단하게 구현할 수 있는 API를 목표로 합니다.

몇 차례 고민 끝에 다음과 같은 함수와 구조체로 정했습니다(ht.h 참고):

// Hash table structure: create with ht_create, free with ht_destroy.
typedef struct ht ht;

// Create hash table and return pointer to it, or NULL if out of memory.
ht* ht_create(void);

// Free memory allocated for hash table, including allocated keys.
void ht_destroy(ht* table);

// Get item with given key (NUL-terminated) from hash table. Return
// value (which was set with ht_set), or NULL if key not found.
void* ht_get(ht* table, const char* key);

// Set item with given key (NUL-terminated) to value (which must not
// be NULL). If not already present in table, key is copied to newly
// allocated memory (keys are freed automatically when ht_destroy is
// called). Return address of copied key, or NULL if out of memory.
const char* ht_set(ht* table, const char* key, void* value);

// Return number of items in hash table.
size_t ht_length(ht* table);

// Hash table iterator: create with ht_iterator, iterate with ht_next.
typedef struct {
    const char* key;  // current key
    void* value;      // current value

    // Don't use these fields directly.
    ht* _table;       // reference to hash table being iterated
    size_t _index;    // current index into ht._entries
} hti;

// Return new hash table iterator (for use with ht_next).
hti ht_iterator(ht* table);

// Move iterator to next item in hash table, update iterator's key
// and value to current item, and return true. If there are no more
// items, return false. Don't call ht_set during iteration.
bool ht_next(hti* it);

이 API 설계에 대해 몇 가지 덧붙이자면:

• 단순함을 위해 C 스타일의 NUL 종료 문자열을 사용합니다. 문자열을 처리하는 더 효율적인 방법도 있지만, 이는 C 표준 라이브러리와 잘 어울립니다.
• ht_set 함수는 키를 (처음 삽입하는 경우) 할당하고 복사합니다. 보통 호출자가 이런 부분을 신경 쓰거나 키 메모리가 계속 유지되도록 보장해야 하는 상황을 원하지 않습니다. ht_set은 복제된 키에 대한 포인터를 반환하는데, 이는 주로 “메모리 부족” 오류 신호로 쓰입니다. 실패 시 NULL을 반환합니다.
• 다만 ht_set은 값을 복사하지 않습니다. 값 포인터가 해시 테이블이 살아 있는 동안 유효하도록 보장하는 것은 호출자의 책임입니다.
• 값은 NULL일 수 없습니다. 덕분에 ht_get의 시그니처가 조금 더 단순해집니다. NULL 값과 아예 설정되지 않은 값을 구분할 필요가 없기 때문입니다.
• ht_length 함수는 엄밀히 말해 필수는 아닙니다. 테이블을 순회하면 길이를 알 수 있기 때문입니다. 하지만 그건 좀 번거롭고(느리기도 하고) ht_length가 있으면 유용합니다.
• 반복(iteration)을 구현하는 방법은 여러 가지가 있을 수 있습니다. 명시적인 이터레이터 타입과 while 루프를 쓰는 방식이 C에서는 간단하고 자연스러워 보입니다(아래 예제 참고). ht_iterator가 반환하는 값은 포인터가 아니라 값 자체인데, 효율성 때문이기도 하고 호출자가 따로 해제할 것이 없도록 하기 위해서입니다.
• 해시 테이블에서 아이템을 제거하는 ht_remove는 제공하지 않습니다. 선형 탐사에서는 제거가 (남게 되는 “구멍” 때문에) 조금 더 까다로운 부분인데, 해시 테이블을 쓸 때 아이템을 제거해야 하는 경우가 그리 많지 않아 빠진 부분을 독자를 위한 연습 문제로 남겨두었습니다.

데모 프로그램

다음은 API의 모든 함수를 사용하는 간단한 프로그램(demo.c)입니다. 표준 입력에서 공백으로 구분된 단어들의 빈도를 세고 결과를 출력합니다(순회 순서가 정의되어 있지 않으므로 임의의 순서로 출력됩니다). 마지막에는 고유 단어의 총 개수를 출력합니다.

// Example:
// $ echo 'foo bar the bar bar bar the' | ./demo
// foo 1
// bar 4
// the 2
// 3

void exit_nomem(void) {
    fprintf(stderr, "out of memory\n");
    exit(1);
}

int main(void) {
    ht* counts = ht_create();
    if (counts == NULL) {
        exit_nomem();
    }

    // Read next word from stdin (at most 100 chars long).
    char word[101];
    while (scanf("%100s", word) != EOF) {
        // Look up word.
        void* value = ht_get(counts, word);
        if (value != NULL) {
            // Already exists, increment int that value points to.
            int* pcount = (int*)value;
            (*pcount)++;
            continue;
        }

        // Word not found, allocate space for new int and set to 1.
        int* pcount = malloc(sizeof(int));
        if (pcount == NULL) {
            exit_nomem();
        }
        *pcount = 1;
        if (ht_set(counts, word, pcount) == NULL) {
            exit_nomem();
        }
    }

    // Print out words and frequencies, freeing values as we go.
    hti it = ht_iterator(counts);
    while (ht_next(&it)) {
        printf("%s %d\n", it.key, *(int*)it.value);
        free(it.value);
    }

    // Show the number of unique words.
    printf("%d\n", (int)ht_length(counts));

    ht_destroy(counts);
    return 0;
}

이제 해시 테이블 구현(ht.c)으로 넘어가 보겠습니다.

생성과 파괴

새 해시 테이블을 할당하는 과정은 꽤 간단합니다. 초기 배열 용량(capacity)은 16으로 시작하며, 이는 확장하기 전까지 최대 8개의 아이템을 담을 수 있다는 뜻입니다. 할당은 두 번 이루어집니다. 하나는 해시 테이블 구조체 자체를 위한 것이고, 다른 하나는 entries 배열을 위한 것입니다. entries 배열에는 calloc을 사용해 시작 시 모든 키가 NULL이 되도록, 즉 모든 슬롯이 비어 있도록 합니다.

ht_destroy 함수는 이 메모리를 해제할 뿐 아니라, 중간에 할당된 복제된 키들의 메모리도 함께 해제합니다(자세한 내용은 아래에서 다룹니다).

// Hash table entry (slot may be filled or empty).
typedef struct {
    const char* key;  // key is NULL if this slot is empty
    void* value;
} ht_entry;

// Hash table structure: create with ht_create, free with ht_destroy.
struct ht {
    ht_entry* entries;  // hash slots
    size_t capacity;    // size of _entries array
    size_t length;      // number of items in hash table
};

#define INITIAL_CAPACITY 16  // must not be zero

ht* ht_create(void) {
    // Allocate space for hash table struct.
    ht* table = malloc(sizeof(ht));
    if (table == NULL) {
        return NULL;
    }
    table->length = 0;
    table->capacity = INITIAL_CAPACITY;

    // Allocate (zero'd) space for entry buckets.
    table->entries = calloc(table->capacity, sizeof(ht_entry));
    if (table->entries == NULL) {
        free(table); // error, free table before we return!
        return NULL;
    }
    return table;
}

void ht_destroy(ht* table) {
    // First free allocated keys.
    for (size_t i = 0; i < table->capacity; i++) {
        free((void*)table->entries[i].key);
    }

    // Then free entries array and table itself.
    free(table->entries);
    free(table);
}

해시 함수

다음으로 해시 함수를 정의하는데, FNV-1a 해시 알고리즘을 C로 직관적으로 구현한 것입니다. FNV는 무작위화되거나 암호학적인 해시 함수가 아니므로, 공격자가 충돌을 많이 일으키는 키를 만들어 조회를 크게 느리게 만들 수 있습니다. Python이 이런 이유로 FNV에서 다른 방식으로 바꾼 것도 그 때문입니다. 하지만 우리의 용도에서는 FNV가 간단하고 빠릅니다.

알고리즘 자체로 보면, FNV-1a는 “오프셋” 상수로 해시를 시작하고, 문자열의 각 바이트마다 해시와 바이트를 XOR한 뒤 큰 소수로 곱합니다. 오프셋과 소수는 박사 학위를 가진 사람들이 신중하게 선택한 값입니다.

우리는 64비트 변형을 사용합니다. 뭐, 요즘은 대부분 컴퓨터가 64비트이니 좋은 생각 같아서입니다. 제가 그런 박사 학위가 없다는 걸 알 수 있을 겁니다. :-) 농담이고, 해시 테이블이 아주 커지는 경우를 대비해 32비트 버전보다 낫다고 판단했습니다.

#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

// Return 64-bit FNV-1a hash for key (NUL-terminated). See description:
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
static uint64_t hash_key(const char* key) {
    uint64_t hash = FNV_OFFSET;
    for (const char* p = key; *p; p++) {
        hash ^= (uint64_t)(unsigned char)(*p);
        hash *= FNV_PRIME;
    }
    return hash;
}

여기서 자세한 분석까지 하지는 않겠지만, 입력의 고유 단어들로 만든 해시 테이블의 평균 탐사 길이를 출력하는 간단한 통계 프로그램을 포함해 두었습니다. 우리가 사용하는 FNV-1a 해시 알고리즘은 50만 개 영어 단어 목록에서 평균 탐사 길이 1.40으로 잘 동작했고, word1, word2처럼 서로 매우 유사한 키 50만 개로 이루어진 목록에서도 평균 탐사 길이 1.38로 잘 동작했습니다.

흥미롭게도 FNV-1 알고리즘(FNV-1a와 비슷하지만 곱셈을 XOR보다 먼저 수행합니다)으로 시도했을 때는 영어 단어에서는 여전히 평균 탐사 길이가 1.43이었지만, 유사한 키들에서는 성능이 매우 나빠 평균 탐사 길이가 5.02였습니다. 따라서 간단한 테스트에서는 FNV-1a가 확실한 승자였습니다.

조회

이제 ht_get 함수를 살펴보겠습니다. 먼저 해시를 계산하고 capacity(entries 배열의 크기)로 나눈 나머지를 구하는데, 이는 capacity - 1과 AND 연산으로 수행합니다. AND를 쓸 수 있는 이유는 아래에서 보게 되겠지만, 단순함을 위해 배열 크기를 항상 2의 거듭제곱으로 유지하고 있기 때문입니다.

그런 다음 빈 슬롯을 찾을 때까지 반복합니다. 빈 슬롯을 만났다는 것은 키를 찾지 못했다는 뜻입니다. 비어 있지 않은 각 슬롯에서는 strcmp로 해당 슬롯의 키가 우리가 찾는 키인지 확인합니다(충돌이 없었다면 첫 번째 슬롯에서 바로 찾을 수 있습니다). 아니라면 한 칸씩 이동합니다.

void* ht_get(ht* table, const char* key) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(table->capacity - 1));

    // Loop till we find an empty entry.
    while (table->entries[index].key != NULL) {
        if (strcmp(key, table->entries[index].key) == 0) {
            // Found key, return value.
            return table->entries[index].value;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }
    return NULL;
}

삽입

ht_set 함수는 요소가 너무 많아지면 테이블을 확장해야 하므로 조금 더 복잡합니다. 우리 구현에서는 테이블이 절반 정도 차면 용량을 두 배로 늘립니다. 메모리는 조금 낭비되지만, 구현을 매우 단순하게 유지할 수 있습니다.

먼저 ht_set 함수입니다. 필요하면 테이블을 확장한 뒤 아이템을 삽입합니다:

const char* ht_set(ht* table, const char* key, void* value) {
    assert(value != NULL);
    if (value == NULL) {
        return NULL;
    }

    // If length will exceed half of current capacity, expand it.
    if (table->length >= table->capacity / 2) {
        if (!ht_expand(table)) {
            return NULL;
        }
    }

    // Set entry and update length.
    return ht_set_entry(table->entries, table->capacity, key, value,
                        &table->length);
}

작업의 핵심은 ht_set_entry 헬퍼 함수에 있습니다(루프가 ht_get의 루프와 매우 유사하다는 점에 주목하세요). plength 인수가 NULL이 아니면 ht_set에서 호출된 것이므로 키를 할당해 복사하고 길이를 갱신합니다:

// Internal function to set an entry (without expanding table).
static const char* ht_set_entry(ht_entry* entries, size_t capacity,
        const char* key, void* value, size_t* plength) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(capacity - 1));

    // Loop till we find an empty entry.
    while (entries[index].key != NULL) {
        if (strcmp(key, entries[index].key) == 0) {
            // Found key (it already exists), update value.
            entries[index].value = value;
            return entries[index].key;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }

    // Didn't find key, allocate+copy if needed, then insert it.
    if (plength != NULL) {
        key = strdup(key);
        if (key == NULL) {
            return NULL;
        }
        (*plength)++;
    }
    entries[index].key = (char*)key;
    entries[index].value = value;
    return key;
}

ht_expand 헬퍼 함수는 어떨까요? 현재 용량의 두 배 크기의 새 entries 배열을 할당하고, plength를 NULL로 하여 ht_set_entry를 이용해 기존 항목들을 복사합니다. 해시 값 자체는 같더라도 capacity가 달라졌기 때문에(인덱스는 해시 modulo capacity입니다) 인덱스는 달라집니다.

// Expand hash table to twice its current size. Return true on success,
// false if out of memory.
static bool ht_expand(ht* table) {
    // Allocate new entries array.
    size_t new_capacity = table->capacity * 2;
    if (new_capacity < table->capacity) {
        return false;  // overflow (capacity would be too big)
    }
    ht_entry* new_entries = calloc(new_capacity, sizeof(ht_entry));
    if (new_entries == NULL) {
        return false;
    }

    // Iterate entries, move all non-empty ones to new table's entries.
    for (size_t i = 0; i < table->capacity; i++) {
        ht_entry entry = table->entries[i];
        if (entry.key != NULL) {
            ht_set_entry(new_entries, new_capacity, entry.key,
                         entry.value, NULL);
        }
    }

    // Free old entries array and update this table's details.
    free(table->entries);
    table->entries = new_entries;
    table->capacity = new_capacity;
    return true;
}

길이와 순회

ht_length 함수는 아주 간단합니다. 진행하면서 _length에 아이템 개수를 계속 갱신하므로, 그냥 그 값을 반환하면 됩니다:

size_t ht_length(ht* table) {
    return table->length;
}

순회가 마지막 부분입니다. 이터레이터를 만들려면 사용자가 ht_iterator를 호출하고, 다음 아이템으로 이동하려면 ht_next가 true를 반환하는 동안 루프에서 호출하면 됩니다. 정의는 다음과 같습니다:

hti ht_iterator(ht* table) {
    hti it;
    it._table = table;
    it._index = 0;
    return it;
}

bool ht_next(hti* it) {
    // Loop till we've hit end of entries array.
    ht* table = it->_table;
    while (it->_index < table->capacity) {
        size_t i = it->_index;
        it->_index++;
        if (table->entries[i].key != NULL) {
            // Found next non-empty item, update iterator key and value.
            ht_entry entry = table->entries[i];
            it->key = entry.key;
            it->value = entry.value;
            return true;
        }
    }
    return false;
}

논의

이게 전부입니다. ht.c의 구현은 빈 줄과 주석을 포함해도 약 200줄에 불과합니다.

주의할 점은, 이것은 라이브러리가 아니라 학습용 도구라는 것입니다. 직접 가지고 놀아보고, 제가 찾지 못한 버그가 있으면 알려주세요! 충분한 추가 테스트와 엣지 케이스 점검 없이 그대로 사용하는 것은 권하지 않습니다. 우리가 다루는 건 안전하지 않은(unsafe) C라는 점을 기억하세요. 이 글을 쓰는 중에도 entries 배열을 할당할 때 calloc 대신 malloc을 썼다는 걸 깨달았는데, 그러면 키가 NULL로 초기화되지 않을 수 있습니다.

앞서 말했듯이 구현을 단순하게 유지하고 싶었고, 성능에 대해 크게 걱정하지 않았습니다. 하지만 Go의 map 구현과 간단하고 비과학적인 성능 비교를 해보니 꽤 괜찮은 결과를 보였습니다. 50만 개 영어 단어 기준으로 이 C 버전은 조회에서는 약 50% 느리지만 삽입에서는 40% 더 빨랐습니다.

Go 얘기가 나와서 말인데, Go 같은 언어에서는 커스텀 해시 테이블을 작성하는 것이 훨씬 더 쉽습니다. 메모리 할당 오류를 처리하거나 할당한 메모리를 해제하는 걱정을 할 필요가 없기 때문입니다. 최근에 Go로 비슷한 종류의 해시 테이블을 구현한 counter 패키지를 작성한 적이 있습니다.

C 버전에 대해 더 할 수 있는 일은 분명히 많습니다. 다양한 테스트를 통해 안전성과 신뢰성에 집중할 수도 있습니다. 성능에 집중해 메모리 할당을 줄이거나, 복제된 키를 위해 “범프 할당자(bump allocator)”를 사용하거나, 짧은 키를 각 아이템 구조체 안에 직접 저장하는 등의 최적화를 할 수도 있습니다. 메모리 사용량을 개선하고 _ht_expand가 매번 크기를 두 배로 늘리지 않도록 조정할 수도 있습니다. 혹은 아이템 제거 같은 기능을 추가할 수도 있습니다.

이 글을 다 쓰고 나서야 Bob Nystrom의 훌륭한 책 Crafting Interpreters에 해시 테이블을 다루는 장이 있다는 걸 떠올렸습니다. 그 장에서도 비슷한 설계 선택을 하고 있지만, 이 글보다 훨씬 더 깊이 있게 다룹니다. 시작 전에 그 장을 기억했더라면 아마 이 글을 쓰지 않았을지도 모릅니다!

어쨌든 이 글이 유용하거나 흥미로웠길 바랍니다. 버그를 발견하거나 피드백이 있으면 알려주세요. Hacker News, 프로그래밍 Reddit, Lobsters에서의 토론에도 참여할 수 있습니다.