[c++] 사용자 정의 데이터 타입을 다루는 해시 테이블

08 Dec 2023

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조입니다. 하지만 C++의 기본 해시 함수는 사용자 정의 데이터 타입에 대해서는 제공되지 않습니다. 이를 해결하기 위해서는 std::hash 템플릿을 특수화하여 사용자 정의 데이터 타입에 대한 해시 함수를 정의해야 합니다.

사용자 정의 데이터 타입

다음은 사용자 정의 데이터 타입인 Book 클래스의 정의입니다.

#include <string>

class Book {
public:
    std::string title;
    std::string author;
    int year;

    // 생성자, 멤버 함수 등
};

해시 함수 특수화

Book 클래스에 대한 해시 함수를 특수화하기 위해 다음과 같이 std::hash의 템플릿을 특수화합니다.

#include <functional>

namespace std {
    template<>
    struct hash<Book> {
        size_t operator()(const Book& b) const {
            size_t titleHash = hash<std::string>()(b.title);
            size_t authorHash = hash<std::string>()(b.author);
            size_t yearHash = hash<int>()(b.year);
            return titleHash ^ (authorHash << 1) ^ (yearHash << 2);
        }
    };
}

위 코드에서 Book 클래스를 위한 해시 함수를 정의하고, std::hash 템플릿을 특수화하여 각 멤버 변수들을 해싱하여 합쳐줍니다.

해시 테이블 사용

이제 Book 객체를 다루는 해시 테이블을 사용할 수 있습니다.

#include <unordered_map>

int main() {
    std::unordered_map<Book, int> bookTable;
    Book book1{"The Great Gatsby", "F. Scott Fitzgerald", 1925};
    Book book2{"To Kill a Mockingbird", "Harper Lee", 1960};
    
    bookTable[book1] = 1;
    bookTable[book2] = 2;

    // 해시 테이블 사용
}

이제 Book 클래스를 사용하여 해시 테이블을 만들고, 효율적으로 데이터를 저장하고 검색할 수 있습니다.

결론

C++에서 사용자 정의 데이터 타입을 다루는 해시 테이블을 구현하기 위해서는 std::hash를 특수화하여 해당 데이터 타입에 대한 해시 함수를 정의해야 합니다. 이를 통해 사용자 정의 데이터 타입을 효율적으로 해싱하여 해시 테이블에 사용할 수 있습니다.

참고 자료

C++ Reference: std::hash
C++ Reference: std::unordered_map