샷건치며 배우는 자료구조 with C++, 9화

데이터를 효율적으로 저장하고 관리하기 위한 자료구조, 해시 테이블에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

C 언어 구현 내용 제거
- 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

해시 테이블

해시 테이블에 대해 알아보기 전에 연관 배열에 대해 알아봅시다.

연관 배열^{Associative Array}은 키^Key와 값^Value의 쌍을 저장하고, 키를 사용해 값을 빠르게 찾아내는 자료구조입니다. 이는 일상생활 속 사용하는 사전과 비슷하다고 볼 수 있습니다. 예를 들어, 사전에서 단어(키)를 찾으면 해당 단어의 정의(값)를 바로 확인할 수 있죠. 이처럼 키를 사용해 값을 빠르게 찾는 것이 이 연관 배열의 핵심입니다.

자, 오늘 우리가 배울 해시 테이블은 이 연관 배열을 구현하는 방법 중 하나입니다. 해시 테이블^{Hash Table}은 키를 해시 함수^{Hash Function}에 넣어 해시 값을 계산하고, 이 값을 인덱스로 사용하여 데이터를 저장하거나 조회할 수 있습니다.

일반적인 배열이나 리스트처럼 데이터를 순차적으로 탐색하지 않고, 해시 함수를 통해 얻은 인덱스를 사용하여 직접 접근하기 때문에 데이터의 검색 속도가 매우 빠릅니다. 평균적으로 \(O(1)\)의 시간 복잡도로 데이터를 저장 및 검색할 수 있습니다.

기본 구조

키배열해시 함수버킷

키^Key는 해시 테이블에서 데이터를 식별하고 접근하기 위한 고유한 식별자입니다. 키를 통해 값을 저장하거나 빠르게 탐색할 수 있죠. 쉽게 말해, 키는 해시 테이블에서 값을 꺼내기 위한 '열쇠'와 같은 역할을 합니다.

사용자가 데이터를 추가, 제거, 탐색할 때마다 키를 입력 값으로 사용하며, 이 키는 해시 함수에 의해 배열의 인덱스로 변환됩니다.

키는 정수, 문자열, 사용자 정의 타입 등 다양한 데이터 타입으로 표현할 수 있어 유연성을 제공합니다. 예를 들어, 전화번호부에서 이름(키)으로 전화번호(값)를 찾거나, 학생 관리 시스템에서 학번(키)으로 이름(값)을 찾는 것처럼 말이죠.

고유성

이상적인 해시 테이블에선 키가 중복되지 않아야합니다. 같은 키가 여러 값을 가리키면 어떤 값을 반환해야 할 지 모호해집니다. 예를 들어, "director"라는 키에 "신창섭"과 "강원기"의 값이 있다면 무엇을 반환해야 할 지 애매합니다.

대부분의 해시 테이블은 같은 키로 새 값을 추가하면 기존의 값을 덮어씁니다. 키의 중복을 허용하는 multimap이 있지만, 표준 해시 테이블의 변형이기 때문에 본문에서는 다루지 않습니다.
다양성

키는 정수, 문자열, 사용자 정의 타입 등 다양한 데이터 타입으로 표현될 수 있습니다. 해시 테이블의 활용 범위가 무궁무진해지는 순간이죠.

도서관에서 책의 관리 번호가 단순 숫자(1234)일 수 있고, 주제 코드(K-1234)일 수 있듯이 키도 상황에 따라 다양한 데이터 타입을 사용할 수 있습니다.
해시 가능성

키는 해시 함수로 처리할 수 있어야 합니다. 즉, 키를 숫자 형태의 해시 값으로 변환할 수 있어야합니다.

해시 테이블은 고정된 크기를 갖는 배열을 기반으로 합니다. 이 배열은 모든 키-값 쌍을 저장하는 역할을 하고 해시 테이블의 빠른 속도를 가능하게 하는 기본 뼈대입니다.

고정 크기

해시 테이블 설계 시 배열은 미리 정해진 크기를 갖습니다. 다만, 크기가 작으면 충돌이 잦아지고... 너무 크면 메모리 낭비가 될 수 있습니다. 보통은 동적 할당 후 크기 조정 방식으로 합니다.
랜덤 액세스

배열은 인덱스를 통한 직접 접근이 가능합니다. 해시 테이블의 장점인 \(O(1)\) 시간 복잡도를 나타내는 큰 이유죠.

해시 함수^{Hash Function}는 키를 배열의 인덱스로 변환하는 핵심 함수입니다. 키를 입력 값으로 받아 배열 내 유효한 인덱스로 변환하죠. 이 함수 덕분에 해시 테이블은 순차 탐색없이 빠르게 데이터 접근이 가능해집니다. 해시 함수를 얼마나 잘 설계하느냐에 따라 해시 테이블의 성능을 좌우한다고 볼 수 있습니다.

결정성

해시 함수는 같은 키에 대해 같은 해시 값을 반환해야 합니다. "sibal"을 6974로 변환했다면, 다음에도 6974로 변환이 되어야 합니다.
효율성

해시 함수는 빠르게 연산이 되어야 합니다. 복잡하고 오래 걸리는 연산은 해시 테이블의 장점 중 하나인 시간 복잡도 \(O(1)\)가 무색해집니다.
균등 분포

해시 함수는 키를 배열의 모든 버킷에 균등하게 분포시켜야 합니다. 특정 버킷에 데이터에 몰리면 충돌이 발생합니다.

서로 다른 키가 같은 인덱스를 가리키는 충돌을 줄이는 것이 이상적이지만 완벽히 피할 수는 없습니다. 이를 최소화하는 것이 목표입니다.

두 사람의 사물함 번호가 겹치면 같은 사물함을 쓰려고 하듯이 충돌은 어쩔 수 없습니다.

버킷^Bucket은 해시 테이블에서 데이터를 저장하는 기본 단위 공간입니다. 해시 함수가 키를 입력 받아 반환한 인덱스는 바로 이 버킷의 위치를 의미합니다. 그리고 실제 데이터는 해당 버킷에 저장되죠.

저장 공간

해시 테이블의 배열에서 각 칸을 버킷이라 합니다. 이 버킷은 하나의 키-값 쌍을 저장하거나, 충돌 처리를 수행하기 위해 여러 개의 쌍을 저장하기도 합니다.
충돌 처리

하나의 버킷에 여러 키가 같은 인덱스를 가리킬 수 있습니다. 이를 해시 충돌^{Hash Collision}이라합니다. 보통 아래의 방식으로 해결합니다.
- 체이닝(Chaining): 버킷을 연결 리스트나 동적 배열 등으로 구성하여 여러 키-값 쌍을 하나의 버킷에 저장
- 오픈 어드레싱(Open Addressing): 충돌 발생 시 빈 버킷을 찾아 순차적으로 저장

해시 함수

기본 구조에서 설명했지만, 해시 함수는 키를 입력 받아 해시 값^{Hash Value}을 반환합니다. 즉 배열의 인덱스를 반환하며, 이 덕분에 해시 테이블은 순차 탐색 없이 빠르게 데이터에 접근할 수 있습니다.

정수문자열std::hasher

hashfunc_int.c
unsigned int hash(int key) {
    return key % TABLE_SIZE;
}

정수를 키로 사용할 경우 해시 함수는 간단하면서 매우 빠르게 작동합니다. 다만, 충돌을 방지하고 고르게 분포시키기 위해 TABLE_SIZE의 값은 소수^{Prime Number}로 설정하는 편입니다.

소수를 사용하는 이유

해시 함수의 목표 중 하나는 키를 가능한 균등하게 분포시키는 것입니다. 소수를 사용하면 충돌을 줄이고, 데이터가 특정 위치에 몰리는 현상을 방지할 수 있죠.

불균등한 분포공약수 최소화

키가 일정한 패턴을 갖고 있을 경우, 테이블 크기가 그 패턴과 공약수를 가지면 해시 값이 몰릴 수 있습니다.

예를 들어, 테이블(1)의 크기가 10이고 키가 10, 20, 30이면, 해시 함수(key % 10)는 모두 0을 반환합니다. 이렇게 되면 대부분의 값이 인덱스 0에 저장되어, 균등 분포를 해칩니다. 이러한 현상을 클러스터링^Clustering이라 합니다.

물리적으론 배열이지만, 데이터를 구조화된 방식으로 매핑하기 때문에 테이블이라 부른다.

소수는 1과 자기 자신 외에는 나누어 떨어지지 않기 때문에 키와 공약수를 가지지 않을 확률이 높습니다. 따라서 키 값이 어떤 패턴을 갖고 있어도 해시 결과는 서로 다른 인덱스에 분산될 가능성이 높습니다.

예를 들어 테이블의 크기를 13으로 하면, 12 % 13 = 12, 24 % 13 = 11, 36 % 13 = 10처럼 충돌이 줄고 균등 분포를 이룰 수 있습니다.

hashfunc_str.cpp
uint32_t hash(std::string_view str) noexcept {
    uint32_t h = 5381u;
    for (char ch : str) {
        h = ((h << 5) + h) + ch;
    }

    return h % TABLE_SIZE;
}

문자열을 해시로 사용할 경우 보통 위 코드의 해시 함수를 사용합니다. "djb2" 알고리즘으로 부릅니다. 단순하지만 효율적이고 충돌이 적은 편으로 평가 받고 있습니다.

h = h * 33 + ch는 h = ((h << 5) + h) + ch; 코드와 같으며, 조금 더 빠른 연산을 위해 비트 연산자를 이용해 최적화 한 코드입니다.

hash.cpp
#include <functional>
#include <iostream>

int main(int argc, char* argv[]) {
    std::string key = "sibal";
    std::hash<std::string> hasher;
    size_t hashValue = hasher(key);

    std::cout << "Hash of " << key << ": " << hashValue << "\n";
}

C++은 functional 헤더에서 std::hash라는 기본 해시 함수 객체를 제공하고 있습니다. std::unordered_map 등 헤시 기반 컨테이너에서 내부적으로 사용되고 있습니다.

기본 데이터 타입(int, std::string 등)에 대한 기본 해시가 구현되어 있고, 사용자 정의 타입은 별도로 구현해야 합니다.

충돌 처리

같은 해시 값(인덱스)을 가지는 서로 다른 키들이 존재할 수 있습니다. 이를 위해 충돌을 대비하는 방법이 필요하며, 크게 두 가지가 있습니다.

체이닝오픈 어드레싱

체이닝^Chaining은 동일한 해시 값을 가진 키들이 하나의 버킷에 링크드 리스트나 기타 다른 자료구조 형태로 저장되는 기법을 말합니다.

충돌이 발생하면 각 버킷에 있는 특정 자료 구조에 데이터를 추가해나가는 방식입니다.

간단하고 유연한 구조

링크드 리스트를 이용하면 구현이 쉽고, 각 노드에 데이터를 추가하기 때문에 사용도 쉽습니다.

다만, 노드가 추가될 때마다 메모리 사용량이 증가하기 때문에 주의가 필요합니다.
탐색 시간 증가

충돌이 잦아지면 한 버킷 내에 추가되는 데이터가 많아져 선형 탐색 시 굉장히 오래 걸릴 수 있습니다. 최악의 경우 \(O(n)\)입니다.

오픈 어드레싱^{Open Addressing}은 해시 충돌이 발생하면 해시 테이블 내에서 다른 빈 공간(버킷)을 찾아 데이터를 저장하는 방식입니다. 추가적인 자료구조 없이 테이블 배열 내에서 충돌을 해결합니다.

탐색 전략

선형 탐사제곱 탐사이중 해싱

충돌 발생 시 인접한 버킷으로 이동하여 빈 공간을 찾습니다.

구현이 간단하지만, 빈 공간이 부족해지면 성능 저하 문제가 발생합니다.

충돌 발생 시 일정한 제곱수 간격으로 이동하면서 빈 공간을 찾습니다.

선형 탐사에 비해 빈 공간이 부족해지는 문제를 최소화할 수 있지만 완벽하진 않습니다.

두 번째 해시 함수를 사용해 충돌이 발생하면 고정된 간격이 아닌 동적인 간격으로 빈 공간을 찾습니다.

균등 분포의 장점이 있지만, 해시 함수의 설계가 복잡해지거나 성능에 영향을 줄 수 있습니다.

로드 팩터

로드 팩터^{Load Factor}는 해시 테이블의 밀도를 나타내는 지표로, 얼마나 가득 찼는 지를 나타내는 비율입니다. \(n ÷ m\)식으로 구할 수 있고, \(n\)과 \(m\)은 각각 저장된 키-값의 개수와 테이블의 크기입니다.

이 로드 팩터는 해시 테이블의 성능과 메모리 효율성을 측정하고 조율하는 핵심 요소 중 하나입니다.

재해싱

재해싱^Rehashing은 해시 테이블의 크기를 조정하고 데이터를 재배치하는 과정입니다. 로드 팩터가 특정 임계값을 초과하면 해시 테이블의 성능 저하를 방지하기 위해 재해싱 과정을 수행합니다.

체이닝 방식의 경우, 로드 팩터가 1.0을 초과해도 동작은 가능하지만 성능을 위해 1.0 ~ 2.0 사이의 범위일 때 재해싱을 수행합니다.

오픈 어드레싱의 경우, 로드 팩터의 값이 1.0이면 더 이상 삽입 불가함을 의미합니다. 그래서 0.7 ~ 0.75 정도가 되면 재해싱을 고려합니다.

재해싱은 비용이 많이 드는 작업이기 때문에 적절한 테이블의 크기와 임계값 설정이 필요합니다.

구현

기본 구성

hashtable.cpp
#include <functional>       // (1)
#include <iostream>
#include <list>             // (2)
#include <string_view>
#include <vector>

//! @brief 테이블 크기 (소수 설정)
constexpr auto TABLE_SIZE = 101;

//! @brief 해시 테이블
class HashTable {
private:
    //! @brief 엔트리
    //! @note 키-값 쌍을 저장하는 구조체
    struct Entry {
        std::string key;
        int value;
    };

    std::vector<std::list<Entry>> m_Buckets;        //!< 버킷 배열
    size_t m_Size;                                  //!< 저장된 엔트리의 수

    //! @brief 해시 메서드
    //! @param key 키
    //! @param size 테이블 크기
    //! @return 해시 값
    size_t hash(std::string_view key) noexcept const {
        return std::hash<std::string_view>{}(key) % TABLE_SIZE;
    }

public:
    //! @brief 생성자
    HashTable() noexcept {
        m_Buckets.resize(TABLE_SIZE);
        m_Size = 0;
    }

    //! @brief 소멸자
    ~HashTable() noexcept {
        for (auto& bucket : m_Buckets) {
            bucket.clear();
        }
    }
};

std::hash 사용을 위해 포함
체이닝을 위해 연결 리스트 사용

Entry는 하나의 데이터를 나타내는 구조체로, 키와 값을 가집니다. 엔트리는 해시 테이블에서 관습적으로 사용되는 용어로, 테이블 안의 데이터를 의미합니다.

m_Buckets는 버킷 배열로, 각 요소는 std::list 컨테이너를 사용하고 있습니다. 링크드 리스트로, 체이닝 구조를 기반으로 합니다.

m_Size는 실제 저장된 키-값(엔트리)의 개수입니다. 리사이징을 고려해서 추가한 멤버 변수인데, 복잡해질까봐 리사이징은 생략했습니다.

hash() 메서드는 C++의 표준 해시 함수를 사용했습니다.

삽입

해시 테이블에 버킷을 추가합니다.

본 예제의 코드는 체이닝과 고정 크기를 기반으로 하기 때문에 평균 시간 복잡도는 \(O(1)\)이고, 최악은 \(O(n)\)입니다.

classstl

insert.cpp
// ...

class HashTable {
    // ...

    //! @brief 엔트리 데이터를 추가하는 메서드
    //! @param key 키
    //! @param value 값
    void Insert(std::string_view key, int value) noexcept {
        // (1) 오류 검사
        if (key.empty()) { return; }

        // (2) 해시 값 (인덱스)
        size_t idx = hash(key);

        // (3) 엔트리 조회
        for (auto& entry : m_Buckets[idx]) {
            // 키가 같다면, 값만 갱신하고 종료
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }

        // (4) 엔트리 추가 (체이닝)
        m_Buckets[idx].push_back({ std::string(key), value });

        // (5) 크기 증가
        m_Size += 1;
    }

    //! @brief 인덱스 연산자 오버로딩
    //! @param key 키
    //! @return 값
    int& operator[](std::string_view key) noexcept {
        // (1) 해시 값 (인덱스)
        size_t idx = hash(key);

        // (2) 엔트리 조회 - 존재하는 키라면 해당 값을 반환
        for (auto& entry : m_Buckets[idx]) {
            if (entry.key == key) {
                return entry.value;
            }
        }

        // (3) 엔트리 추가 및 반환
        m_Buckets[idx].push_back({ std::string(key), 0 });
        m_Size += 1;

        return m_Buckets[idx].back().value;
    }
};

Insert연산자 오버로딩

오류 검사

문자열의 값이 비어 있으면 아래의 코드를 수행하지 않도록 합니다.
해시 값 (인덱스)

해시 메서드를 통해 인덱스를 취득합니다.
엔트리 조회

이미 해당 키가 존재한다면 값만 변경한 후 종료하도록 합니다.
엔트리 추가 (체이닝)

같은 키가 없으면 엔트리를 추가합니다.
크기 증가

엔트리가 추가되었으니 크기를 1 증가시킵니다.

해시 값 (인덱스)

해시 메서드를 통해 인덱스를 취득합니다.
엔트리 조회

키가 이미 존재하는 지 순회하여 찾은 후 값을 반환합니다.
엔트리 추가 및 반환

존재하지 않은 키라면 추가한 후, 해당 값을 반환하도록 합니다.

std::mapstd::unordered_map

map_insert.cpp
#include <map>

int main(int argc, char* argv[]) {
    // map
    std::map<std::string, int> map;

    // insert 1
    map.insert({ "dog", 4 });
    map.insert({ "cat", 3 });

    // insert 2
    map["rabbit"] = 6;

    return 0;
}

std::map은 레드-블랙 트리 기반 연관 컨테이너로, 키를 기준으로 데이터를 정렬합니다. 키 정렬이 필요하거나 범위 쿼리를 사용할 때 적합합니다. 해시 테이블은 아니지만, 키-값 쌍을 저장한다는 점에서 연관 자료구조로 언급됩니다. 이 컨테이너는 키를 기반으로 데이터를 정렬하기 때문에 조금의 오버헤드가 있습니다.

std::map에서 insert() 메서드를 사용해 데이터를 추가할 수 있습니다.

unordered_map_insert.cpp
#include <unordered_map>

int main(int argc, char* argv[]) {
    // unordered_map
    std::unordered_map<std::string, int> umap;

    // insert 1
    umap.insert({ "dog", 4 });
    umap.insert({ "cat", 3 });

    // insert 2
    umap["rabbit"] = 6;

    return 0;
}

std::unordered_map은 연관 배열을 구현한 STL 컨테이너 중 하나로, std::map 컨테이너와는 다르게 정렬을 수행하지 않습니다. C++ STL에서 제공하는 해시 테이블입니다. 키를 해시 함수로 매핑하여 값을 찾을 수 있도록 합니다.

std::map과 동일하게 insert() 메서드를 사용해 데이터를 추가할 수 있습니다.

제거

해시 테이블의 특정 버킷을 제거합니다.

본 예제의 코드는 체이닝과 고정 크기를 기반으로 하기 때문에 평균 시간 복잡도는 \(O(1)\)이고, 최악은 \(O(n)\)입니다.

classstl

remove.cpp
// ...

class HashTable {
    // ...

    //! @brief 엔트리 데이터를 제거하는 메서드
    //! @param key 키
    //! @return 성공(true), 실패(false)
    bool Remove(std::string_view key) noexcept {
        // (1) 오류 검사
        if (key.empty()) { return false; }

        // (2) 해시 값 (인덱스)
        size_t idx = hash(key);

        // (3) 버킷
        auto& bucket = m_Buckets[idx];

        // (4) 순회
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->key == key) {
                bucket.erase(it);
                m_Size -= 1;
                return true;
            }
        }

        return false;
    }
};

오류 검사

올바르지 않은 키는 실패를 반환하도록 합니다.
해시 값 (인덱스)

해시 메서드를 통해 인덱스를 취득합니다.
버킷

인덱스에 해당하는 버킷을 취득합니다.
순회

링크드 리스트를 사용했기 때문에 순회하여 키가 같으면 제거한 후, true를 반환합니다.

std::mapstd::unordered_map

remove_map.cpp
// ...

int main(int argc, char* argv[]) {
    // ...

    // 제거 1
    map.erase("dog");

    // 제거 2 - 전체 제거 (clear()로 대체 가능)
    map.erase(map.begin(), map.end());

    return 0;
}

erase() 메서드를 통해 특정 키를 가진 데이터를 삭제할 수 있습니다. 또는 범위를 지정해서 제거하는 것도 가능합니다.

remove_umap.cpp
// ...

int main(int argc, char* argv[]) {
    // ...

    // 제거 1
    umap.erase("dog");

    // 제거 2 - 전체 제거 (clear()로 대체 가능)
    umap.erase(umap.begin(), umap.end());

    return 0;
}

erase() 메서드를 통해 특정 키를 가진 데이터를 삭제할 수 있습니다. 또는 범위를 지정해서 제거하는 것도 가능합니다.

전체 코드

classstl

hashtable.cpp
#include <functional>       // 
#include <iostream>
#include <list>             // 
#include <string_view>
#include <vector>

//! @brief 테이블 크기 (소수 설정)
constexpr auto TABLE_SIZE = 101;

//! @brief 해시 테이블
class HashTable {
private:
    //! @brief 엔트리
    //! @note 키-값 쌍을 저장하는 구조체
    struct Entry {
        std::string key;
        int value;
    };

    std::vector<std::list<Entry>> m_Buckets;        //!< 버킷 배열
    size_t m_Size;                                  //!< 저장된 엔트리의 수

    //! @brief 해시 메서드
    //! @param key 키
    //! @param size 테이블 크기
    //! @return 해시 값
    size_t hash(std::string_view key) const noexcept {
        return std::hash<std::string_view>{}(key) % TABLE_SIZE;
    }

public:
    //! @brief 생성자
    HashTable() noexcept {
        m_Buckets.resize(TABLE_SIZE);
        m_Size = 0;
    }

    //! @brief 소멸자
    ~HashTable() noexcept {
        for (auto& bucket : m_Buckets) {
            bucket.clear();
        }
    }

    //! @brief 엔트리 데이터를 추가하는 메서드
    //! @param key 키
    //! @param value 값
    void Insert(std::string_view key, int value) noexcept {
        // (1) 오류 검사
        if (key.empty()) { return; }

        // (2) 해시 값 (인덱스)
        size_t idx = hash(key);

        // (3) 엔트리 조회
        for (auto& entry : m_Buckets[idx]) {
            // 키가 같다면, 값만 갱신하고 종료
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }

        // (4) 엔트리 추가 (체이닝)
        m_Buckets[idx].push_back({ std::string(key), value });

        // (5) 크기 증가
        m_Size += 1;
    }

    //! @brief 인덱스 연산자 오버로딩
    //! @param key 키
    //! @return 값
    int& operator[](std::string_view key) noexcept {
        // (1) 해시 값 (인덱스)
        size_t idx = hash(key);

        // (2) 엔트리 조회 - 존재하는 키라면 해당 값을 반환
        for (auto& entry : m_Buckets[idx]) {
            if (entry.key == key) {
                return entry.value;
            }
        }

        // (3) 엔트리 추가 및 반환
        m_Buckets[idx].push_back({ std::string(key), 0 });
        m_Size += 1;

        return m_Buckets[idx].back().value;
    }

    //! @brief 엔트리 데이터를 제거하는 메서드
    //! @param key 키
    //! @return 성공(true), 실패(false)
    bool Remove(std::string_view key) noexcept {
        // (1) 오류 검사
        if (key.empty()) { return false; }

        // (2) 해시 값 (인덱스)
        size_t idx = hash(key);

        // (3) 버킷
        auto& bucket = m_Buckets[idx];

        // (4) 순회
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->key == key) {
                bucket.erase(it);
                m_Size -= 1;
                return true;
            }
        }

        return false;
    }
};

int main(int argc, char* argv[]) {
    // 해시 테이블
    HashTable ht;

    // 데이터 추가
    ht["dog"] = 4;
    ht["cat"] = 3;
    ht["rabbit"] = 6;

    // 출력
    std::cout << ht["dog"] << "\n";
    std::cout << ht["cat"] << "\n";
    std::cout << ht["rabbit"] << "\n";

    return 0;
}

std::mapstd::unordered_map

map.cpp
#include <iostream>
#include <map>

int main(int argc, char* argv[]) {
    // map
    std::map<std::string, int> map;

    // 데이터 추가
    map["dog"] = 4;
    map["cat"] = 3;
    map["rabbit"] = 6;

    // 출력
    for (auto m : map) {
        std::cout << m.second << "\n";
    }

    return 0;
}

3 4 6

키를 기반으로 정렬을 수행하기 때문에 결과는 위와 같이 나타납니다.

umap.cpp
#include <iostream>
#include <unordered_map>

int main(int argc, char* argv[]) {
    // unordered_map
    std::unordered_map<std::string, int> umap;

    // 데이터 추가
    umap["dog"] = 4;
    umap["cat"] = 3;
    umap["rabbit"] = 6;

    // 출력
    for (auto m : umap) {
        std::cout << m.second << "\n";
    }

    return 0;
}