해시 테이블 병합, 성능 저하의 원인과 해결책은?
해시 테이블 병합 시, 성능 저하를 유발하는 주요 원인과 해결책을 제시함
Salted Hash Function, Preallocation, Stride Iteration 등 3가지 해결책을 제시하고, 각 방법의 장단점을 비교 분석함
커뮤니티에서는 해시 함수 선택의 중요성과 라이브러리별 성능 차이에 대한 논의가 활발하게 진행됨
해시 테이블 병합 성능 저하의 기술적 배경
해시 테이블 병합 시 성능 저하는 주로 Primary Clustering 현상으로 발생한다. 구체적으로, 동일한 해시 함수를 사용하는 두 해시 테이블을 병합할 때, 병합 대상 테이블의 데이터가 특정 버킷에 집중되면서 충돌(Collision)이 증가한다. 따라서, Swiss Table 기반의 구현체에서 이러한 문제가 두드러지게 나타난다.
해결책 비교: Salted Hash, Preallocation, Stride Iteration
Salted Hash는 각 해시 테이블 인스턴스에 랜덤 시드를 추가하여 해시 충돌을 완화한다. Preallocation은 병합 전 충분한 공간을 확보하여 메모리 사용량을 늘리는 대신, 캐시 효율을 높인다. 반면, Stride Iteration은 해시 테이블의 반복 순서를 변경하여 Primary Clustering을 회피하며, 라이브러리 수준의 변경이 필요하다.
실전 적용 가이드: 성능과 트레이드오프
Preallocation은 중복된 데이터가 적을 경우 가장 빠른 성능을 보이지만, 메모리 사용량이 증가할 수 있다. Salted Hash는 Abseil에서 기본적으로 제공되며, 대부분의 연산에서 무난한 성능을 보인다. 따라서, 해시 함수를 직접 구현해야 하는 경우, Salted Hash를 고려해 볼 수 있다. 결과적으로, Stride Iteration은 균형 잡힌 접근 방식이지만, 라이브러리 내부 구조에 대한 이해가 필요하다.
