[c++] 커스텀 해시 함수 구현

08 Dec 2023

C++에서 unordered_map 또는 unordered_set을 사용할 때, 사용자 정의 객체를 키로 사용하기 위해서는 해시 함수를 정의해야 합니다. 유용한 해시 함수를 직접 만들어보겠습니다.

해시 함수란?

해시 함수는 임의의 길이의 데이터를 고정된 길이의 값으로 매핑하는 함수입니다. 키로 사용되는 데이터가 같다면 해시 함수는 항상 동일한 값을 반환해야 합니다.

해시 함수를 구현하는 방법

C++에서 unordered_map 또는 unordered_set을 사용할 때 객체를 키로 사용한다면, 해당 객체의 타입에 맞는 해시 함수를 구현해야 합니다. 예를 들어, 문자열을 키로 사용한다면 이를 처리하기 위한 해시 함수를 구현해야 합니다.

아래는 문자열을 키로 사용하는 경우의 해시 함수를 구현한 예시입니다.

#include <iostream>
#include <unordered_map>

struct MyKey {
    std::string value;

    // 해시 함수 구현
    size_t operator()(const MyKey& key) const {
        // 문자열을 해시하는 간단한 방법
        size_t hash = 0;
        for (char ch : key.value) {
            hash = (hash * 31) + ch; // 소수를 이용한 해싱
        }
        return hash;
    }
};

int main() {
    std::unordered_map<MyKey, int, MyKey> myMap;  // MyKey를 키로 사용하는 unordered_map
    MyKey key{ "example" };
    myMap[key] = 1;  // 사용자 정의 객체를 키로 사용한 예시
    //...
    return 0;
}

해시 함수 operator()는 MyKey 타입의 객체를 받아 해시 값을 반환합니다. 이 예시에서는 간단한 문자열을 해싱하는 방법을 사용하였습니다.

해시 충돌 다루기

해시 함수를 구현할 때는 반드시 해시 충돌을 고려해야 합니다. 해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 경우를 말합니다. 이를 다루기 위한 방법으로는 체이닝, 개방 주소법 등이 있습니다.

마무리

사용자 정의 객체를 키로 사용하는 경우, 적절한 해시 함수를 구현하여 unordered_map 또는 unordered_set을 효과적으로 활용할 수 있습니다.

참고 자료: