SBCL의 적응형 해싱: 해시 테이블 속도 향상 및 강건성 개선

2024년 ELS 컨퍼런스에서 발표된 내용은 범용 해시 테이블의 속도와 강건성을 개선하기 위한 적응형 해싱에 초점을 맞추었습니다. 기존의 해시 테이블 이론은 주로 최악의 경우 점근적 비용에 초점을 맞추고 실제 성능에 미치는 상수 인자의 영향을 무시해 왔습니다. 이 연구에서는 키의 실제 분포에 따라 해시 함수를 조정하여 충돌을 줄이고 캐시 활용률을 높이는 온라인 적응형 접근 방식을 도입했습니다. 실험 결과, 예상 비교 횟수 감소와 PUT 연산 속도 향상에서 상당한 개선이 나타났으며, 특히 특정 키 분포에서 효과적임을 확인했습니다. SBCL의 내장 해시 테이블은 현재 이 기술을 사용하며, 충돌 횟수와 해시 테이블 크기에 따라 선형 검색, 비트 시프트 해시, MurmurHash 등의 해시 함수를 동적으로 전환합니다. 문자열이나 리스트와 같은 복합 키의 경우, 잘림 전략이 사용되며 충돌이 너무 많으면 잘림 길이가 동적으로 조정됩니다. 이러한 개선으로 SBCL 해시 테이블의 일반적인 경우 속도와 기타 경우 강건성이 향상되었습니다.