C++ Academy · 강의

사용자 지정 해시 함수

직접 만든 타입 해시하기

사용자 지정 해시 함수은(는) CoddyKit의 무료 C++ Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C++ Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C++ Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

사용자 지정 hash가 필요한 이유

정렬되지 않은 컨테이너는 키에 hash를 적용할 방법이 필요합니다. 기본 제공 타입과 std::string에는 이미 hash가 있지만, 사용자 정의 타입에는 없습니다. 직접 제공해야 합니다.

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

std::hash 템플릿

std::hash는 값을 size_t로 매핑하는 함수 객체입니다. 함수처럼 호출할 수 있습니다.

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

hash를 적용할 구조체

두 개의 int를 포함하는 Point가 있다고 가정해 보겠습니다. 이를 unordered_set에 저장하려면 동등성과 hash가 모두 필요합니다.

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

hash 함수 객체 작성하기

hash 함수 객체는 operator()를 포함하고 size_t를 반환하는 구조체입니다. 일반적으로 XOR과 시프트를 사용해 필드의 hash를 결합합니다.

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

hash 함수 객체 사용하기

hash 함수 객체를 unordered 컨테이너의 두 번째 템플릿 인수로 전달하세요.

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

동등성도 필요합니다

두 키의 hash가 충돌하면 같은 bucket에 들어갑니다. 그러면 컨테이너가 operator==를 사용해 두 키를 구분하므로 동등성 비교가 반드시 필요합니다.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

hash를 map 키로 사용하기

동일한 사용자 지정 hash를 사용하면 구조체를 unordered_map의 키로 사용할 수 있습니다.

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

여러 필드 결합하기

일반적인 도우미 함수는 boost::hash_combine과 비슷한 곱셈 후 덧셈 패턴을 사용해 한 번에 한 필드씩 hash를 결합합니다.

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

균등한 hash 분포

항상 같은 값을 반환하는 나쁜 hash는 모든 요소를 하나의 bucket에 넣어 성능을 O(n)으로 떨어뜨립니다. 모든 필드의 비트를 잘 섞으세요.

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

std::hash 특수화하기

또는 자신의 타입에 대해 std::hash를 특수화하면 함수 객체를 명시적으로 전달하지 않아도 작동하게 할 수 있습니다.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

hash로 사용하는 람다

C++20에서는 타입을 전달해 상태가 없는 람다를 hash로 사용할 수도 있습니다.

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

빠른 확인

사용자 지정 hash를 제대로 이해했는지 테스트해 보세요.

복습

사용자 정의 타입에 hash를 적용하는 방법을 배웠습니다.

size_t를 반환하는 hash 함수 객체를 제공하거나 std::hash를 특수화합니다
충돌하는 키를 구분할 수 있도록 operator==도 제공해야 합니다
균등한 분포를 위해 필드의 hash를 적절히 결합합니다

다음에는 bucket과 로드 팩터가 성능에 미치는 영향을 알아봅니다.

자주 묻는 질문

“사용자 지정 해시 함수” 강의는 무료인가요?

네 — “사용자 지정 해시 함수” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C++ Academy 강의 전체를 잠금 해제할 수 있습니다. C++ Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“사용자 지정 해시 함수”에서 뭘 배우나요?

직접 만든 타입 해시하기 브라우저에서 직접 실행하는 실습 코드로 C++ Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

C++ Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 C++ Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“사용자 지정 해시 함수” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 C++ Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 C++ Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← C++ Academy(으)로 돌아가기