hopscotch hashing을 사용한 빠른 hash map 및 hash set의 C++ 구현

AI 요약

hopscotch-map 라이브러리는 오픈 어드레싱과 hopscotch 해싱을 사용한 빠른 C++ 해시 맵 및 해시 셋 구현체입니다. std::unordered_map보다 대부분의 경우 성능이 우수하며, google::dense_hash_map과 유사하면서도 메모리를 덜 사용하고 더 많은 기능을 제공합니다. 헤더 전용 라이브러리로 설치가 간편하며, 다양한 성장 정책과 추가 기능을 지원하는 여러 클래스를 제공합니다.

핵심 포인트

• tsl::hopscotch_map, tsl::hopscotch_set 등 주요 클래스 제공 (2의 거듭제곱 성장 정책)
• tsl::bhopscotch_map 계열은 키에 LessThanComparable 요구사항 추가, 최악의 경우 O(log n) 보장
• 헤더 전용 라이브러리로 include 디렉토리만 추가하면 사용 가능
• 이동 전용 키/값, 이종 조회, 사전 계산된 해시 값 전달 등 다양한 고급 기능 지원

향후 전망

• 해시 테이블 성능 최적화가 중요한 C++ 프로젝트에서 표준 라이브러리 대체재로 널리 채택될 가능성