C++ 해시맵 벤치마크 총정리: 어떤 구현체가 가장 빠를까?

해시맵, 다 같은 해시맵이 아니에요

C++로 개발하다 보면 std::unordered_map을 자연스럽게 사용하게 되는데요. 키-값 쌍을 빠르게 저장하고 조회하는 해시맵(Hash Map)은 거의 모든 프로그램에서 쓰이는 핵심 자료구조잖아요. 그런데 혹시 "표준 라이브러리의 unordered_map이 사실 꽤 느리다"는 이야기를 들어보신 적 있나요?

Martin Ankerl이라는 개발자가 C++에서 사용할 수 있는 다양한 해시맵 구현체들을 정말 꼼꼼하게 벤치마크한 자료가 있는데요, 삽입, 조회, 삭제, 메모리 사용량까지 다양한 관점에서 비교해놨어요. 해시맵을 많이 쓰는 고성능 시스템을 만들고 있다면 꼭 알아둘 만한 내용이에요.

벤치마크에 포함된 구현체들

이 벤치마크에서 비교하는 구현체가 상당히 많은데, 주요한 것들만 추려볼게요. 먼저 기준이 되는 건 C++ 표준 라이브러리의 std::unordered_map이에요. 이게 뭐냐면, C++ 표준에서 제공하는 "공식" 해시맵이에요. 어디서든 쓸 수 있다는 장점이 있지만, 성능 면에서는 아쉬운 점이 많아요.

그 이유를 간단히 설명하면, std::unordered_map은 체이닝(Chaining) 방식을 쓰거든요. 해시 충돌이 발생하면 같은 버킷에 연결 리스트로 데이터를 매달아 놓는 방식이에요. 이러면 메모리가 여기저기 흩어져서(캐시 미스가 많아져서) 현대 CPU에서 성능이 떨어질 수 있어요.

반면에 벤치마크 상위권을 차지하는 구현체들은 대부분 오픈 어드레싱(Open Addressing) 방식을 사용해요. 이건 충돌이 나면 연결 리스트를 만드는 대신, 테이블 안에서 빈 자리를 찾아가는 방식이에요. 데이터가 메모리에 연속적으로 배치되니까 CPU 캐시를 훨씬 효율적으로 활용할 수 있거든요.

대표적으로 Abseil의 absl::flat_hash_map(구글이 만든 라이브러리), Boost의 boost::unordered_flat_map, 그리고 Martin Ankerl 본인이 만든 ankerl::unordered_dense::map 등이 있어요. 이 외에도 Robin Hood 해싱을 사용하는 구현체, Folly(페이스북의 라이브러리)에 포함된 구현체 등 다양한 후보가 있어요.

벤치마크 결과에서 눈에 띄는 점들

결과를 보면 몇 가지 흥미로운 패턴이 보여요.

첫째, 거의 모든 서드파티 구현체가 std::unordered_map보다 빨라요. 단순 조회(lookup) 성능에서 2배에서 많게는 5배까지 차이가 나는 경우도 있어요. 특히 데이터 크기가 커질수록 캐시 효율의 차이가 극명하게 드러나요.

둘째, 삽입과 삭제에서는 구현체마다 특성이 달라요. 어떤 구현체는 조회는 엄청 빠른데 삽입 시 리해싱(rehashing) 비용이 크고, 어떤 구현체는 삽입·삭제가 고르게 빠른 대신 조회가 살짝 느린 트레이드오프가 있어요. 리해싱이 뭐냐면, 해시 테이블이 꽉 차면 더 큰 테이블로 옮겨야 하는데, 이때 기존 데이터를 전부 다시 배치하는 비용이에요.

셋째, 메모리 사용량도 꽤 차이가 나요. std::unordered_map은 노드 기반이라 원소마다 별도 메모리 할당이 일어나서 오버헤드가 크거든요. 오픈 어드레싱 기반 구현체들은 하나의 연속된 배열에 데이터를 저장하니까 메모리 효율이 훨씬 좋아요. 다만, 로드 팩터(테이블 대비 실제 데이터 비율)를 낮게 유지해야 해서, 빈 슬롯이 좀 낭비되는 면은 있어요.

넷째, 해시 함수 선택도 성능에 큰 영향을 줘요. 벤치마크에서는 여러 해시 함수도 함께 비교하는데, 같은 해시맵 구현체라도 해시 함수를 바꾸면 성능이 20~30% 달라지는 경우가 있어요.

업계에서의 위치

구글이 Abseil을 통해 flat_hash_map을 공개한 게 이 분야에서 큰 전환점이었어요. 구글 내부에서 사용하던 고성능 자료구조를 오픈소스로 풀면서, "표준 라이브러리만 고집할 필요가 없다"는 인식이 퍼졌거든요. 이후 Boost도 unordered_flat_map을 추가하면서, 이제는 성능이 중요한 프로젝트에서 오픈 어드레싱 해시맵을 사용하는 게 사실상 표준 관행이 되었어요.

Rust 진영에서는 이미 기본 해시맵(std::collections::HashMap)이 Swiss Table(구글의 오픈 어드레싱 구현) 기반이에요. C++은 표준 변경이 느리다 보니 아직 std::unordered_map이 체이닝 기반이지만, 미래 표준에서는 변경될 가능성도 있어요.

한국 개발자에게 주는 시사점

게임 서버, 실시간 데이터 처리, 고빈도 트레이딩 같은 성능에 민감한 C++ 프로젝트를 하고 계시다면, std::unordered_map을 absl::flat_hash_map이나 boost::unordered_flat_map으로 교체하는 것만으로 눈에 보이는 성능 개선을 얻을 수 있어요. 특히 해시맵 조회가 핫패스(hot path, 자주 실행되는 경로)에 있다면 효과가 크죠.

교체할 때 주의할 점이 하나 있는데요, 오픈 어드레싱 기반 해시맵은 포인터 안정성(pointer stability)을 보장하지 않는 경우가 많아요. 이게 뭐냐면, 원소를 삽입하거나 테이블이 리사이즈될 때 기존 원소의 메모리 주소가 바뀔 수 있다는 거예요. std::unordered_map은 노드 기반이라 이 보장이 되거든요. 기존 코드가 해시맵 원소의 포인터나 참조를 오래 들고 있다면, 교체 전에 이 부분을 꼭 확인해야 해요.

C++을 쓰지 않더라도, 해시맵의 내부 구조 차이(체이닝 vs 오픈 어드레싱)와 캐시 효율은 모든 언어의 개발자가 알아두면 좋은 기본기예요. 면접에서 자료구조 질문으로도 종종 나오고요.