Utilities

3.10 Custom Hash

개념

C++의 unordered_set은 키의 포함 여부를, unordered_map은 키에 연결된 값을 해시로 찾습니다. 해시 함수는 키를 size_t 타입의 정수로 바꾸는 함수입니다. 컨테이너는 이 값을 이용해 키를 저장하거나 찾을 버킷을 정합니다. 버킷은 여러 키가 모이는 저장 구역입니다.

int, string에는 표준 해시가 제공됩니다. 직접 만든 좌표 구조체처럼 여러 값을 하나의 키로 사용할 때는 키를 비교하는 방법과 해시를 구하는 방법을 함께 정의합니다.

같은 키인지 판단하는 기준

좌표 (x,y)(x,y)를 키로 사용한다면 xx와 yy가 모두 같아야 같은 키입니다. 구조체의 bool operator==(const Key& a) const에서 두 좌표를 비교하면 기본 동등 비교가 이 연산자를 사용합니다.

비교결과
(1,2)(1,2)와 (1,2)(1,2)같은 키
(1,2)(1,2)와 (2,1)(2,1)다른 키
(1,2)(1,2)와 (1,3)(1,3)다른 키

해시 값이 같다는 것과 키가 같다는 것은 구분합니다. 서로 다른 키의 해시 값이 같아지는 충돌이 발생해도 컨테이너는 동등 비교로 실제 키를 구별합니다. 반대로 같은 키로 판단하는 두 값은 반드시 같은 해시 값을 반환해야 합니다. 이 조건은 C++ 표준 초안의 unordered 컨테이너 요구사항에 명시되어 있습니다.

operator()로 해시 함수 작성

해시를 담당하는 구조체에 size_t operator()(const Key& a) const를 정의합니다. 그러면 그 구조체의 객체를 함수처럼 호출하여 키의 해시 값을 구할 수 있습니다. operator==는 두 키를 비교하지만, 해시의 operator()는 키 하나를 받아 정수 하나를 반환합니다.

여기서는 좌표 범위가 0≤x,y<1 0000\le x,y<1\,000이라고 정하고 다음 식을 사용합니다.

h(x,y)=1 000x+y.h(x,y)=1\,000x+y.

(1,2)(1,2)는 1 0021\,002, (2,1)(2,1)은 2 0012\,001에 대응합니다. yy가 1 0001\,000보다 작으므로 xx가 하나 증가할 때의 간격을 넘지 않습니다. 이 범위에서는 계산한 값을 1 0001\,000으로 나눈 몫과 나머지로 원래 좌표를 구할 수 있어 서로 다른 좌표가 서로 다른 계산값을 만듭니다.

단순히 x+yx+y를 반환하면 (1,2)(1,2)와 (2,1)(2,1)처럼 순서가 다른 키가 같은 값을 만들고, 합이 같은 좌표들이 한곳에 몰릴 수 있습니다. 키를 구성하는 각 값과 순서가 해시 값에 반영되도록 정합니다.

좌표를 한 정수로 합치는 이 방식은 범위 조건을 이용합니다. 입력 범위가 달라지면 곱할 기준과 계산 자료형을 다시 정해야 합니다. 범위가 정해지지 않은 키는 각 필드의 std::hash 결과를 순서를 고려하여 조합하는 등의 방법을 사용합니다. 서로 다른 해시 값도 컨테이너가 버킷을 정하는 과정에서 같은 버킷에 배치될 수 있습니다.

컨테이너에 해시 타입 전달

키 타입을 Key, 해시를 계산하는 타입을 Hash라고 하면 다음과 같이 선언합니다.

용도선언
좌표의 중복 제거·포함 확인unordered_set<Key, Hash> s;
좌표별 등장 횟수 저장unordered_map<Key, int, Hash> cnt;

템플릿 인자에는 해시 함수 객체의 타입인 Hash를 전달합니다. 컨테이너가 해시 객체를 보관하고 필요할 때 operator()를 호출합니다. 키 비교는 기본적으로 operator==를 사용합니다. 별도의 동등 비교 타입을 쓴다면 그 기준과 해시 기준도 함께 맞춰야 합니다.

해시 사용 시 유의점

같은 키의 해시 값은 컨테이너를 사용하는 동안 일관되어야 합니다. 호출할 때마다 달라지는 난수나 변경 가능한 외부 값에 의존하면 이미 넣은 키를 제대로 찾을 수 없습니다. 해시 함수는 전달받은 키를 변경하지 않고 계산합니다. C++ 표준 초안의 해시 함수 요구사항

unordered_ 컨테이너의 순회 순서는 정렬 순서나 입력 순서를 보장하지 않습니다. 정렬된 출력이 필요하면 키를 별도로 모아 정렬합니다. 값 조회만 할 때는 find 또는 C++20의 contains를 사용할 수 있습니다. unordered_map의 operator[]는 없는 키를 조회하면 기본값을 가진 항목을 새로 만듭니다.

많은 원소를 넣을 예정이라면 reserve로 예상 원소 수에 맞게 버킷을 준비할 수 있습니다. 재해시가 일어나면 저장한 반복자는 무효화되므로 다시 구해야 합니다. reserve는 충돌이 많은 해시 함수 자체를 개선하지는 않습니다.

복잡도

저장한 서로 다른 키의 수를 NN이라고 합니다. 정수 필드 두 개를 계산하는 해시와 동등 비교는 각각 O(1)O(1)입니다.

연산·저장 대상평균 시간복잡도최악 시간복잡도공간복잡도
키 하나의 삽입·검색·삭제O(1)O(1)O(N)O(N)전체 저장 O(N)O(N)

충돌이 많으면 같은 버킷의 키를 여러 개 비교해야 하므로 연산이 느려질 수 있습니다. 해시를 사용한다고 모든 입력에서 상수 시간이 보장되는 것은 아닙니다.

예제

문제

좌표 NN개가 주어진다. 질의로 주어지는 각 좌표가 입력에 몇 번 등장했는지 구하여라.

입력

첫째 줄에 좌표 수 NN과 질의 수 QQ가 공백을 사이에 두고 주어진다. 1≤N,Q≤1001\le N,Q\le100이다.

다음 NN개 줄에 좌표 xx, yy가 공백을 사이에 두고 주어진다. 이어지는 QQ개 줄에 질의할 좌표 xx, yy가 같은 형식으로 주어진다. 모든 좌표는 0≤x,y<1 0000\le x,y<1\,000을 만족한다.

출력

각 질의에 대해 해당 좌표의 등장 횟수를 한 줄에 하나씩 출력한다. 등장하지 않은 좌표의 횟수는 00이다.

예제 입력

5 4
1 2
2 1
1 2
0 0
1 2
1 2
2 1
0 0
9 9

예제 출력

3
1
1
0

예제 코드

C++20

#include <iostream>
#include <unordered_map>
#include <cstddef>

using namespace std;

struct Key {
    int x, y;

    bool operator==(const Key& a) const {
        // 두 좌표가 모두 같으면 같은 키
        return x == a.x && y == a.y;
    }
};

struct Hash {
    size_t operator()(const Key& a) const {
        // 0 이상 1000 미만인 두 좌표를 하나의 값으로 변환
        return static_cast<size_t>(a.x) * 1000 + a.y;
    }
};

int main() {
    int n, q, i;
    Key a;
    unordered_map<Key, int, Hash> cnt;
    unordered_map<Key, int, Hash>::iterator it;

    cin >> n >> q;
    cnt.reserve(n);
    for (i = 0; i < n; ++i) {
        cin >> a.x >> a.y;
        ++cnt[a];
    }

    for (i = 0; i < q; ++i) {
        cin >> a.x >> a.y;
        // 없는 키를 추가하지 않고 조회
        it = cnt.find(a);
        if (it != cnt.end()) cout << it->second << '\n';
        else cout << 0 << '\n';
    }
}