Abseil Code Review · 28/79

absl::flat_hash_set — set 버전 Swiss Table

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

cpp abseil container hash-set swiss-table

#한 줄 요약

absl::flat_hash_set은 flat_hash_map의 set 대응이다. value 자체가 key 역할을 하며, Swiss Table 구조와 성능 특성, iterator 무효화 규칙은 동일하다. dedup, membership test, set 연산에서 std::unordered_set 대비 같은 성능 우위를 누린다.

#동기

flat_hash_set은 flat_hash_map<K, void>로 생각하면 된다. (key, value)가 아니라 key만. 사용 시나리오:

중복 제거 (dedup)
빠른 membership test
작은 집합 연산(intersection, union)

1
absl::flat_hash_set<std::string> seen;
2
for (const auto& line : input) {
3
  if (seen.insert(line).second) {
4
    Process(line);  // 첫 등장만 처리
5
  }
6
}

insert(x).second가 처음 삽입했는가를 알려준다. 이는 표준 set의 관용구다.

#API와 사용법

1
#include "absl/container/flat_hash_set.h"
2

3
absl::flat_hash_set<int> s = {1, 2, 3};
4

5
s.insert(4);
6
s.emplace(5);
7

8
if (s.contains(3)) { /*...*/ }
9
if (s.count(3) > 0) { /*...*/ }   // 동일
10
if (auto it = s.find(3); it != s.end()) { /*...*/ }
11

12
s.erase(1);

C++20부터 std::unordered_set에도 contains가 있지만, Abseil은 처음부터 제공했다. 가독성 측면에서 contains를 선호.

#heterogeneous lookup

1
absl::flat_hash_set<std::string> words;
2
words.insert("hello");
3

4
absl::string_view query = "hello";
5
if (words.contains(query)) { /*...*/ }   // no alloc
6
if (words.contains("hello")) { /*...*/ } // no alloc

std::unordered_set<std::string>::contains(string_view)는 C++20까지도 transparent 동작이 약하다. heterogeneous lookup이 자연스럽게 동작하는 점이 코드 가독성에 크다.

#set 연산

표준 set과 마찬가지로 <algorithm>의 set 연산은 정렬된 입력을 가정하므로 hash set에는 부적합하다. 직접 작성한다.

1
// 교집합
2
absl::flat_hash_set<int> Intersect(const absl::flat_hash_set<int>& a,
3
                                   const absl::flat_hash_set<int>& b) {
4
  const auto& smaller = a.size() < b.size() ? a : b;
5
  const auto& larger = a.size() < b.size() ? b : a;
6
  absl::flat_hash_set<int> r;
7
  r.reserve(smaller.size());
8
  for (int x : smaller) {
9
    if (larger.contains(x)) r.insert(x);
10
  }
11
  return r;
12
}

작은 쪽을 순회하고 큰 쪽에 contains로 조회하는 것이 O(min(|a|,|b|))이라 표준 코드보다 빠르다.

#std::unordered_set 비교

차이는 flat_hash_map 대 std::unordered_map과 동일하다.

항목	std::unordered_set	absl::flat_hash_set
storage	노드 chain	open-addressing flat array
lookup cache miss	2~3회	0~1회
iterator 안정성	insert/erase에 stable	rehash·erase에서 무효화
heterogeneous lookup	C++20 부분	처음부터 강력
평균 lookup	baseline	~2-3x

#내부 구현

flat_hash_set은 flat_hash_map<T, void>의 type alias가 아니다(value type이 없는 별도 instantiation). 다만 Swiss Table 코어를 공유하므로 Part 5-07에서 설명할 control byte / SIMD 스캔 / probing 전략이 그대로 적용된다.

#코드 리뷰 포인트

1. count → contains

1
// 회피
2
if (s.count(x)) { /*...*/ }
3

4
// Good
5
if (s.contains(x)) { /*...*/ }

count는 multiset 시절의 유산이다. flat_hash_set에서 count는 항상 0 또는 1이다. contains가 의도 표현이 더 좋다.

2. dedup 패턴

1
// 회피 — O(n²)
2
std::vector<std::string> dedup;
3
for (const auto& s : input) {
4
  if (std::find(dedup.begin(), dedup.end(), s) == dedup.end()) {
5
    dedup.push_back(s);
6
  }
7
}
8

9
// Good — O(n) 평균
10
absl::flat_hash_set<absl::string_view> seen;
11
std::vector<absl::string_view> dedup;
12
for (absl::string_view s : input) {
13
  if (seen.insert(s).second) dedup.push_back(s);
14
}

순서 보존 dedup의 표준 패턴.

3. 큰 element는 unique_ptr

1
// 회피
2
absl::flat_hash_set<BigStruct> s;  // rehash 시 대량 이동
3

4
// Good
5
absl::flat_hash_set<std::unique_ptr<BigStruct>, ByPtrHash, ByPtrEq> s;
6
// 또는
7
absl::node_hash_set<BigStruct> s;