C++ 해시맵, 이렇게 빠를 수 있다고? 홉스카치 해싱의 비밀

C++ 표준 라이브러리의 std::unordered_map은 체이닝 방식 탓에 캐시 효율이 떨어져 늘 아쉬움이 남았습니다. Tessil이 만든 hopscotch-map은 '홉스카치 해싱'이라는 오픈 어드레싱 기법으로 이 한계를 정면 돌파한 헤더 온리 라이브러리입니다. 핵심 아이디어는 각 원소를 자신의 원래 해시 버킷에서 일정 거리(이웃, neighborhood) 안에만 배치하도록 보장하는 것입니다. 덕분에 조회 시 인접한 메모리만 훑으면 되어 캐시 적중률이 크게 올라가고, std 대비 수배 빠른 lookup 성능을 냅니다. tsl::hopscotch_map, hopscotch_set 등 STL과 거의 동일한 인터페이스를 제공해 기존 코드에 바로 끼워 넣기 좋고, 정수 키처럼 가벼운 타입에서 특히 강력합니다. 다만 삭제가 잦거나 메모리를 극도로 아껴야 하는 상황에서는 robin-hood나 그의 다른 라이브러리(sparse-map)와 벤치마크를 비교해보길 권합니다. 성능에 민감한 C++ 백엔드·게임·임베디드 개발자라면 한 번쯤 써볼 가치가 충분합니다.