1. 사용자 정의 키가 필요한 이유
처음 unordered_map을 보면 “키 = int 또는 string” 같은 이야기로 보일 수 있습니다. 하지만 실제로는 “(user, tag)로 문제 찾기”나 “(city, date)로 결과 캐싱” 같은 상황이 자주 생깁니다. 이런 경우 하나의 int로는 부족하고 여러 필드를 합친 복합 키가 필요합니다.
예를 들어 학습용 미니앱(가칭 TaskBook)을 생각해봅시다. 우리는 태스크를 저장하고, 각 태스크는 id, 소유자(ownerId)와 태그(tag, 예: "cpp" 또는 "home")를 가집니다. 우리는 빠른 색인을 원합니다:
- (ownerId, tag) → 태스크 id 집합
기술적으로 이는 키가 두 개의 값을 가져야 함을 의미합니다. 따라서 우리는 사용자 정의 키 타입 — struct Key — 을 만듭니다.
검색 과정에서 unordered_map이 실제로 무슨 일을 하는지에 대한 개략도:
flowchart LR
A["키 (ownerId, tag)"] --> B["hash(key) -> 숫자"]
B --> C["버킷 선택"]
C --> D["후보들을 operator==로 확인"]
D --> E["값을 찾았는지 여부"]
2. struct Key 설계
복합 키는 모든 경우에 대한 구조체가 아니라, 바로 그 레코드를 구분하는 유일성의 여권이어야 합니다. 즉, 정확히 레코드를 구분하는 필드만 포함해야 합니다. 불필요한 필드를 추가하면 인덱스가 지나치게 세분화되고, 중요한 필드를 빼먹으면 서로 다른 엔티티를 혼동하게 됩니다.
우리 TaskBook에서는 인덱스 키가 ownerId와 tag의 쌍이 될 것입니다.
#include <string>
struct OwnerTagKey {
int ownerId{};
std::string tag;
};
간단한 점에 주의하세요: 키는 보통 복사하고 비교하기 편한 “작은” 객체입니다. 여기서는 int와 string이 괜찮습니다. 만약 키가 거대한(예: 긴 태스크 본문을 포함하는) 객체라면 이상합니다: 키는 레코드를 식별하는 데 필요한 것만 포함해야 합니다.
또한 실무적인 중요한 포인트: 키는 “안정적”이어야 합니다. 만약 (ownerId, "cpp")로 unordered_map에 넣은 후 키를 변경한다면 컨테이너가 엉망이 됩니다. 연관 컨테이너에서는 키가 사실상 변경 불가능한 것으로 간주됩니다(그리고 unordered_map에서는 pair 내부의 키가 const로 저장됩니다).
3. operator== 작성
컨테이너는 “이 두 키가 같은 키인가?”라는 질문에 답할 수 있어야 합니다. unordered_* 계열에서는 보통 이 비교를 operator==로 구현합니다.
철학적인 고민은 필요 없습니다. 키가 “(ownerId, tag)”라면 동등성은 문자 그대로입니다: ownerId가 같고 tag가 같아야 합니다.
#include <string>
struct OwnerTagKey {
int ownerId{};
std::string tag;
};
bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
return a.ownerId == b.ownerId && a.tag == b.tag;
}
만약 “ownerId만 비교하고 tag는 무시하자”라고 결정하면, 컨테이너 관점에서는 (1, "cpp")와 (1, "home")가 같은 키로 간주됩니다. 때로는 의도한 동작일 수 있지만, 그럴 경우 키 설계 자체가 달라야 합니다.
간단한 검사 예:
#include <iostream>
#include <string>
struct OwnerTagKey {
int ownerId{};
std::string tag;
};
bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
return a.ownerId == b.ownerId && a.tag == b.tag;
}
int main() {
OwnerTagKey k1{1, "cpp"};
OwnerTagKey k2{1, "cpp"};
OwnerTagKey k3{1, "home"};
std::cout << (k1 == k2) << '\n'; // 1
std::cout << (k1 == k3) << '\n'; // 0
}
4. std::hash<T> 계약과 operator==의 일치성
해시 함수는 키를 std::size_t 타입의 숫자로 바꾸는 방법입니다. 컨테이너는 이 숫자를 사용해 요소가 있을 “대략적인 위치”를 빠르게 찾습니다. 해시는 고유한 지문이 아닙니다. 충돌은 가능하고 허용됩니다: 서로 다른 키가 같은 해시를 가질 수 있으며, 컨테이너는 이후 ==로 이를 구분합니다.
하지만 동작을 보장하기 위한 강력한 규칙(계약)이 있습니다:
만약 a == b라면 반드시 hash(a) == hash(b)여야 합니다.
이 규칙을 어기면 “삽입은 되었지만 검색이 되지 않는” 신비로운 현상이 발생합니다. 데이터가 존재하는데 검색이 이를 못 찾는 그런 상황을 만나게 됩니다.
참고로 충돌 문제는 성능뿐 아니라 보안 측면도 있습니다. 표준 토론에서는 다수의 키가 동일한 해시를 갖도록 유도해 컨테이너의 시간 복잡도를 악화시키는 공격 위험이 논의된 적이 있습니다.
계약이 깨진 경우의 예
해시 관련 문제는 두 종류로 구분할 수 있습니다.
첫 번째는 “해시가 나쁨”입니다. 이 경우 프로그램은 올바르지만 큰 데이터에서 느려질 수 있습니다. 예를 들어 return 0;처럼 하면 모든 키가 하나의 버킷으로 몰립니다. 동작은 하지만 성능은 나쁩니다.
두 번째는 “계약이 깨짐”입니다. 이 경우 operator==와 hash가 서로 다른 필드 집합을 사용할 때 발생합니다. 그러면 정확성이 깨져 삽입한 요소를 찾지 못하는 문제가 생깁니다. 성능 문제가 아니라 논리적 오류입니다.
예를 들어 다음과 같이 하면 안 됩니다: ==는 ownerId만 보고, 해시는 ownerId와 tag를 둘 다 사용하는 경우입니다. 그러면 같은 키로 판정되는 두 객체의 해시가 달라질 수 있어 규칙 a == b ⇒ hash(a) == hash(b)을 위반합니다.
#include <string>
struct OwnerTagKey {
int ownerId{};
std::string tag;
};
bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
return a.ownerId == b.ownerId; // tag를 무시함 — 이 키에는 적합하지 않음
}
만약 해시가 tag를 사용한다면 “같은” 키들이 서로 다른 버킷에 배치되어 컨테이너가 비정상적으로 동작합니다. 진단 방법은 단순합니다: unordered_map이 요소를 “잃어버린”다면 먼저 ==와 hash의 일치를 확인하세요. 대부분의 경우 원인은 여기에 있습니다.
5. 복합 키용 해시: 필드 섞기 방법
기본 타입에 대해서는 표준이 이미 std::hash<int>, std::hash<std::string> 등을 제공합니다. 따라서 우리 키의 논리는 다음과 같습니다:
- h1 = hash(ownerId) 계산
- h2 = hash(tag) 계산
- 이들 h1과 h2를 하나의 size_t로 적절히 섞기
학습 목적이라면 간단한 섞기가 충분합니다. 예를 들면:
- h1에 상수를 곱하고,
- h2를 더합니다.
#include <cstddef>
std::size_t CombineHash(std::size_t h1, std::size_t h2) {
return h1 * 31u + h2;
}
왜 이것이 “마법”이 아니라 실무적 관행인가요? 서로 다른 값 쌍이 보통 서로 다른 결과를 내게 하고 싶기 때문입니다. 상수 31은 교육용 예제에서 자주 쓰이는 선택으로 간단하고 역사적으로 널리 등장합니다. 완벽한 공식은 아니지만 return h1 + h2;처럼 서로 다른 쌍이 쉽게 충돌하는 방법보다는 낫습니다.
나쁜 해시 예(하지 말아야 할 예):
#include <cstddef>
std::size_t VeryBadHash() {
return 0; // 모든 키가 하나의 버킷으로
}
이런 해시는 ==가 정상이라면 정확성을 깨지 않지만(동작은 함), unordered_*의 목적이 사라지고 컨테이너가 사실상 느린 리스트처럼 동작하게 됩니다.
6. 해시를 unordered_map에 연결하는 방법
커스텀 해시 객체를 만들어 unordered_map에 명시적으로 전달하기
가장 간단하고 이해하기 쉬운 방법 중 하나는 std::hash<Key>를 직접 손대지 않고, 컨테이너에 세번째 템플릿 인자로 “해시 방법”을 전달하는 것입니다. 이를 위해 호출 가능한 함수 객체(즉, operator()를 가진 객체)가 필요합니다.
#include <cstddef>
#include <functional>
#include <string>
struct OwnerTagKey {
int ownerId{};
std::string tag;
};
bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
return a.ownerId == b.ownerId && a.tag == b.tag;
}
std::size_t CombineHash(std::size_t h1, std::size_t h2) {
return h1 * 31u + h2;
}
struct OwnerTagKeyHash {
std::size_t operator()(const OwnerTagKey& k) const {
std::size_t h1 = std::hash<int>{}(k.ownerId);
std::size_t h2 = std::hash<std::string>{}(k.tag);
return CombineHash(h1, h2);
}
};
이제 컨테이너는 이렇게 선언할 수 있습니다:
#include <unordered_map>
#include <unordered_set>
#include <string>
std::unordered_map<OwnerTagKey, std::unordered_set<int>, OwnerTagKeyHash> index;
이 방법의 장점은 선언 위치에서 어떤 키, 어떤 값, 어떤 해시를 쓰는지 바로 볼 수 있다는 점이고, namespace std에 손대지 않아도 된다는 점입니다.
std::hash<Key> 특수화
키를 표준 라이브러리에 “자연스럽게” 보이게 하고 싶다면, 사용자 타입에 대해 std::hash를 특수화할 수 있습니다. 사용자 정의 타입에 대해 이렇게 특수화하는 것은 허용되는 관행이며 표준 라이브러리도 때때로 이를 기대합니다.
문법은 약간 복잡해 보이지만 의미는 동일합니다: size_t를 반환하고 operator==에서 사용한 동일한 필드를 사용하면 됩니다.
#include <cstddef>
#include <functional>
#include <string>
struct OwnerTagKey {
int ownerId{};
std::string tag;
};
bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
return a.ownerId == b.ownerId && a.tag == b.tag;
}
std::size_t CombineHash(std::size_t h1, std::size_t h2) {
return h1 * 31u + h2;
}
namespace std {
template <>
struct hash<OwnerTagKey> {
std::size_t operator()(const OwnerTagKey& k) const noexcept {
std::size_t h1 = std::hash<int>{}(k.ownerId);
std::size_t h2 = std::hash<std::string>{}(k.tag);
return CombineHash(h1, h2);
}
};
}
noexcept에 주목하세요. 학습 코드에서는 항상 필수는 아니지만, 해시 함수를 noexcept로 만드는 것이 컨테이너의 보장과 최적화에 도움이 된다는 논의가 있습니다.
이러한 특수화를 하면 컨테이너 선언을 더 간단하게 쓸 수 있습니다:
#include <unordered_map>
#include <unordered_set>
std::unordered_map<OwnerTagKey, std::unordered_set<int>> index;
이제 키가 표준 라이브러리에 “친숙해진” 느낌입니다.
7. 예시: 소유자와 태그로 인덱싱한 TaskBook
이제 학습용 애플리케이션의 작고 일관된 조각을 만들어 보겠습니다. 우리는 두 가지 저장구조를 만들겠습니다:
- 기본 저장소: id → Task
- 보조 인덱스: (ownerId, tag) → id 집합
한 태스크가 단 하나의 태그만 가진다고 가정합시다. 이렇게 하면 단순해지고, 다중 태그는 단순히 반복문으로 처리하면 동일한 아이디어입니다.
#include <string>
struct Task {
int id{};
int ownerId{};
std::string title;
std::string tag;
};
이제 저장소의 '골격'을 보겠습니다:
#include <unordered_map>
#include <unordered_set>
std::unordered_map<int, Task> tasksById;
std::unordered_map<OwnerTagKey, std::unordered_set<int>> tasksByOwnerTag;
태스크 추가 시 두 구조를 모두 업데이트해야 합니다. 실무에서는 이를 함수로 숨기는 것이 좋으므로 간단한 버전을 작성해봅니다:
#include <utility>
void AddTask(const Task& t) {
tasksById.emplace(t.id, t);
OwnerTagKey key{t.ownerId, t.tag};
tasksByOwnerTag[key].insert(t.id); // 여기서 operator[]는 의도적: 없으면 집합을 생성
}
operator[]에 주목하세요: 이 경우에는 적절합니다. (ownerId, tag) 쌍에 대해 아직 집합이 없다면 첫 번째 태스크를 추가하는 시점에서 이를 생성하고 싶기 때문입니다.
소유자와 태그로 태스크를 찾는 전형적인 패턴은 find → 확인 → 사용입니다:
#include <iostream>
void PrintCountByOwnerTag(int ownerId, const std::string& tag) {
OwnerTagKey key{ownerId, tag};
if (auto it = tasksByOwnerTag.find(key); it != tasksByOwnerTag.end()) {
std::cout << it->second.size() << '\n'; // 예: 3
} else {
std::cout << 0 << '\n'; // 0
}
}
향후 완전한 CRUD(추가/삭제/이름 변경/태그 변경)를 구현할 때 이러한 인덱스는 속도와 단순한 로직을 제공합니다: 매번 전체 tasksById를 훑지 않아도 됩니다.
8. 사용자 정의 키와 std::hash에서 흔한 실수
실수 #1: operator==가 실제로 키를 결정하는 필드를 비교하지 않음.
종종 “태그는 별로 중요하지 않으니 무시하자”는 선의에서 발생합니다. 하지만 인덱스가 (ownerId, tag)를 기반으로 한다면 tag를 무시하면 안 됩니다: 컨테이너가 다른 키들을 합쳐버리고 요소를 숨기게 됩니다.
실수 #2: hash와 operator==가 서로 다른 필드를 사용함.
가장 위험한 실수로, 속도가 아니라 정확성을 망가뜨립니다. 삽입은 되었지만 find가 요소를 찾지 못할 수 있습니다. 컨테이너가 “나를 속이는” 것처럼 느껴지면 거의 확실히 이 규칙을 어긴 경우입니다.
실수 #3: 너무 “게으른” 해시 사용(예: 상수 반환 또는 한 필드만 해시).
이 코드는 작은 테스트에서는 잘 돌아가지만 실제 데이터에서는 느려집니다. 충돌은 허용되지만 대량으로 발생하면 unordered_map의 장점이 사라집니다.
실수 #4: 단순 존재 확인을 원할 때 operator[]를 사용함.
이것은 고전적인 함정입니다: tasksByOwnerTag[key]는 키가 없어도 빈 집합을 생성합니다. 그 결과 눈치채지 못하게 인덱스가 빈 항목으로 부풀려질 수 있습니다. 존재 확인에는 find/contains를 사용하고, operator[]는 “생성 또는 업데이트” 시나리오에만 사용하세요.
실수 #5: 수명 보장이 없는 view 타입을 키에 저장함(예: std::string_view).
string_view는 문자열을 소유하지 않습니다. 키에 string_view를 넣고 원본 문자열이 소멸하거나 변경되면 키는 유효하지 않은 참조가 됩니다. 해시 컨테이너의 키에는 보통 소유권을 가진 std::string을 저장하는 것이 안전합니다.
GO TO FULL VERSION