해시 테이블 (Hash Table)

2026. 07. 16

들어가는 말

배열은 인덱스를 알고 있으면 원하는 위치의 원소에 O(1) 시간에 접근할 수 있다.
해시 테이블은 이 특성을 이용해 키(key)를 배열 인덱스에 대응시키고, 탐색·삽입·삭제를 평균적으로 O(1) 시간에 처리하는 자료구조다.

key는 데이터를 식별하고 찾는 데 사용하는 값이며, value는 그 key에 대응하는 값이다.
key와 value로 이루어진 한 쌍을 엔트리(Entry)라고 한다.
어떤 데이터를 key로, 어떤 데이터를 value로 사용할지는 구현 목적에 따라 달라진다.
예를 들어 학번을 key로, 학생 이름을 value로 저장할 수 있으며, 반대로 저장하는 것도 가능하다.
다만 key는 중복될 수 없으므로, 동명이인이 있을 수 있는 이름보다 학번이 key로 더 적합하다.

해시(Hash)는 음식을 잘게 다져 섞는다는 뜻의 프랑스어 hacher에서 유래한 말이다.
일상에서 만날 수 있는 해시의 예로는 해시 브라운(Hash Browns)이 있다.
해시 브라운은 감자를 잘게 다져 갈색이 나도록 구운 음식으로, 이름에 해시의 원래 뜻이 남아 있다.

컴퓨터 과학에서도 음식을 잘게 다지듯 데이터를 일정한 규칙으로 변환한다는 의미에서 해시라는 말을 사용한다.
해시 함수(Hash Function)는 임의의 길이를 가진 데이터를 고정된 길이의 값으로 변환하는 함수다.
이렇게 변환한 결과를 해시값(Hash Value)이라고 하며, 해싱(Hashing)은 해시 함수를 적용해 해시값을 만드는 과정이다.

해시 테이블은 흔히 해시 맵(Hash Map)이라고도 부른다.
Map은 key와 value의 쌍을 저장하고, key로 value를 찾을 수 있게 하는 ADT다.
해시 테이블은 해시값을 배열 인덱스에 대응시켜 key와 value의 쌍을 저장하므로 Map을 구현할 수 있다.
이렇게 해시 테이블로 구현한 Map을 해시 맵(Hash Map)이라고 한다.

해시 테이블 작동 원리

해시 테이블은 다음 순서로 key를 이용해 삽입하거나 조회한다.

key → 해시 함수 → 해시값 → 해시값 % 버킷 수 → 배열 인덱스 → key·value 삽입 또는 조회

버킷(Bucket)은 해시 테이블에서 하나의 배열 인덱스에 대응하는 저장 공간을 뜻한다.
구현이나 문맥에 따라 같은 공간을 슬롯(Slot)이라고 부르기도 한다.

배열 크기가 10이고 전화번호를 key, 이름을 value로 사용한다고 해 보자.

연산	key	해시값	`해시값 % 10`	결과
삽입	`"010-1111-1111"`	`3335458735`	`5`	`table[5]`에 `("010-1111-1111", "tom")` 삽입
조회	`"010-0000-0008"`	`2483939255`	`5`	`table[5]`의 `key`와 비교해 일치하지 않아 실패

삽입 후 table[5]에는 다음 엔트리가 들어 있다.

table[5]
+----------------------------+
| key:   "010-1111-1111"     |
| value: "tom"               |
+----------------------------+

조회할 때도 삽입할 때와 마찬가지로 먼저 key를 배열 인덱스로 변환한다.
하지만 table[5]에 있는 key는 "010-1111-1111"이고, 찾는 key는 "010-0000-0008"이므로 조회에 실패한다.

해시 테이블은 key를 먼저 일정한 범위의 정수 해시값으로 변환한 뒤, 해시값을 다시 배열 인덱스로 줄여 사용한다.
서로 다른 key가 같은 해시값을 만들 수도 있고, 서로 다른 해시값이 같은 배열 인덱스로 변환될 수도 있다.
따라서 서로 다른 key가 같은 버킷에 대응하는 충돌은 피할 수 없다.
하지만 충돌이 발생했을 때 이를 처리하는 방법은 존재한다.
이제 대표적인 충돌 처리 방법을 살펴보자.

충돌 예시

Java의 문자열 해시 함수인 String.hashCode()를 예시로 살펴보자.
이 함수는 각 문자의 코드 값을 이용해 다음 계산을 반복한다.

hash = hash × 31 + character code

해시값 충돌

서로 다른 key가 같은 해시값으로 변환되는 경우를 해시값 충돌이라고 한다.
문자열 "Aa"와 "BB"에 적용하면 서로 다른 문자열이 같은 해시값을 만드는 과정을 확인할 수 있다.

hash("Aa")
Initial: hash = 0
After reading 'A': hash = 0 × 31 + 65 = 65
After reading 'a': hash = 65 × 31 + 97 = 2112

hash("BB")
Initial: hash = 0
After reading first 'B': hash = 0 × 31 + 66 = 66
After reading second 'B': hash = 66 × 31 + 66 = 2112

"Aa"와 "BB"는 서로 다른 key지만 같은 해시값 2112로 변환된다.
key로 사용하는 문자열은 길이를 제한하지 않으면 무한히 많지만, 해시값으로 표현할 수 있는 값의 수는 유한하다.
따라서 좋은 해시 함수란 충돌을 완전히 없애는 함수가 아니라, 해시값을 고르게 분포시켜 충돌을 줄이는 함수다.

인덱스 충돌

서로 다른 해시값이 같은 배열 인덱스로 변환되는 경우를 인덱스 충돌이라고 한다.
배열 크기가 10이고 해시값을 배열 인덱스로 바꾸기 위해 % 10을 사용한다고 해 보자.

hash("A") = 65
hash("K") = 75

65 % 10 = 5
75 % 10 = 5

"A"와 "K"는 서로 다른 해시값을 만들지만, 두 해시값 모두 table[5]에 대응한다.
해시값의 범위보다 배열 인덱스의 범위가 좁으므로, 이 유형의 충돌도 피할 수 없다.

충돌 처리 방법

분리 체이닝(Separate Chaining)

분리 체이닝은 key가 충돌하면 해당 버킷의 연결 리스트에 차례로 저장하는 충돌 처리 방법이다.

table[0] → NULL
table[1] → (11, "Tom") → NULL
table[2] → NULL
table[3] → (23, "Alice") → (33, "Jack") → NULL

삽입, 조회, 삭제할 때는 key로 버킷 인덱스를 계산한 뒤, 해당 버킷의 연결 리스트에서 작업을 수행한다.

삽입할 때는 같은 key가 있으면 값을 갱신하고, 없으면 새 엔트리를 추가한다.
조회할 때는 같은 key를 찾아 value를 반환한다.
삭제할 때는 같은 key를 찾아 엔트리를 제거한다.

분리 체이닝은 충돌한 엔트리를 연결 리스트로 관리하므로 구현이 단순하다는 장점이 있다.
하지만 n개의 엔트리가 모두 충돌해 table[0]에 들어가면, 조회와 삭제를 할 때 연결 리스트의 노드를 순서대로 확인해야 하므로 성능이 O(n)까지 떨어질 수 있다.

개방 주소법(Open Addressing)

개방 주소법은 모든 key와 value를 버킷 배열에 직접 저장하는 충돌 처리 방법이다.
key가 충돌하면 정해진 조사 규칙에 따라 다른 버킷을 확인한다.
조사 규칙에는 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 이중 해싱(Double Hashing), 로빈 후드 해싱(Robin Hood Hashing)이 있다.
이 글에서는 구현이 단순하고, 충돌이 나면 다음 칸부터 차례대로 빈 칸을 찾는 선형 조사를 살펴보겠다.

삽입

삽입할 세 엔트리의 key는 각각 17, 27, 37이고, 모두 최초 버킷 인덱스가 7이라고 가정하자.

key가 17이고 value가 "Tom"인 엔트리를 삽입할 때는 table[7]이 비어 있으므로 바로 저장한다.
key가 27이고 value가 "Jack"인 엔트리를 삽입할 때는 table[7]이 사용 중이므로 다음 빈 버킷인 table[8]에 저장한다.
key가 37이고 value가 "Alice"인 엔트리를 삽입할 때는 table[7]과 table[8]이 모두 사용 중이므로 table[9]에 저장한다.

table[7] = (17, "Tom")
table[8] = (27, "Jack")
table[9] = (37, "Alice")

조회

key가 37인 엔트리를 조회할 때는 최초 버킷 인덱스인 7부터 확인한다.
충돌로 다음 버킷에 저장되었을 수 있으므로, 같은 key를 찾을 때까지 다음 버킷도 차례로 확인한다.

table[7] = (17, "Tom")    Key Mismatch
table[8] = (27, "Jack")   Key Mismatch
table[9] = (37, "Alice")  Key Match

삭제

삭제하려면 먼저 대상 엔트리를 찾아야 하므로 조회 과정이 필요하다.
삽입 중 충돌이 발생한 엔트리는 최초 버킷 인덱스가 아닌 다른 위치에 저장될 수 있다.
이 상태에서 단순히 엔트리만 삭제하면 중간에 빈 공간이 생겨 이후 조회에서 탐사 경로가 끊긴다.
따라서 삭제 후에도 탐사 경로를 유지하는 두 가지 방법을 살펴보자.

삭제 표시 남기기

Before Deletion
table[7] = (17, "Tom")   Key Mismatch
table[8] = (27, "Jack")  Key Match
table[9] = (37, "Alice")

After Deletion
table[7] = (17, "Tom")
table[8] = DELETED
table[9] = (37, "Alice")

key가 27인 엔트리를 삭제할 때, 해당 위치를 DELETED로 표시하는 방법이 있다.
이렇게 DELETED 표시를 남기면 이후 엔트리의 조사 경로를 유지할 수 있다.

삭제 후 key가 37인 엔트리를 조회해 보자.
37의 최초 버킷 인덱스는 7이므로 table[7]부터 확인한다.
키가 일치하지 않으므로 다음 버킷인 table[8]로 이동한다.
table[8]의 DELETED는 삭제된 엔트리가 있던 자리이므로, 탐색을 멈추지 않고 table[9]로 이동해 엔트리를 찾는다.

이 방식의 단점은 삭제 표시가 쌓일수록 조회 시 확인해야 할 버킷이 늘어난다는 점이다.
따라서 일정 시점에는 테이블을 다시 구성해야 한다.

뒤로 당기기

Before Deletion
table[7] = (17, "Tom")
table[8] = (27, "Jack")
table[9] = (37, "Alice")

After Deletion
table[7] = (27, "Jack")
table[8] = (37, "Alice")
table[9] = EMPTY

key가 17인 엔트리를 삭제해 보자.
17의 최초 버킷 인덱스는 7이며, 해당 엔트리는 table[7]에 있다.
table[7]을 삭제하면 빈 칸이 생기므로, table[8]의 엔트리를 table[7]로 옮긴다.
이어서 table[9]의 엔트리를 table[8]로 옮기고, table[9]를 빈 값으로 초기화하면 엔트리의 조사 경로를 유지할 수 있다.

이 예시에서는 단순하게 table[8]의 엔트리를 table[7]로 옮긴 뒤, table[9]의 엔트리를 table[8]로 옮겼다.
실제로는 각 엔트리의 최초 버킷 인덱스부터 현재 위치까지의 조사 경로에 빈 칸이 포함될 때만 엔트리를 옮길 수 있다.

예를 들어 table[7]의 엔트리를 삭제한 뒤, 검사없이 뒤따르는 엔트리를 당기는 과정을 살펴보자.

Before Deletion
table[7] = (17, "Tom")   First Bucket Index: 7
table[8] = (27, "Jack")  First Bucket Index: 7
table[9] = (19, "Mia")   First Bucket Index: 9

After Deleting table[7]
table[7] = EMPTY
table[8] = (27, "Jack")
table[9] = (19, "Mia")

After Moving table[8] to table[7]
table[7] = (27, "Jack")
table[8] = EMPTY
table[9] = (19, "Mia")

Incorrectly Moving table[9] to table[8]
table[7] = (27, "Jack")
table[8] = (19, "Mia")
table[9] = EMPTY

Lookup key 19
table[9] = EMPTY  -> Stop (Not Found)

19의 최초 버킷 인덱스는 9이므로 조회는 table[9]에서 시작한다.
하지만 검사없이 table[9]의 엔트리를 빈 table[8]로 옮겼다면 19의 조회 경로가 끊겨 해당 엔트리를 찾지 못한다.
따라서 충돌로 형성된 연속 구간이 길수록 확인하고 옮겨야 할 엔트리도 많아져 삭제에 필요한 작업이 늘어난다.

적재율(Load Factor)과 시간 복잡도

적재율은 해시 테이블에 저장된 엔트리 수를 버킷 수로 나눈 값으로, 테이블이 얼마나 꽉 차 있는지를 나타내는 지표다.
보통 그리스 문자 람다 λ로 표기한다.

λ = 저장된 엔트리 수 / 버킷 수

버킷이 10개이고 엔트리가 7개라면 적재율은 0.7이다.

적재율은 버킷 하나당 평균적으로 몇 개의 엔트리가 들어 있는지를 나타낸다.
적재율이 1보다 낮다는 것은 버킷 수가 엔트리 수보다 많다는 뜻이다.
이 경우 빈 버킷이 늘어나 할당된 메모리 일부가 낭비될 수 있다.
반대로 적재율이 1보다 높다는 것은 버킷 하나에 평균 1개 이상의 엔트리가 몰린다는 뜻이다.
이 경우 충돌 가능성이 커지고, 각 버킷의 연결 리스트가 길어져 탐색·삭제 시 더 많은 비교 연산이 필요해진다.

다만 적재율만으로는 실제 충돌 정도나 성능을 판단할 수는 없다.
적재율이 1이어도 엔트리가 버킷마다 고르게 분산된다는 보장은 없기 때문이다.
예를 들어 버킷 10개짜리 테이블에 엔트리 10개를 넣었을 때, 모두 1번 버킷에만 몰린다면 적재율은 여전히 1이지만 해당 버킷의 연결 리스트 길이는 10이 된다.
즉 적재율은 평균 지표일 뿐이고, 실제 성능은 해시 함수가 키를 얼마나 고르게 분산시키는지에 크게 좌우된다.

연산	평균	최악
탐색	`O(1)`	`O(n)`
삽입	`O(1)`	`O(n)`
삭제	`O(1)`	`O(n)`

최악의 경우는 모든 키가 같은 버킷에 몰려 연결 리스트 하나만 계속 길어지는 상황이다.

이런 최악의 경우를 줄이기 위해, 적재율이 일정 기준(threshold)을 넘으면 버킷 배열의 크기를 늘리는 리사이징(Resizing)을 수행하고 모든 엔트리의 인덱스를 다시 계산하는 재해싱(Rehashing)을 진행한다.
배열 크기 M이 바뀌면 key % M의 결과도 달라지므로, 기존 엔트리를 새 배열에 그대로 복사할 수 없다.
반드시 새 테이블의 크기를 기준으로 해시 함수를 다시 적용해 각 엔트리를 새로운 위치에 저장해야 한다.

소스 코드

문자열을 key와 value로 저장하며 충돌은 분리 체이닝 방식으로 처리한다.
연결 리스트는 해시 테이블의 핵심이 아니므로 직접 구현하지 않고 C++ 표준 라이브러리의 std::list를 사용한다.
코드는 C++로 작성하지만, 해시 테이블의 동작에 집중할 수 있도록 구조체와 함수 중심의 C 스타일로 작성했다.

#include <cstdio>
#include <cstdint>
#include <string>
#include <list>
#include <vector>

using namespace std;

const int INITIAL_BUCKET_COUNT = 4;

struct Entry
{
    string key;
    string value;
};

struct HashTable
{
    vector<list<Entry>> buckets;
};

void init_hash_table(HashTable* table, int bucket_count)
{
    table->buckets.resize(bucket_count);
}

uint32_t hash_code(const string& key)
{
    uint32_t hash = 0;

    for (size_t i = 0; i < key.length(); ++i)
    {
        hash = hash * 31 + (unsigned char)key[i];
    }

    return hash;
}

size_t get_index(const HashTable& table, const string& key)
{
    return hash_code(key) % table.buckets.size();
}

void resize(HashTable& table)
{
    size_t new_bucket_count = table.buckets.size() * 2;
    vector<list<Entry>> new_buckets(new_bucket_count);

    for (const list<Entry>& bucket : table.buckets)
    {
        for (const Entry& entry : bucket)
        {
            size_t index = hash_code(entry.key) % new_bucket_count;
            new_buckets[index].push_back(entry);
        }
    }

    table.buckets.swap(new_buckets);
}

void put(HashTable& table, const string& key, const string& value)
{
    size_t index = get_index(table, key);

    for (Entry& entry : table.buckets[index])
    {
        if (entry.key == key)
        {
            entry.value = value;
            return;
        }
    }

    table.buckets[index].push_back(Entry { key, value });
}

bool get(const HashTable& table, const string& key, string* out_value)
{
    size_t index = get_index(table, key);

    for (const Entry& entry : table.buckets[index])
    {
        if (entry.key == key)
        {
            *out_value = entry.value;
            return true;
        }
    }

    return false;
}

bool remove(HashTable& table, const string& key)
{
    size_t index = get_index(table, key);
    list<Entry>* bucket = &table.buckets[index];
    list<Entry>::iterator iterator;

    for (iterator = bucket->begin(); iterator != bucket->end(); ++iterator)
    {
        if (iterator->key == key)
        {
            bucket->erase(iterator);
            return true;
        }
    }

    return false;
}

void print_table(const HashTable& table)
{
    for (size_t i = 0; i < table.buckets.size(); ++i)
    {
        printf("[%zu] ", i);

        if (table.buckets[i].empty())
        {
            printf("(empty)");
        }
        else
        {
            for (const Entry& entry : table.buckets[i])
            {
                printf("(%s, %s) -> ", entry.key.c_str(), entry.value.c_str());
            }

            printf("NULL");
        }

        printf("\n");
    }
}

int main()
{
    HashTable table;
    init_hash_table(&table, INITIAL_BUCKET_COUNT);

    string value;
    string number1 = "010-0000-0001";
    string number2 = "010-0000-0002";
    string number3 = "010-0000-0003";
    string number4 = "010-0000-0004";
    string number5 = "010-0000-0005";
    string missing_number = "010-9999-9999";

    put(table, number1, "ann");
    put(table, number2, "brian");
    put(table, number3, "cathy");
    put(table, number4, "dan");
    put(table, number5, "eric");

    put(table, number2, "bob");
    put(table, number5, "eve");

    printf("===== TABLE STATE =====\n");
    print_table(table);

    printf("\n===== SEARCH =====\n");
    if (get(table, number2, &value))
    {
        printf("%s %s\n", number2.c_str(), value.c_str());
    }

    if (!get(table, missing_number, &value))
    {
        printf("%s not found\n", missing_number.c_str());
    }

    printf("\n===== RESIZE =====\n");
    resize(table);
    print_table(table);

    printf("\n===== REMOVE =====\n");
    remove(table, number2);
    remove(table, number3);
    print_table(table);

    return 0;
}

실행 결과

===== TABLE STATE =====
[0] (010-0000-0001, ann) -> (010-0000-0005, eve) -> NULL
[1] (010-0000-0002, bob) -> NULL
[2] (010-0000-0003, cathy) -> NULL
[3] (010-0000-0004, dan) -> NULL

===== SEARCH =====
010-0000-0002 bob
010-9999-9999 not found

===== RESIZE =====
[0] (010-0000-0001, ann) -> NULL
[1] (010-0000-0002, bob) -> NULL
[2] (010-0000-0003, cathy) -> NULL
[3] (010-0000-0004, dan) -> NULL
[4] (010-0000-0005, eve) -> NULL
[5] (empty)
[6] (empty)
[7] (empty)

===== REMOVE =====
[0] (010-0000-0001, ann) -> NULL
[1] (empty)
[2] (empty)
[3] (010-0000-0004, dan) -> NULL
[4] (010-0000-0005, eve) -> NULL
[5] (empty)
[6] (empty)
[7] (empty)