Abseil Code Review · 57/79

Abseil HashState chaining

2026년 6월 12일 · Hawk · 3분 읽기

#HashState의 정체

AbslHashValue 함수가 받는 H는 HashState concept을 만족하는 타입이다. Abseil 내부에서는 absl::hash_internal::MixingHashState 같은 구체 구현이 들어오지만 사용자는 추상 인터페이스만 본다.

1
template <typename H>
2
friend H AbslHashValue(H h, const MyType& v) {
3
    // h: HashState — 누적된 해시 상태
4
    // 반환: 새 HashState
5
    return H::combine(std::move(h), v.field1, v.field2);
6
}

HashState는 immutable에 가까운 모델 — combine은 새 상태를 반환한다.

#combine — 기본 chaining

1
template <typename H>
2
friend H AbslHashValue(H h, const Order& o) {
3
    return H::combine(std::move(h), o.id, o.user_id, o.amount, o.timestamp);
4
}

combine(h, x1, x2, ..., xN)은 순차적으로 각 인자를 누적한다. 내부적으로는 다음과 동등.

1
h = AbslHashValue(std::move(h), x1);
2
h = AbslHashValue(std::move(h), x2);
3
...
4
return h;

각 인자에 대해 그 타입의 AbslHashValue를 ADL로 찾아 호출.

#combine_contiguous — 연속 메모리 최적화

같은 타입의 N개를 한 번에 hash할 때.

1
template <typename H>
2
friend H AbslHashValue(H h, const Histogram& hg) {
3
    return H::combine_contiguous(std::move(h), hg.bins.data(), hg.bins.size());
4
}

combine_contiguous는 trivially-hashable 타입(int, char, float 등)이면 바이트 단위 묶어 한 번에 처리한다. 일반 combine을 N번 부르는 것보다 빠르다.

#combine_unordered — set·map 친화

set·unordered_map의 hash는 순서에 무관 해야 한다.

1
template <typename H>
2
friend H AbslHashValue(H h, const Bag& b) {
3
    return H::combine_unordered(std::move(h), b.items.begin(), b.items.end());
4
}

내부적으로 각 원소의 hash를 commutative하게 결합(XOR가 아닌 안전한 방식). 같은 원소집합이면 어떤 순서로 들어와도 같은 결과.

absl::flat_hash_set·absl::flat_hash_map의 hash가 이걸 쓴다.

#H::combine의 의미론

combine은 다음을 약속한다.

결정적 — 같은 시드, 같은 입력이면 같은 결과.
분포 좋음 — 약한 비트가 없도록 mixing 함수 적용.
순서 의존 — combine(h, a, b)와 combine(h, b, a)는 다른 결과(원하면 combine_unordered 사용).
타입 의존 — int 0과 string ""이 같은 결과를 내지 않음.

마지막 항목이 중요하다. 사용자가 직접 h = h * 31 + x 같은 코드를 짜면 (0, "")와 ("", 0)이 같은 결과를 낼 수 있다. combine은 타입 인코딩을 포함해 이런 충돌을 막는다.

#가변 alternative — variant

variant의 hash는 index + active value 를 함께 섞는다.

1
template <typename H>
2
friend H AbslHashValue(H h, const absl::variant<int, std::string>& v) {
3
    return H::combine(std::move(h), v.index(), absl::visit([](auto&& x) {
4
        return absl::Hash<std::decay_t<decltype(x)>>{}(x);
5
    }, v));
6
}

Abseil이 variant에 대해 기본 AbslHashValue를 제공하므로 사용자는 보통 직접 짤 일이 없다. 단, 자체 sum type에 hash가 필요하면 같은 패턴.

#작은 예시 — nested struct

1
struct Address {
2
    std::string street;
3
    std::string city;
4

5
    template <typename H>
6
    friend H AbslHashValue(H h, const Address& a) {
7
        return H::combine(std::move(h), a.street, a.city);
8
    }
9
};
10

11
struct Person {
12
    std::string name;
13
    Address address;
14
    std::vector<std::string> phones;
15

16
    template <typename H>
17
    friend H AbslHashValue(H h, const Person& p) {
18
        // address: 그 자체로 AbslHashValue 정의 → combine이 위임
19
        // phones: vector<string>은 std로 제공된 hash 사용
20
        return H::combine(std::move(h), p.name, p.address, p.phones);
21
    }
22
};

combine이 각 인자의 AbslHashValue를 ADL로 찾아 재귀적으로 합성한다. 사용자는 평탄한 한 줄만 쓴다.

#회피 패턴

1
// 회피 — 직접 mixing
2
template <typename H>
3
friend H AbslHashValue(H h, const Bad& b) {
4
    size_t s = std::hash<int>{}(b.x);
5
    s ^= std::hash<std::string>{}(b.y) << 1;   // ❌ 약한 분포
6
    return H::combine(std::move(h), s);
7
}
8

9
// Good
10
template <typename H>
11
friend H AbslHashValue(H h, const Bad& b) {
12
    return H::combine(std::move(h), b.x, b.y);
13
}

1
// 회피 — set hash인데 순서 의존
2
template <typename H>
3
friend H AbslHashValue(H h, const MySet& s) {
4
    return H::combine_contiguous(std::move(h), s.items.data(), s.items.size());
5
    // ❌ {1,2,3}과 {3,2,1}이 다른 해시
6
}
7

8
// Good — unordered 헬퍼
9
template <typename H>
10
friend H AbslHashValue(H h, const MySet& s) {
11
    return H::combine_unordered(std::move(h), s.items.begin(), s.items.end());
12
}

1
// 회피 — std::move 누락
2
template <typename H>
3
friend H AbslHashValue(H h, const X& x) {
4
    return H::combine(h, x.a);   // ❌ rvalue 권장
5
}
6

7
// Good
8
return H::combine(std::move(h), x.a);

H는 가벼운 값 타입 으로 설계되어 move가 cheap하지만, 관례적으로 std::move를 명시한다.

#표 — combine 변형

메서드	용도
`combine(h, x1, x2, ...)`	순서 있는 필드 chaining
`combine_contiguous(h, ptr, n)`	같은 타입 연속 — 빠름
`combine_unordered(h, it1, it2)`	순서 무관 (set·map)